Numerical methods for matching for teams and Wasserstein barycenters
1 CEREMADE, UMR CNRS 7534, Université Paris IX Dauphine, Pl. de
Lattre de Tassigny, 75775 Paris cedex 16, France.
2 Department of Mathematics and Statistics, McGill University, 805 Sherbrooke Street West, Montreal, Canada.
3 Laboratoire Jean Kuntzmann, Université Joseph Fourier, Tour IRMA, BP 53 51, rue des Mathématiques 38041 Grenoble cedex 9, France.
Equilibrium multi-population matching (matching for teams) is a problem from mathematical economics which is related to multi-marginal optimal transport. A special but important case is the Wasserstein barycenter problem, which has applications in image processing and statistics. Two algorithms are presented: a linear programming algorithm and an efficient nonsmooth optimization algorithm, which applies in the case of the Wasserstein barycenters. The measures are approximated by discrete measures: convergence of the approximation is proved. Numerical results are presented which illustrate the efficiency of the algorithms.
Mathematics Subject Classification: 49M29 / 90C05
Key words: Matching for teams / Wasserstein barycenters / duality / linear programming / numerical methods for nonsmooth convex minimization
© EDP Sciences, SMAI 2015