Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten
Abstract
We give a reduction from (1 + ε)-approximate Earth Mover’s Distance (EMD) to (1 + ε)-approximate Closest Pair (CP). As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given p ∈ [1], [2] and two sets of n points , their EMD is the minimum cost of a perfect matching between X and Y, where the cost of matching two vectors is their ℓpdistance. Further, CP is the basic problem of finding a pair of points realizing minx∈X,y∈Y║x − y║p. Our contribution is twofold:• We show that if (1 + ε)-approximate CP can be computed in time n2−ϕ, then a 1 + O(ε) approximation to EMD can be computed in time n2−Ω(ϕ).• Plugging in the fastest known algorithm for CP [5], we obtain a (1 + ε)-approximation algorithm for EMD running in time for high-dimensional point sets, which improves over the prior fastest running time of [13].Our main technical contribution is a sublinear implementation of the Multiplicative Weights Update framework for EMD. Specifically, we demonstrate that the updates can be executed without ever explicitly computing or storing the weights; instead, we exploit the underlying geometric structure to perform the updates implicitly.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers2
Builds on8
- Maximum Flow and Minimum-Cost Flow in Almost-Linear TimeLi Chen, Rasmus Kyng, Yang P. Liu, Richard Peng et al.FOCS 2022 · 135 citations
- Parallel approximate undirected shortest paths via low hop emulatorsAlexandr Andoni, Clifford Stein, Peilin ZhongSTOC 2020 · 50 citations
- Faster parallel algorithm for approximate shortest pathJason LiSTOC 2020 · 48 citations
- New streaming algorithms for high dimensional EMD and MSTXi Chen, Rajesh Jayaram, Amit Levi, Erik WaingartenSTOC 2022 · 11 citations
- Better Sum Estimation via Weighted SamplingLorenzo Beretta, Jakub TetekSODA 2022 · 7 citations
Related papers
- Approximate Earth Mover's Distance in Truly-Subquadratic TimeLorenzo Beretta, Aviad RubinsteinSTOC 2024 · 3 citations
- Near-Linear Time Algorithm for the Chamfer DistanceAinesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal et al.NeurIPS 2023 · 9 citations
- A Robust Exact Algorithm for the Euclidean Bipartite Matching ProblemAkshaykumar Gattani, Sharath Raghvendra, Pouyan ShirzadianNeurIPS 2023 · 6 citations
- Tree Embedding in High Dimensions: Dynamic and Massively ParallelGramoz Goranci, Shaofeng H.-C. Jiang, Peter Kiss, Qihao Kong et al.SODA 2026
- Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with ApplicationsAlexandr Andoni, Hengjie ZhangFOCS 2023 · 4 citations
