Mathematics

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 state-of-the-art optimal transport algorithms.We also show how  simple Linear Programming models permit to compute Wasserstein Barycenter of a large set of two-dimensional 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, two-dimensional 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 Kantorovich-Wasserstein of order 2.  The talk is based on some works in collaboration with G. Auricchio, S. Gualandi, M. Veneroni (Universita' di Pavia).