zbMATH — the first resource for mathematics

Computing Wasserstein barycenters via linear programming. (English) Zbl 07116704
Rousseau, Louis-Martin (ed.) et al., Integration of constraint programming, artificial intelligence, and operations research. 16th international conference, CPAIOR 2019, Thessaloniki, Greece, June 4–7, 2019. Proceedings. Cham: Springer (ISBN 978-3-030-19211-2/pbk; 978-3-030-19212-9/ebook). Lecture Notes in Computer Science 11494, 355-363 (2019).
Summary: This paper presents a family of generative Linear Programming models that permit to compute the exact 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 clouds of points, such as, for instance, two-dimensional images. In Machine Learning terms, the Wasserstein Barycenter problem is a generative constrained optimization problem, since the values of the decision variables of the optimal solution give a new image that represents the “average” of the input images. Unfortunately, in the recent literature, Linear Programming is repeatedly described as an inefficient method to compute Wasserstein Barycenters. In this paper, we aim at disproving such claim. Our family of Linear Programming models rely on different types of Kantorovich-Wasserstein distances used to compute a barycenter, and they are efficiently solved with a modern commercial Linear Programming solver. We numerically show the strength of the proposed models by computing and plotting the barycenters of all digits included in the classical MNIST dataset.
For the entire collection see [Zbl 1410.68020].
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
Full Text: DOI