Lower Estimates for L₁-Distortion of Transportation Cost Spaces

Quantifying the degree of dissimilarity between two probability distributions on a finite metric space X is a fundamental task in Computer Science and Computer Vision. A natural dissimilarity measurement based on optimal transport is the earth mover's distance (EMD), also known as the Kantorovich metric or Wasserstein-1 metric. We denote the metric space of probability measures on X equipped with the earth mover's distance as EMD(X), called the earth mover's space. A key technique for analyzing this metric -pioneered by Charikar [Cha02] and Indyk and Thaper [IT03] -involves constructing low-distortion embeddings of EMD(X) into the Lebesgue space L1. The best upper bound for the distortion of an embedding of EMD(X) with |X| = n into L1 is O(log n). This result follows from a combination of Charikar's work (which builds on [KT02]) and the seminal result by Fakcharoenphol, Rao, and Talwar [FRT04]. Moreover, it is well known that expander graphs yield a matching lower bound of Ω(log n) for L1-distortion, showing that the upper bound can be tight.

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 L1. In the context of Computer Vision, grid graphs -especially planar grids -are among the most fundamental. Indyk posed in [MN11, Problem 2.17] the related problem of estimating the L1distortion of the space of uniform distributions on n-point subsets of R 2 . The Progress Report in [MN11], last updated in August 2011, highlighted two key results: first, the work of Khot and Naor [KN06] on Hamming cubes, which showed that the L1-distortion of EMD(0, 1 n ) is of the order n, and second, the result of Naor and Schechtman [NS07] for planar grids, which established that the L1-distortion of EMD(0, . . . , n 2 ) is Ω( √ log n). Our first result is the improvement of the lower bound on the L1-distortion of EMD(0, . . . , n 2 ) 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.