Numerical methods for matching for teams and Wasserstein barycenters
Carlier, Guillaume1 ; Oberman, Adam2 ; Oudet, Edouard3
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.
ESAIM: Mathematical Modelling and Numerical Analysis , Optimal Transport, Tome 49 (2015) no. 6, pp. 1621-1642.

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.

Reçu le :
DOI : 10.1051/m2an/2015033
Classification : 49M29, 90C05
Mots-clés : Matching for teams, Wasserstein barycenters, duality, linear programming, numerical methods for nonsmooth convex minimization
Carlier, Guillaume 1 ; Oberman, Adam 2 ; Oudet, Edouard 3

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. 
@article{M2AN_2015__49_6_1621_0,
     author = {Carlier, Guillaume and Oberman, Adam and Oudet, Edouard},
     title = {Numerical methods for matching for teams and {Wasserstein} barycenters},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
     pages = {1621--1642},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {6},
     year = {2015},
     doi = {10.1051/m2an/2015033},
     mrnumber = {3423268},
     zbl = {1331.49042},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/m2an/2015033/}
}
TY  - JOUR
AU  - Carlier, Guillaume
AU  - Oberman, Adam
AU  - Oudet, Edouard
TI  - Numerical methods for matching for teams and Wasserstein barycenters
JO  - ESAIM: Mathematical Modelling and Numerical Analysis 
PY  - 2015
SP  - 1621
EP  - 1642
VL  - 49
IS  - 6
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/m2an/2015033/
DO  - 10.1051/m2an/2015033
LA  - en
ID  - M2AN_2015__49_6_1621_0
ER  - 
%0 Journal Article
%A Carlier, Guillaume
%A Oberman, Adam
%A Oudet, Edouard
%T Numerical methods for matching for teams and Wasserstein barycenters
%J ESAIM: Mathematical Modelling and Numerical Analysis 
%D 2015
%P 1621-1642
%V 49
%N 6
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/m2an/2015033/
%R 10.1051/m2an/2015033
%G en
%F M2AN_2015__49_6_1621_0
Carlier, Guillaume; Oberman, Adam; Oudet, Edouard. Numerical methods for matching for teams and Wasserstein barycenters. ESAIM: Mathematical Modelling and Numerical Analysis , Optimal Transport, Tome 49 (2015) no. 6, pp. 1621-1642. doi : 10.1051/m2an/2015033. http://www.numdam.org/articles/10.1051/m2an/2015033/

M. Agueh and G. Carlier, Barycenters in the wasserstein space. SIAM J. Math. Anal. 43 (2011) 904–924. | DOI | MR | Zbl

J.-D. Benamou and Y. Brenier, A computational fluid mechanics solution to the Monge−Kantorovich mass transfer problem. Numer. Math. 84 (2000) 375–393. | DOI | MR | Zbl

J.-D. Benamou, B.D. Froese and A.M. Oberman, Numerical solution of the optimal transportation problem using the Monge–Ampère equation. J. Comput. Phys. 260 (2014) 107–126. | DOI | MR | Zbl

J. Bigot and T. Klein, Consistent estimation of a population barycenter in the wasserstein space. Preprint arXiv:1212.2562 (2012).

Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions. Commun. Pure Appl. Math. 44 (1991) 375–417. | DOI | MR | Zbl

J.V. Burke, A.S. Lewis and M.L. Overton, A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM J. Optim. 15 (2005) 751–779. | DOI | MR | Zbl

G. Carlier and I. Ekeland, Matching for teams. Economic Theory 42 (2010) 397–418. | DOI | MR | Zbl

M. Cuturi and A. Doucet, Fast computation of Wasserstein barycenters. Proc. of the 31st International Conference on Machine Learning – ICML-14 (2014) 685–693.

B. Galerne, Y. Gousseau and J.-M. Morel, Random phase textures: theory and synthesis. IEEE Trans. Image Process. 20 (2011) 257–267. | DOI | MR | Zbl

W. Gangbo and A. Swiech, Optimal maps for the multidimensional Monge-Kantorovich problem. Commun. Pure Appl. Math. 51 (1998) 23–45. | DOI | MR | Zbl

N. Ghoussoub and B. Maurey, Remarks on multi-marginals symmetric Monge-Kantorovich problems. Discrete Cont. Dyn. Syst. 34 (2014) 1465–1480. | DOI | MR | Zbl

N. Ghoussoub and A. Moameni, A self-dual polar factorization for vector fields. Commun. Pure Appl. Math. 66 (2013) 905–933. | DOI | MR | Zbl

M. Grant and S. Boyd, Graph implementations for nonsmooth convex programs. In Recent Advances in Learning and Control. Edited by V. Blondel, S. Boyd and H. Kimura. Lect. Notes Control Inform. Sci. Springer-Verlag Limited (2008) 95–110. Available on http://stanford.edu/˜boyd/graph˙dcp.html. | MR | Zbl

M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming. Version 1.21. Available on http://cvxr.com/cvx (2010).

N. Haarala, K. Miettinen and M.M. Mäkelä, Globally convergent limited memory bundle method for large-scale nonsmooth optimization. Math. Program. 109 (2007) 181–205. | DOI | MR | Zbl

J.B. Hiriart-Urruty and C. Lemaréchal, Vol. 1 of Convex analysis and minimization algorithms. Springer (1996).

C. Lemaréchal, R. Mifflin, Nonsmooth optimization. In Proc. of IIASA: International Institute for Applied Systems Analysis. Pergamon Press (1978). | MR | Zbl

A.S. Lewis and M.L. Overton, Behavior of BFGS with an exact line search on nonsmooth examples. Technical report. Optimization Online (2008b). http://www.optimization-online.org/DB˙FILE/2008/12/2173.pdf. SIAM J. Optim. (Submitted).

A.S. Lewis and M.L. Overton, Nonsmooth optimization via BFGS. SIAM J. Optim. (Submitted).

R.J. Mccann, A convexity principle for interacting gases. Adv. Math. 128 (1997) 153–179. | DOI | MR | Zbl

Q. Mérigot and É. Oudet, Discrete optimal transport: complexity, geometry and applications. Preprint (2012). | MR

N. Papadakis, G. Peyré and E. Oudet, Optimal transport with proximal splitting. SIAM J. Imag. Sci. 7 (2014) 212–238. | DOI | MR | Zbl

B. Pass, Multi-marginal optimal transport and multi-agent matching problems: uniqueness and structure of solutions. Discrete Contin. Dyn. Syst. 34 (2014) 1623–1639. | DOI | MR | Zbl

B. Pass, On the local structure of optimal measures in the multi-marginal optimal transportation problem. Calc. Var. Partial Differ. Equ. 43 (2012) 529–536. | DOI | MR | Zbl

M.J.D. Powell, Some global convergence properties of a variable metric algorithm for minimization without exact line searches. Nonlin. Progr. 9 (1976) 53–72. | MR | Zbl

J. Rabin, G. Peyré, J. Delon and M. Bernot, Wasserstein barycenter and its application to texture mixing. In Scale Space and Variational Methods in Computer Vision. Springer. (2012) 435–446.

A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Vol. 24. Springer (2003). | MR | Zbl

C. Villani, Topics in Optimal Transportation. Vol. 58. AMS Bookstore (2003). | MR | Zbl

C. Villani, Optimal Transport: Old and New. Vol. 338. Springer (2009). | MR | Zbl

Cité par Sources :