Computing Kantorovich-Wasserstein Distances on $d$-Dimensional Histograms Using $(d+1)$-Partite Graphs
Abstract
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.
Cite
Text
Auricchio et al. "Computing Kantorovich-Wasserstein Distances on $d$-Dimensional Histograms Using $(d+1)$-Partite Graphs." Neural Information Processing Systems, 2018.Markdown
[Auricchio et al. "Computing Kantorovich-Wasserstein Distances on $d$-Dimensional Histograms Using $(d+1)$-Partite Graphs." Neural Information Processing Systems, 2018.](https://mlanthology.org/neurips/2018/auricchio2018neurips-computing/)BibTeX
@inproceedings{auricchio2018neurips-computing,
title = {{Computing Kantorovich-Wasserstein Distances on $d$-Dimensional Histograms Using $(d+1)$-Partite Graphs}},
author = {Auricchio, Gennaro and Bassetti, Federico and Gualandi, Stefano and Veneroni, Marco},
booktitle = {Neural Information Processing Systems},
year = {2018},
pages = {5793-5803},
url = {https://mlanthology.org/neurips/2018/auricchio2018neurips-computing/}
}