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-01-01

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).
2020
Kantorovich metric
Network simplex
Transportation problem
Uncapacitated minimum cost flow problem
Wasserstein distance
File in questo prodotto:
File Dimensione Formato  
11311-1150351_Bassetti.pdf

accesso aperto

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 4.19 MB
Formato Adobe PDF
4.19 MB Adobe PDF Visualizza/Apri

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/1150351
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 10
social impact