Answers are grounded in this paper and cite their sources.
In this work, we present a method to compute the Kantorovich--Wasserstein distance of order 1 between a pair of two-dimensional histograms. Recent works in computer vision and machine learning have shown the benefits of measuring Wasserstein distances of order 1 between histograms with n bins by solving a classical transportation problem on very large complete bipartite graphs with n nodes and n² edges. The main contribution of our work is to approximate the original transportation problem by an uncapacitated min cost flow problem on a reduced flow network of size $O(n)$ that exploits the geometric structure of the cost function. More precisely, when the distance among the bin centers is measured with the 1-norm or the ∞-norm, our approach provides an optimal solution. When the distance among bins is measured with the 2-norm, (i) we derive a quantitative estimate on the error between optimal and approximate solution; (ii) given the error, we construct a reduced flow network of size $O(n)$.
No takes yet. Share an insight, caveat, or question.
Bassetti et al. (2020) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: