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 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 bio medical histograms. On these types of instances, our approach is competitive with state-of-the-art optimal transport algorithms.

Computing Kantorovich-Wasserstein Distances on d-dimensional histograms using (d + 1)-partite graphs

Auricchio G.;Gualandi S.;Veneroni M.;Bassetti F.
2018-01-01

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 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 bio medical histograms. On these types of instances, our approach is competitive with state-of-the-art optimal transport algorithms.
2018
Advances in Neural Information Processing Systems
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1091135
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 0
social impact