Simple Approximative Algorithms for Free-Support Wasserstein Barycenters
share
Computing Wasserstein barycenters of discrete measures has recently attracted considerable attention due to its wide variety of applications in data science. In general, this problem is NP-hard, calling for practical approximative algorithms. In this paper, we analyze two straightforward algorithms for approximating barycenters, which produce sparse support solutions and show promising numerical results. These algorithms require N-1 and N(N-1)/2 standard two-marginal OT computations between the N input measures, respectively, so that they are fast, in particular the first algorithm, as well as memory-efficient and easy to implement. Further, they can be used with any OT solver as a black box. Based on relations of the barycenter problem to the multi-marginal optimal transport problem, which are interesting on their own, we prove sharp upper bounds for the relative approximation error. In the second algorithm, this upper bound can be evaluated specifically for the given problem, which always guaranteed an error of at most a few percent in our numerical experiments.
READ FULL TEXT