In this work, we present a method to compute the Kantorovich-Wasserstein distance of order 1 between a pair of two-dimensional histograms. Recent works in computer vision and machine learning have shown the benefits of measuring Wasserstein distances of order 1 between histograms with n bins by solving a classical transportation problem on very large complete bipartite graphs with n nodes and n2 edges. The main contribution of our work is to approximate the original transportation problem by an uncapacitated min cost flow problem on a reduced flow network of size O(n) that exploits the geometric structure of the cost function. More precisely, when the distance among the bin centers is measured with the 1-norm or the ∞-norm, our approach provides an optimal solution. When the distance among bins is measured with the 2-norm, (i) we derive a quantitative estimate on the error between optimal and approximate solution; (ii) given the error, we construct a reduced flow network of size O(n).

On the computation of kantorovich-wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows

Bassetti F.;Gualandi S.;Veneroni M.
2020

Abstract

In this work, we present a method to compute the Kantorovich-Wasserstein distance of order 1 between a pair of two-dimensional histograms. Recent works in computer vision and machine learning have shown the benefits of measuring Wasserstein distances of order 1 between histograms with n bins by solving a classical transportation problem on very large complete bipartite graphs with n nodes and n2 edges. The main contribution of our work is to approximate the original transportation problem by an uncapacitated min cost flow problem on a reduced flow network of size O(n) that exploits the geometric structure of the cost function. More precisely, when the distance among the bin centers is measured with the 1-norm or the ∞-norm, our approach provides an optimal solution. When the distance among bins is measured with the 2-norm, (i) we derive a quantitative estimate on the error between optimal and approximate solution; (ii) given the error, we construct a reduced flow network of size O(n).
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: http://hdl.handle.net/11571/1349014
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 6
social impact