This portal has been archived. Explore the next generation of this technology.
Computing Kantorovich-Wasserstein Distances on d-dimensional histograms using (d+1)-partite graphs
lib:6407684390aad244 (v1.0.0)
Authors: Gennaro Auricchio,Federico Bassetti,Stefano Gualandi,Marco Veneroni
Where published: NeurIPS 2018 12
Document: PDF DOI
Abstract URL: http://papers.nips.cc/paper/7821-computing-kantorovich-wasserstein-distances-on-d-dimensional-histograms-using-d1-partite-graphs
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.
Where published: NeurIPS 2018 12
Document: PDF DOI
Abstract URL: http://papers.nips.cc/paper/7821-computing-kantorovich-wasserstein-distances-on-d-dimensional-histograms-using-d1-partite-graphs
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.
Relevant initiatives
Related knowledge about this paper
Reproduced results (crowd-benchmarking and competitions)
Artifact and reproducibility checklists
- ACM/cTuning artifact appendix and reproducibility checklist
- NeurIPS reproducibility checklist
- SIGPLAN's checklist for empirical evaluation
- Collective Knowledge (organizing research projects based on FAIR principles)