Recent works in Computer Vision and Machine Learning have shown the benefits of measuring Wasserstein distances between histograms with $N$ bins, by solving a classical transportation problem on (very large) complete bipartite graphs with $N$ nodes and $N^2$ edges.We show how to approximate the original transportation problem by an uncapacitated min cost flow problem on a reduced flow network of size $O(N)$. For $L^1$ and the sup norm as ground distances our our approach provides an exact optimal solution. When the ground distance is the $L^2$ norm we derive a quantitative estimate on the error between optimal and approximate solutions. We numerically show the benefits of our approach by computing Wasserstein distances of order one on a set of grey scale images used as benchmarks in the literature. On these types of instances, our approach is competitive with stateoftheart optimal transport algorithms.We also show how simple Linear Programming models permit to compute Wasserstein Barycenter of a large set of twodimensional images. Wasserstein Barycenters were recently introduced to mathematically generalize the concept of averaging a set of points, to the concept of averaging a set of cloud of points (measures), such as, for instance, twodimensional images.We numerically show the strength of the proposed methods by computing the barycenters of all digits included in the classical MNIST dataset.Time permitting we show some analogous methods and results for KantorovichWasserstein of order 2. The talk is based on some works in collaboration with G. Auricchio, S. Gualandi, M. Veneroni (Universita' di Pavia).
You are here
Efficient computation of KantorovichWasserstein distances and Wasserstein Barycenters between ddimensional histograms
Research Group:
Federico Bassetti
Institution:
Politecnico di Milano
Location:
A128
Schedule:
Wednesday, January 23, 2019  14:00
Abstract:
Openings
 Public Calls for Professors
 Temporary Professors/Researchers/Visiting Professors
 SISSA Mathematical Fellowships
 Marie SklodowskaCurie Grants
 Post Doctoral Fellowships
 PhD Scolarships
 SIS Fellowships
 Undergraduate Fellowships
 Postgraduate Fellowships
 MSc in Mathematics
 MSc in Data Science and Scientific Computing (DSSC)
 Professional Master Courses
Upcoming events
 Fernando Rodriguez Villegas Hypergeometric Motives Room: Luigi Stasi Seminar Room, ICTP

Federico Bassetti
Efficient computation of KantorovichWasserstein distances and Wasserstein Barycenters between ddimensional histograms
Wednesday, January 23, 2019  14:00

John Cremona
The Lfunctions and modular forms database project
Wednesday, January 23, 2019  16:00

Flavia Santarcangelo
Isoperimetry in MCP spaces
Friday, January 25, 2019  14:00
Today's Lectures

Gianni Dal Maso
09:00 to 11:00

Nicola Gigli
11:00 to 13:00

Guido De Philippis
14:00 to 16:00

Ugo Boscain
16:00 to 18:00
Recent publications

F. Auricchio; M. Conti; A. Lefieux; S. Morganti; A. Reali; G. Rozza; A. Veneziani,

G. Cotti; B. Dubrovin; D. Guzzetti,Local moduli of semisimple Fro...

N. Giuliani; A. Mola; L. Heltai,πBEM : A flexible parallel im...

F. Salmoiraghi; A. Scardigli; H. Telib; G. Rozza,Freeform deformation, mesh mo...