We are very excited to join forces with MLCommons and OctoML.ai! Contact Grigori Fursin for more details!

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.

Relevant initiatives  

Related knowledge about this paper Reproduced results (crowd-benchmarking and competitions) Artifact and reproducibility checklists Common formats for research projects and shared artifacts Reproducibility initiatives

Comments  

Please log in to add your comments!
If you notice any inapropriate content that should not be here, please report us as soon as possible and we will try to remove it within 48 hours!