Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.19434 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918350255292416 |
|---|---|
| author | Gartland, Chris Ostrovskii, Mikhail Rabani, Yuval Young, Robert |
| author_facet | Gartland, Chris Ostrovskii, Mikhail Rabani, Yuval Young, Robert |
| contents | We prove that the distortion of any embedding into $L_1$ of the transportation cost space or earth mover distance over a $d$-dimensional grid $\{1,\dots m\}^d$ is $Ω(\log N)$, where $N$ is the number of vertices and the implicit constant is universal (in particular, independent of dimension). This lower bound matches the universal upper bound $O(\log N)$ holding for any $N$-point metric space. Our proof relies on a new Sobolev inequality for real-valued functions on the grid, based on random measures supported on dyadic cubes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_19434 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | $L_1$-distortion of Earth Mover Distances and Transportation Cost Spaces on High Dimensional Grids Gartland, Chris Ostrovskii, Mikhail Rabani, Yuval Young, Robert Functional Analysis Computational Geometry Metric Geometry We prove that the distortion of any embedding into $L_1$ of the transportation cost space or earth mover distance over a $d$-dimensional grid $\{1,\dots m\}^d$ is $Ω(\log N)$, where $N$ is the number of vertices and the implicit constant is universal (in particular, independent of dimension). This lower bound matches the universal upper bound $O(\log N)$ holding for any $N$-point metric space. Our proof relies on a new Sobolev inequality for real-valued functions on the grid, based on random measures supported on dyadic cubes. |
| title | $L_1$-distortion of Earth Mover Distances and Transportation Cost Spaces on High Dimensional Grids |
| topic | Functional Analysis Computational Geometry Metric Geometry |
| url | https://arxiv.org/abs/2602.19434 |