CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishIn 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).
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
| Titolo: | On the computation of kantorovich-wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows |
| Autori: | |
| Data di pubblicazione: | 2020 |
| Rivista: | |
| 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). |
| Handle: | http://hdl.handle.net/11571/1349014 |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11571/1349014
Copyright © 2021