Virtual presentation / top 25% paper
A Higher Precision Algorithm for Computing the -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 -Wasserstein distance between two -dimensional discrete distributions and whose support lie within the unit hypercube. There are several algorithms that estimate within an additive error of . However, when is small, the additive error dominates, leading to noisy results. Consider any additive approximation algorithm with execution time . We propose an algorithm that runs in time and boosts the accuracy of estimating from to an expected additive error of . For the special case where every point in the support of and has a mass of (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 in time.
Chat is not available.