Scaling algorithms for unbalanced optimal transport problems

Chizat, Lénaïc; Peyré, Gabriel; Schmitzer, Bernhard; Vialard, François-Xavier

doi:10.1090/mcom/3303

Scaling algorithms for unbalanced optimal transport problems
HTML articles powered by AMS MathViewer

by Lénaïc Chizat, Gabriel Peyré, Bernhard Schmitzer and François-Xavier Vialard;

Math. Comp. 87 (2018), 2563-2609

DOI: https://doi.org/10.1090/mcom/3303

Published electronically: February 6, 2018

PDF | Request permission

Abstract:

This article introduces a new class of fast algorithms to approximate variational problems involving unbalanced optimal transport. While classical optimal transport considers only normalized probability distributions, it is important for many applications to be able to compute some sort of relaxed transportation between arbitrary positive measures. A generic class of such “unbalanced” optimal transport problems has been recently proposed by several authors. In this paper, we show how to extend the now classical entropic regularization scheme to these unbalanced problems. This gives rise to fast, highly parallelizable algorithms that operate by performing only diagonal scaling (i.e., pointwise multiplications) of the transportation couplings. They are generalizations of the celebrated Sinkhorn algorithm. We show how these methods can be used to solve unbalanced transport, unbalanced gradient flows, and to compute unbalanced barycenters. We showcase applications to 2-D shape modification, color transfer, and growth models.

References

Martial Agueh and Guillaume Carlier, Barycenters in the Wasserstein space, SIAM J. Math. Anal. 43 (2011), no. 2, 904–924. MR 2801182, DOI 10.1137/100805741
Louis-Philippe Saumier, Boualem Khouider, and Martial Agueh, Optimal transport for particle image velocimetry, Commun. Math. Sci. 13 (2015), no. 1, 269–296. MR 3238148, DOI 10.4310/CMS.2015.v13.n1.a13
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré, Gradient flows in metric spaces and in the space of probability measures, 2nd ed., Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2008. MR 2401600
F. Aurenhammer, F. Hoffmann, and B. Aronov, Minkowski-type theorems and least-squares clustering, Algorithmica 20 (1998), no. 1, 61–76. MR 1483422, DOI 10.1007/PL00009187
Heinz H. Bauschke and Adrian S. Lewis, Dykstra’s algorithm with Bregman projections: a convergence proof, Optimization 48 (2000), no. 4, 409–427. MR 1811866, DOI 10.1080/02331930008844513
Amir Beck, On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes, SIAM J. Optim. 25 (2015), no. 1, 185–209. MR 3300410, DOI 10.1137/13094829X
Jean-David Benamou and Yann Brenier, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numer. Math. 84 (2000), no. 3, 375–393. MR 1738163, DOI 10.1007/s002110050002
Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré, Iterative Bregman projections for regularized transportation problems, SIAM J. Sci. Comput. 37 (2015), no. 2, A1111–A1138. MR 3340204, DOI 10.1137/141000439
Jean-David Benamou, Guillaume Carlier, Quentin Mérigot, and Édouard Oudet, Discretization of functionals involving the Monge-Ampère operator, Numer. Math. 134 (2016), no. 3, 611–636. MR 3555350, DOI 10.1007/s00211-015-0781-y
Jean-David Benamou, Guillaume Carlier, and Maxime Laborde, An augmented lagrangian approach to wasserstein gradient flows and applications, (2015).
Dimitri P. Bertsekas and David A. Castañon, The auction algorithm for the transportation problem, Ann. Oper. Res. 20 (1989), no. 1-4, 67–96. Network optimization and applications. MR 1015946, DOI 10.1007/BF02216923
N. Bonneel, M. van de Panne, S. Paris, and W. Heidrich, Displacement interpolation using Lagrangian mass transport, ACM Transactions on Graphics (SIGGRAPH ASIA’11) 30 (2011), no. 6.
J. M. Borwein and A. S. Lewis, Duality relationships for entropy-like minimization problems, SIAM J. Control Optim. 29 (1991), no. 2, 325–338. MR 1092730, DOI 10.1137/0329017
L. M. Brègman, A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming, Ž. Vyčisl. Mat i Mat. Fiz. 7 (1967), 620–631 (Russian). MR 215617
Yann Brenier, Polar factorization and monotone rearrangement of vector-valued functions, Comm. Pure Appl. Math. 44 (1991), no. 4, 375–417. MR 1100809, DOI 10.1002/cpa.3160440402
Martin Burger, José A. Carrillo, and Marie-Therese Wolfram, A mixed finite element method for nonlinear diffusion equations, Kinet. Relat. Models 3 (2010), no. 1, 59–83. MR 2580954, DOI 10.3934/krm.2010.3.59
Martin Burger, Marzena Franek, and Carola-Bibiane Schönlieb, Regularized regression and density estimation based on optimal transport, Appl. Math. Res. Express. AMRX 2 (2012), 209–253. MR 2982774, DOI 10.1093/amrx/abs007
Rainer Burkard, Mauro Dell’Amico, and Silvano Martello, Assignment problems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2009. MR 2488749, DOI 10.1137/1.9780898717754
Luis A. Caffarelli and Robert J. McCann, Free boundaries in optimal transport and Monge-Ampère obstacle problems, Ann. of Math. (2) 171 (2010), no. 2, 673–730. MR 2630054, DOI 10.4007/annals.2010.171.673
Guillaume Carlier, Vincent Duval, Gabriel Peyré, and Bernhard Schmitzer, Convergence of entropic schemes for optimal transport and gradient flows, SIAM J. Math. Anal. 49 (2017), no. 2, 1385–1418. MR 3635459, DOI 10.1137/15M1050264
José A. Carrillo, Alina Chertock, and Yanghong Huang, A finite-volume method for nonlinear nonlocal equations with a gradient flow structure, Commun. Comput. Phys. 17 (2015), no. 1, 233–258. MR 3372289, DOI 10.4208/cicp.160214.010814a
Yair Censor and Simeon Reich, The Dykstra algorithm with Bregman projections, Commun. Appl. Anal. 2 (1998), no. 3, 407–419. MR 1626725
Antonin Chambolle and Thomas Pock, On the ergodic convergence rates of a first-order primal-dual algorithm, Math. Program. 159 (2016), no. 1-2, Ser. A, 253–287. MR 3535925, DOI 10.1007/s10107-015-0957-3
L. Chizat, G. Peyré, B. Schmitzer, and F-X. Vialard, Unbalanced optimal transport: Geometry and kantorovich formulation, Preprint 1508.05216, Arxiv, 2015.
L. Chizat, B. Schmitzer, G. Peyré, and F-X. Vialard, An interpolating distance between optimal transport and Fischer-Rao, Preprint 1506.06430, Arxiv, 2015.
M. Cuturi, Sinkhorn distances: Lightspeed computation of optimal transport, Advances in Neural Information Processing Systems (NIPS) 26, 2013, pp. 2292–2300.
M. Cuturi and A. Doucet, Fast computation of Wasserstein barycenters, Proceedings of ICML, vol. 32, 2014.
J. Delon, Movie and video scale-time equalization application to flicker reduction, IEEE Transactions on Image Processing 15 (2006), no. 1, 241–248.
W. Edwards Deming and Frederick F. Stephan, On a least squares adjustment of a sampled frequency table when the expected marginal totals are known, Ann. Math. Statistics 11 (1940), 427–444. MR 3527, DOI 10.1214/aoms/1177731829
Richard L. Dykstra, An algorithm for restricted least squares regression, J. Amer. Statist. Assoc. 78 (1983), no. 384, 837–842. MR 727568
Jonathan Eckstein, Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming, Math. Oper. Res. 18 (1993), no. 1, 202–226. MR 1250114, DOI 10.1287/moor.18.1.202
Jalal M. Fadili and Gabriel Peyré, Total variation projection with first order schemes, IEEE Trans. Image Process. 20 (2011), no. 3, 657–669. MR 2799177, DOI 10.1109/TIP.2010.2072512
Alessio Figalli, The optimal partial transport problem, Arch. Ration. Mech. Anal. 195 (2010), no. 2, 533–560. MR 2592287, DOI 10.1007/s00205-008-0212-7
Joel Franklin and Jens Lorenz, On the scaling of multidimensional matrices, Linear Algebra Appl. 114/115 (1989), 717–735. MR 986904, DOI 10.1016/0024-3795(89)90490-4
C. Frogner, C. Zhang, H. Mobahi, M. Araya-Polo, and T. Poggio, Learning with a Wasserstein loss, Preprint 1506.05439, Arxiv, 2015.
A. Galichon and B. Salanié, Matching with trade-offs: Revealed preferences over competing characteristics, Tech. report, Preprint SSRN-1487307, 2009.
Thomas O. Gallouët and Léonard Monsaingeon, A JKO splitting scheme for Kantorovich-Fisher-Rao gradient flows, SIAM J. Math. Anal. 49 (2017), no. 2, 1100–1130. MR 3628313, DOI 10.1137/16M106666X
Leonid G. Hanin, Kantorovich-Rubinstein norm and its application in the theory of Lipschitz spaces, Proc. Amer. Math. Soc. 115 (1992), no. 2, 345–352. MR 1097344, DOI 10.1090/S0002-9939-1992-1097344-5
Richard Jordan, David Kinderlehrer, and Felix Otto, The variational formulation of the Fokker-Planck equation, SIAM J. Math. Anal. 29 (1998), no. 1, 1–17. MR 1617171, DOI 10.1137/S0036141096303359
L. Kantorovitch, On the translocation of masses, C. R. (Doklady) Acad. Sci. URSS (N.S.) 37 (1942), 199–201. MR 9619
S. Kondratyev, L. Monsaingeon, and D. Vorotnikov, A new optimal transport distance on the space of finite Radon measures, Tech. report, Pre-print, 2015.
J.J. Kosowsky and A.L. Yuille, The invisible hand algorithm: Solving the assignment problem with statistical physics, Neural Networks 7 (1994), no. 3, 477–490.
Maxime Laborde, On some non linear evolution systems which are perturbations of wasserstein gradient flows, arXiv preprint arXiv:1506.00126 (2015).
Christian Léonard, From the Schrödinger problem to the Monge-Kantorovich problem, J. Funct. Anal. 262 (2012), no. 4, 1879–1920. MR 2873864, DOI 10.1016/j.jfa.2011.11.026
Christian Léonard, A survey of the Schrödinger problem and some of its connections with optimal transport, Discrete Contin. Dyn. Syst. 34 (2014), no. 4, 1533–1574. MR 3121631, DOI 10.3934/dcds.2014.34.1533
Bruno Lévy, A numerical algorithm for $L_2$ semi-discrete optimal transport in 3D, ESAIM Math. Model. Numer. Anal. 49 (2015), no. 6, 1693–1715. MR 3423272, DOI 10.1051/m2an/2015055
Matthias Liero, Alexander Mielke, and Giuseppe Savaré, Optimal transport in competition with reaction: the Hellinger-Kantorovich distance and geodesic curves, SIAM J. Math. Anal. 48 (2016), no. 4, 2869–2911. MR 3542003, DOI 10.1137/15M1041420
Matthias Liero, Alexander Mielke, and Giuseppe Savaré, Optimal transport in competition with reaction: the Hellinger-Kantorovich distance and geodesic curves, ArXiv e-prints (2015).
Jan Maas, Martin Rumpf, Carola Schönlieb, and Stefan Simon, A generalized model for optimal transport of images including dissipation and density modulation, ESAIM Math. Model. Numer. Anal. 49 (2015), no. 6, 1745–1769. MR 3423274, DOI 10.1051/m2an/2015043
Bertrand Maury, Aude Roudneff-Chupin, and Filippo Santambrogio, A macroscopic crowd motion model of gradient flow type, Math. Models Methods Appl. Sci. 20 (2010), no. 10, 1787–1821. MR 2735914, DOI 10.1142/S0218202510004799
Bertrand Maury, Aude Roudneff-Chupin, Filippo Santambrogio, and Juliette Venel, Handling congestion in crowd motion modeling, Netw. Heterog. Media 6 (2011), no. 3, 485–519. MR 2826756, DOI 10.3934/nhm.2011.6.485
Q. Mérigot, A multiscale approach to optimal transport, Comput. Graph. Forum 30 (2011), no. 5, 1583–1592.
G. Monge, Mémoire sur la théorie des déblais et des remblais, Histoire de l’Académie Royale des Sciences (1781), 666–704.
Q. V. Nguyen, Forward-backward splitting with Bregman distances, arXiv:1505.05198 (2015).
Felix Otto, The geometry of dissipative evolution equations: the porous medium equation, Comm. Partial Differential Equations 26 (2001), no. 1-2, 101–174. MR 1842429, DOI 10.1081/PDE-100002243
Nicolas Papadakis, Gabriel Peyré, and Edouard Oudet, Optimal transport with proximal splitting, SIAM J. Imaging Sci. 7 (2014), no. 1, 212–238. MR 3158785, DOI 10.1137/130920058
Benoît Perthame, Fernando Quirós, and Juan Luis Vázquez, The Hele-Shaw asymptotics for mechanical models of tumor growth, Arch. Ration. Mech. Anal. 212 (2014), no. 1, 93–127. MR 3162474, DOI 10.1007/s00205-013-0704-y
Gabriel Peyré, Entropic approximation of Wasserstein gradient flows, SIAM J. Imaging Sci. 8 (2015), no. 4, 2323–2351. MR 3413589, DOI 10.1137/15M1010087
Benedetto Piccoli and Francesco Rossi, Generalized Wasserstein distance and its application to transport equations with source, Arch. Ration. Mech. Anal. 211 (2014), no. 1, 335–358. MR 3182483, DOI 10.1007/s00205-013-0669-x
F. Pitié, A.C. Kokaram, and R. Dahyot, Automated colour grading using colour distribution transfer, Computer Vision and Image Understanding 107 (2007), no. 1, 123–137.
Julien Rabin and Nicolas Papadakis, Convex color image segmentation with optimal transport distances, Scale space and variational methods in computer vision, Lecture Notes in Comput. Sci., vol. 9087, Springer, Cham, 2015, pp. 256–269. MR 3394935, DOI 10.1007/978-3-319-18461-6_{2}1
R. Tyrrell Rockafellar, Duality and stability in extremum problems involving convex functions, Pacific J. Math. 21 (1967), 167–187. MR 211759
R. T. Rockafellar, Integrals which are convex functionals, Pacific J. Math. 24 (1968), 525–539. MR 236689
R. T. Rockafellar, Integral functionals, normal integrands and measurable selections, Nonlinear operators and the calculus of variations, Springer, 1976, pp. 157–207.
R.T. Rockafellar and R. J-B. Wets, Variational analysis, vol. 317, Springer Science & Business Media, 2009.
Y. Rubner, C. Tomasi, and L.J. Guibas, The earth mover’s distance as a metric for image retrieval, International Journal of Computer Vision 40 (2000), no. 2.
Filippo Santambrogio, Optimal transport for applied mathematicians, Progress in Nonlinear Differential Equations and their Applications, vol. 87, Birkhäuser/Springer, Cham, 2015. Calculus of variations, PDEs, and modeling. MR 3409718, DOI 10.1007/978-3-319-20828-2
Bernhard Schmitzer, A sparse multiscale algorithm for dense optimal transport, J. Math. Imaging Vision 56 (2016), no. 2, 238–259. MR 3535020, DOI 10.1007/s10851-016-0653-9
Bernhard Schmitzer, Stabilized sparse scaling algorithms for entropy regularized transport problems, https://arxiv.org/abs/1610.06519, 2016.
E. Schrödinger, Über die Umkehrung der Naturgesetze, Sitzungsberichte Preuss. Akad. Wiss. Berlin. Phys. Math. 144 (1931), 144–153.
Meisam Sharify, Stéphane Gaubert, and Laura Grigori, Solution of the optimal assignment problem by diagonal scaling algorithms, arXiv preprint arXiv:1104.3830 (2011).
Richard Sinkhorn, A relationship between arbitrary positive matrices and doubly stochastic matrices, Ann. Math. Statist. 35 (1964), 876–879. MR 161868, DOI 10.1214/aoms/1177703591
J. Solomon, F. de Goes, G. Peyré, M. Cuturi, A. Butscher, A. Nguyen, T. Du, and L. Guibas, Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains, ACM Transactions on Graphics (Proc. SIGGRAPH 2015) 34 (2015), no. 4, 66:1–66:11.
J. Solomon, R.M. Rustamov, L. Guibas, and A. Butscher, Wasserstein propagation for semisupervised learning, Proc. ICML 2014, 2014.
A. C. Thompson, On certain contraction mappings in a partially ordered vector space, Proc. Amer. Math. Soc. 14 (1963), 438–443. MR 149237, DOI 10.1090/S0002-9939-1963-0149237-7
Cédric Villani, Topics in optimal transportation, Graduate Studies in Mathematics, vol. 58, American Mathematical Society, Providence, RI, 2003. MR 1964483, DOI 10.1090/gsm/058
Cédric Villani, Optimal transport, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 338, Springer-Verlag, Berlin, 2009. Old and new. MR 2459454, DOI 10.1007/978-3-540-71050-9
H. Wang and A. Banerjee, Bregman alternating direction method of multipliers, preprint arXiv:1306.3203 (2014).
Jonathan Zinsl and Daniel Matthes, Transport distances and geodesic convexity for systems of degenerate diffusion equations, Calc. Var. Partial Differential Equations 54 (2015), no. 4, 3397–3438. MR 3426082, DOI 10.1007/s00526-015-0909-z