Approximating High-Dimensional Earth Mover’s Distance as Fast as Closest Pair

Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten · 2025

Read Approximating High-Dimensional Earth Mover’s Distance as Fast as Closest Pair by Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-06774.txt.

Introduction

Lorenzo Beretta and co-authors give a 2025 math result linking two hard tasks with points in high dimensional space. One task is Earth Mover's Distance, the least cost of pairing two point sets by distance. The other is Closest Pair, finding the two points that sit nearest each other across the sets.

The authors show that a fast near exact method for Closest Pair can be turned into one for Earth Mover's Distance with a like gain in speed. Their key step runs a known update method without storing all its weights, using the shape of the point sets instead. Plugging in the best known Closest Pair method beats the prior fastest time for this distance task.

Catalog record

CREATORLorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE143 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-06774

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

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 + ε ) (1+\varepsilon) -approximate Earth Mover’s Distance (EMD) to ( 1 + ε ) (1+\varepsilon) -approximate Closest Pair (CP). As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given p ∈ [ 1 , 2 ] p\in[1,2] and two sets of n n points X , Y ⊂ ( ℝ d , ℓ p ) X,Y\subset(\mathbbm{R}^{d},\ell_{p}) , their EMD is the minimum cost of a perfect matching between X X and Y Y , where the cost of matching two vectors is their ℓ p \ell_{p} distance. Further, CP is the basic problem of finding a pair of points realizing min x ∈ X , y ∈ Y ⁡ ‖ x − y ‖ p \min_{x\in X,y\in Y}||x-y||_{p} . Our contribution is twofold: • We show that if a ( 1 + ε ) (1+\varepsilon) -approximate CP can be computed in time n 2 − ϕ n^{2-\phi} , then a 1 + O ⁡ ( ε ) 1+O(\varepsilon) approximation to EMD can be computed in time n 2 − Ω ⁡ ( ϕ ) n^{2-\Omega(\phi)} . • Plugging in the fastest known algorithm for CP [ ACW16 ] , we obtain a ( 1 + ε ) (1+\varepsilon) -approximation algorithm for EMD running in time n 2 − Ω ~ ​ ( ε 1 / 3 ) n^{2-\tilde{\Omega}(\varepsilon^{1/3})} for high-dimensional point sets, which improves over the prior fastest running time of n 2 − Ω ⁡ ( ε 2 ) n^{2-\Omega(\varepsilon^{2})} [ AZ23 ] . 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. 1 Introduction In this paper, we study algorithms for the Earth Mover’s Distance ( \mathsf{EMD} ) which is a fundamental measure of dissimilarity between two sets of point in a metric space [ Vil+08 , San15 , PC19 ] (also known as the Wasserstein-1 metric). Specifically, we consider the ground metric (\mathbbm{R}^{d},\ell_{p}) , for p\in[1,2] , and given two subsets of n vectors, X=\{x_{1},\dots,x_{n}\},Y=\{y_{1},\dots,y_{n}\}\subset\mathbbm{R}^{d} , the Earth Mover’s distance ( \mathsf{EMD} ) between X and Y is \mathsf{EMD}(X,Y)=\min_{\begin{subarray}{c}\pi\colon[n]\to[n]\\ \text{bijection}\end{subarray}}\hskip 5.69046pt\sum_{i=1}^{n}\|x_{i}-y_{\pi(i)}\|_{p} In other words, \mathsf{EMD}(x,y) is the value of a min-cost flow in the complete bipartite geometric graph: the n points of X become vertices on the left-hand side and have uniform supply, the n points of Y become vertices on the right-hand side and have uniform demand, and every edge between x_{i} and y_{j} appears with cost \|x_{i}-y_{j}\|_{p} and infinite capacity. A natural algorithmic approach to compute \mathsf{EMD} is to first construct the geometric graph and then utilize the best graph algorithm for min-cost flow. However, this graph has n^{2} edges, resulting in an at least quadratic time algorithm. On the other hand, the input has size O(nd) , thus it is feasible that faster algorithms exist. In fact, there is a extensive line-of-work on approximation algorithms for \mathsf{EMD} running in sub-quadratic time; to avoid constructing the complete graph, algorithms must exploit the geometric structure of (\mathbbm{R}^{d},\ell_{p}) [ Cha02 , IT03 , AIK08 , SA20 , AS14 , And+14 , Aga+17 , KNP19 , Roh19 , Aga+22 , AZ23 , BR24 , Cha+23 , FL23 ] . The Spanner Approach. A standard approach to avoid constructing the full geometric graph is to employ geometric spanners , which are sparse graphs where the shortest path distances approximates the geometric distances. Since the runtime of min-cost flow graph algorithms scale with the number of edges [ She17 , ASZ20 , Li20 , Che+22 ] , sparser spanners will yield faster approximations for \mathsf{EMD} . 1 1 1 Using the almost-linear time algorithm for capacitated min-cost flow [ Che+22 ] , it suffices to construct a directed spanner (i.e., a directed graph whose shortest paths approximate pairwise distances). If using near-linear, approximate, uncapacitated min-cost flow [ She17 , ASZ20 , Che+22 , Li20 ] , the spanner must be undirected. In low-dimensional space, where d=o(\log n) , one can construct (1+\varepsilon ) approximate spanners with n\cdot O(\varepsilon^{-d}) edges [ Cla87 , Alt+93 , RS91 ] . However, until recently it was not known whether sub-quadratic (1+\varepsilon) approximate spanners exist for high-dimensional spaces for \varepsilon<2.4 . 2 2 2 For large constant approximations, it is known that C -approximate n^{1+O(1/C)} sized spanners exist [ HIS13 ] . This was addressed by [ AZ23 ] , who designed such spanners (crucially using additional Steiner vertices) with n^{2-\Omega(\varepsilon^{3})} undirected edges or n^{2-\Omega(\varepsilon^{2})} directed edges. The main application of their work is a (1+\varepsilon) -approximation algorithm for \mathsf{EMD} over (\mathbbm{R}^{d},\ell_{p}) running in time n^{2-\Omega(\varepsilon^{2})} . To date, this is the only sub-quadratic (1+\varepsilon) approximation of high-dimensional \mathsf{EMD} . The fact that the runtimes of all state-of-the-art \mathsf{EMD} approximations are directly tied to the best available spanner construction motivates our central question: can this dependency be circumvented? Specifically: Do there exists (1+\varepsilon) -approximation algorithms to high-dimensional \mathsf{EMD} with running times faster than that of the best spanner constructions? We answer the above question affirmatively, and thereby improve the runtime of best known (1+\varepsilon) approximation for \mathsf{EMD} . Our key technical contribution enabling this is a black-box reduction from \mathsf{EMD} to the approximate closest pair (CP) problem. Here, the CP problems is: given two sets X,Y\subseteq\mathbbm{R}^{d} , return a pair (x,y)\in X\times Y such that \|x-y\|_{1}\leq(1+\varepsilon)\min_{x^{\prime}\in X,y^{\prime}\in Y}\|x^{\prime}-y^{\prime}\|_{1} . 3 3 3 For both \mathsf{EMD} and CP, we focus on the \ell_{1} norm. Via standard reductions [ JS82 ] , one can embed \ell_{p} for p\in[1,2] into \ell_{1} with (1+\varepsilon) error, making \ell_{1} the more general space. Closest pair is a cornerstone problem in computational geometry [ Val15 , ACW16 ] , and is intimately related to the nearest neighbor search problem [ IM98 , HIM12 , AI08 , And09 ] . Crucially, CP is amenable to powerful algorithmic techniques outside of spanners, most notably the polynomial method [ ACW16 ] . These techniques have yielded CP algorithms with runtimes faster than the best known spanner constructions. Specifically, we prove the following: Theorem 1 (Main Theorem, informal version of Theorem 5 ) . If there exists an algorithm for (1+\varepsilon) -approximate closest pair on (\mathbb{R}^{d},\ell_{1}) with running time T_{CP}(n,\varepsilon)=n^{2-\phi(\varepsilon)} , then there exists an algorithm that computes a (1+O(\varepsilon)) -approximation to \mathsf{EMD}(A,B) over (\mathbb{R}^{d},\ell_{p}) for any p\in[1,2] in time n^{2-\Omega(\phi(\varepsilon))} . Theorem 1 provides a fine-grained reduction, translating runtime improvements for CP directly into runtime improvements for \mathsf{EMD} , losing only a constant in \varepsilon and \phi(\varepsilon) . The existence of such an efficient reduction is perhaps surprising. Namely, while exact closest pair admits a simple O(n^{2}) algorithm, computing \mathsf{EMD} , which is a global matching optimization task, appears significantly more complex. Indeed, a natural greedy approach for \mathsf{EMD} —repeatedly finding the closest available pair (a,b) , matching them, and removing them—is known to yield very poor approximations [ RT81 ] . Despite the failure of this simple reduction, Theorem 1 demonstrates that, via a considerably more

Read the complete text