Computing Wasserstein Distances with the Network Simplex Algorithm -- Talk by Stefano Gualandi Event

Event details

The computation of a measure of similarity (or dissimilarity) between pairs of objects is a crucial subproblem in several applications in Computer Vision, Computational Statistic, Probability, and Machine Learning. We present different methods to compute using the Network Simplex Algorithm the so-called “Kantorovich-Wasserstein (KW) distance” between d-dimensional histograms, considering two general cases: KW distance of order 1 and of order 2. The first contribution we present is the approximation of the KW distance of order 1 by solving an uncapacitated minimum cost flow problem defined on grid graphs of size O(N), where N is the number of bins in each histogram [1]. More precisely, when the distance among the bins of the histograms is measured with the 1-norm or the infinity-norm, our approach provides an optimal solution. When the distance between the bins is measured with the 2-norm: (i) we derive a quantitative estimate on the error between optimal and approximate solution; (ii) given the desired error, we construct a grid graph of size O(N). The second contribution we present show how to compute exactly the KW distance of order 2 between d- dimensional histograms using a (d+1)-bipartite graph with (d + 1)*N nodes and d*N^{(d+1)/d} arcs [2]. Our new formulation gives the current state-of-the-art approach to compute exactly KW distances of order 2. We show numerically the benefits of our approaches by computing the KW distance among two sets of instances: gray scale images and d-dimensional biomedical histograms. On these types of instances, our approach is competitive with state-of-the-art optimal transport algorithms. [1] On the Computation of Kantorovich-Wasserstein Distances between 2D-Histograms by Uncapacitated Minimum Cost Flows. F. Bassetti, S. Gualandi, M. Veneroni. arXiv preprint arXiv:1804.00445. [2] Computing Kantorovich-Wasserstein Distances on -dimensional histograms using -partite graphs. G. Auricchio, F. Bassetti, S. Gualandi, M. Veneroni. arXiv preprint arXiv:1805.07416. To appear in NIPS 2018.