On the computation of kantorovich-wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows

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 n2 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).