Computing Wasserstein Barycenters via Linear Programming

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.