A HIGHER PRECISION ALGORITHM FOR COMPUTING THE 1-WASSERSTEIN DISTANCE

We consider the problem of computing the 1-Wasserstein distance W(µ, ν) between two d-dimensional discrete distributions µ and ν whose support lie within the unit hypercube. There are several algorithms that estimate W(µ, ν) within an additive error of ε. However, when W(µ, ν) is small, the additive error ε dominates, leading to noisy results. Consider any additive approximation algorithm with execution time T(n, ε). We propose an algorithm that runs in O(T(n, ε/d) log n) time and boosts the accuracy of estimating W(µ, ν) from ε to an expected additive error of min{ε, (dlog^√d/ε n)W(µ, ν)}. For the special case where every point in the support of µ and ν has a mass of 1/n (also called the Euclidean Bipartite Matching problem), we describe an algorithm to boost the accuracy of any additive approximation algorithm from ε to an expected additive error of min{ε, (dlog log n)W(µ, ν)} in O(T(n, ε/d) log log n) time.

Duke Scholars

Author Pankaj K. Agarwal Computer Science