Computing Kantorovich-Wasserstein Distances on $d$-dimensional histograms using $(d+1)$-partite graphs
This provides an efficient method for computing optimal transport distances in applications like image processing and biomedical data analysis, though it appears incremental as it builds on existing graph-based flow formulations.
The paper tackles the problem of computing exact Kantorovich-Wasserstein distances for d-dimensional histograms by proving equivalence to an uncapacitated minimum cost flow problem on a (d+1)-partite graph, and shows numerically that this approach is competitive with state-of-the-art algorithms on gray scale images and biomedical histograms.
This paper presents a novel method to compute the exact Kantorovich-Wasserstein distance between a pair of $d$-dimensional histograms having $n$ bins each. We prove that this problem is equivalent to an uncapacitated minimum cost flow problem on a $(d+1)$-partite graph with $(d+1)n$ nodes and $dn^{\frac{d+1}{d}}$ arcs, whenever the cost is separable along the principal $d$-dimensional directions. We show numerically the benefits of our approach by computing the Kantorovich-Wasserstein distance of order 2 among two sets of instances: gray scale images and $d$-dimensional biomedical histograms. On these types of instances, our approach is competitive with state-of-the-art optimal transport algorithms.