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

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 $X,Y \subset \left( {{\mathbb{R}^d},{\ell _p}} \right)$, 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 ${n^{2 - \tilde \Omega \left( {{\varepsilon ^{1/3}}} \right)}}$ for high-dimensional point sets, which improves over the prior fastest running time of ${n^{2 - \Omega \left( {{\varepsilon ^2}} \right)}}$ [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.