Primal Heuristics for Wasserstein Barycenters

This paper presents primal heuristics for the computation of Wasserstein Barycenters of a given set of discrete probability measures. The computation of a Wasserstein Barycenter is formulated as an optimization problem over the space of discrete probability measures. In practice, the barycenter is a discrete probability measure which minimizes the sum of the pairwise Wasserstein distances between the barycenter itself and each input measure. While this problem can be formulated using Linear Programming techniques, it remains a challenging problem due to the size of real-life instances. In this paper, we propose simple but efficient primal heuristics, which exploit the properties of the optimal plan obtained while computing the Wasserstein Distance between a pair of probability measures. In order to evaluate the proposed primal heuristics, we have performed extensive computational tests using random Gaussian distributions, the MNIST handwritten digit dataset, and the Fashion MNIST dataset introduced by Zalando. We also used Translated MNIST, a modification of MNIST which contains original images, rescaled randomly and translated into a larger image. We compare the barycenters computed by our heuristics with the exact solutions obtained with a commercial Linear Programming solver, and with a state-of-the-art algorithm based on Gaussian convolutions. Our results show that the proposed heuristics yield in very short run time and an average optimality gap significantly smaller than 1%.