Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2602.14852 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910023892860928 |
|---|---|
| author | Gartland, Chris Ostrovskii, Mikhail |
| author_facet | Gartland, Chris Ostrovskii, Mikhail |
| contents | Quantifying the degree of dissimilarity between two probability distributions on a finite metric space is a fundamental task in Computer Science and Computer Vision. A natural dissimilarity measure based on optimal transport is the Earth Mover's Distance (EMD). A key technique for analyzing this metric, pioneered by Charikar (2002) and Indyk and Thaper (2003), involves constructing low-distortion embeddings of EMD(X) into the Lebesgue space $L_1$.
It became a key problem to investigate whether the upper bound of $O(\log n)$ can be improved for important classes of metric spaces known to admit low-distortion embeddings into $L_1$. In the context of Computer Vision, grid graphs, especially planar grids, are among the most fundamental. Indyk posed the related problem of estimating the $L_1$-distortion of the space of uniform distributions on $n$-point subsets of $R^2$. The Progress Report, last updated in August 2011, highlighted two key results: first, the work of Khot and Naor (2006) on Hamming cubes, which showed that the $L_1$-distortion for Hamming cubes meets the described above upper estimate, and second, the result of Naor and Schechtman (2007) for planar grids, which established that the $L_1$-distortion of for a planar $n$ by $n$ grid is $Ω(\sqrt{\log n})$.
Our first result is the improvement of the lower bound on the $L_1$-distortion for grids to $Ω(\log n)$, matching the universal upper bound up to multiplicative constants. The key ingredient allowing us to obtain these sharp estimates is a new Sobolev-type inequality for scalar-valued functions on the grid graphs. Our method is also applicable to many recursive families of graphs, such as diamond and Laakso graphs. We obtain the sharp distortion estimates of $\log n$ in these cases as well. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_14852 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Lower Estimates for $L_1$-Distortion of Transportation Cost Spaces Gartland, Chris Ostrovskii, Mikhail Functional Analysis Computational Geometry Combinatorics Metric Geometry 51F30 (Primary) 05C76, 30L05, 46B03, 49Q22, 68R12, 68W25 (Secondary) Quantifying the degree of dissimilarity between two probability distributions on a finite metric space is a fundamental task in Computer Science and Computer Vision. A natural dissimilarity measure based on optimal transport is the Earth Mover's Distance (EMD). A key technique for analyzing this metric, pioneered by Charikar (2002) and Indyk and Thaper (2003), involves constructing low-distortion embeddings of EMD(X) into the Lebesgue space $L_1$. It became a key problem to investigate whether the upper bound of $O(\log n)$ can be improved for important classes of metric spaces known to admit low-distortion embeddings into $L_1$. In the context of Computer Vision, grid graphs, especially planar grids, are among the most fundamental. Indyk posed the related problem of estimating the $L_1$-distortion of the space of uniform distributions on $n$-point subsets of $R^2$. The Progress Report, last updated in August 2011, highlighted two key results: first, the work of Khot and Naor (2006) on Hamming cubes, which showed that the $L_1$-distortion for Hamming cubes meets the described above upper estimate, and second, the result of Naor and Schechtman (2007) for planar grids, which established that the $L_1$-distortion of for a planar $n$ by $n$ grid is $Ω(\sqrt{\log n})$. Our first result is the improvement of the lower bound on the $L_1$-distortion for grids to $Ω(\log n)$, matching the universal upper bound up to multiplicative constants. The key ingredient allowing us to obtain these sharp estimates is a new Sobolev-type inequality for scalar-valued functions on the grid graphs. Our method is also applicable to many recursive families of graphs, such as diamond and Laakso graphs. We obtain the sharp distortion estimates of $\log n$ in these cases as well. |
| title | Lower Estimates for $L_1$-Distortion of Transportation Cost Spaces |
| topic | Functional Analysis Computational Geometry Combinatorics Metric Geometry 51F30 (Primary) 05C76, 30L05, 46B03, 49Q22, 68R12, 68W25 (Secondary) |
| url | https://arxiv.org/abs/2602.14852 |