Skip to yearly menu bar Skip to main content


Virtual presentation / top 25% paper

A Higher Precision Algorithm for Computing the 1-Wasserstein Distance

Pankaj Agarwal · Sharath Raghvendra · Pouyan Shirzadian · Rachita Sowle

Keywords: [ Bipartite Matching ] [ wasserstein distance ] [ Earth Movers Distance ] [ Optimization ]


Abstract: 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)logn) time and boosts the accuracy of estimating W(μ,ν) from ε to an expected additive error of min{ε,(dlogd/ε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{ε,(dloglogn)W(μ,ν)} in O(T(n,ε/d)loglogn) time.

Chat is not available.