Numerical resolution of an “unbalanced” mass transport problem

Benamou, Jean-David

ESAIM: Modélisation mathématique et analyse numérique, Tome 37 (2003) no. 5, pp. 851-868

We introduce a modification of the Monge-Kantorovitch problem of exponent 2 which accommodates non balanced initial and final densities. The augmented lagrangian numerical method introduced in [6] is adapted to this “unbalanced” problem. We illustrate the usability of this method on an idealized error estimation problem in meteorology.

Classification : 35J60, 65K10, 78A05, 90B99
Keywords: Monge-Kantorovitch problem, Wasserstein distance, augmented lagrangian method

[1] M. Balinski, A competitive (dual) simplex method for the assignment problem. Math. Program. 34 (1986) 125-141. | Zbl

[2] F. Barthe, On a reverse form of the Brascamp-Lieb inequality. Invent. Math. 134 (1998) 335-361. | Zbl

[3] J.-D. Benamou, A domain decomposition method for the polar factorization of vector valued mappings. SIAM J. Numer. Anal. 32 (1995) 1808-1838. | Zbl

[4] J.D. Benamou and Y. Brenier, Numerical resolution on a massively parallel computer of a test problem in meteorology using a domain decomposition algorithm, in First European conference in computational fluid dynamics. North Holland (1992).

[5] J.D. Benamou and Y. Brenier, Weak existence for the semigeostrophic equations formulated as a coupled Monge-Ampère/transport problem. SIAM J. Appl. Math. 58 (1998) 1450-1461. | Zbl

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

[7] J.D. Benamou and Y. Brenier, Mixed $L^2$/Wasserstein Optimal Mapping Between Prescribed Densities Functions (submitted). | Zbl

[8] J.D. Benamou, Y. Brenier and K. Guittet, Numerical resolution of a multiphasic optimal mass transport problem. Tech. Report INRIA RR-4022.

[9] G. Boucjitte, G. Buttazzo and P. Seppechere, Shape Optimization Solutions via Monge-Kantorovich. C. R. Acad. Sci. Paris Sér. I 324 (1997) 1185-1191. | Zbl

[10] Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions. Comm. Pure Appl. Math. 44 (1991) 375-417. | Zbl

[11] Y. Brenier, Minimal geodesics on groups of volume-preserving maps and generalized solutions of the Euler equations. Comm. Pure Appl. Math. 52 (1999) 411-452. | Zbl

[12] Y. Brenier, Extended Monge-Kantorovich theory. CIME 2001 lecture. | Zbl

[13] L.A. Caffarelli, Boundary regularity of maps with convex potentials. Comm. Pure Appl. Math. 45 (1992) 1141-1151. | Zbl

[14] L.A. Caffarelli, Boundary regularity of maps with convex potentials. II. Ann. of Math. 144 (1996) 3, 453-496. | Zbl

[15] M.J.P. Cullen, Solution to a model of a front forced by deformation. Q. J. R. Met. Soc. 109 (1983) 565-573.

[16] M.J.P. Cullen, private communication.

[17] M.J.P. Cullen and R.J. Purser, An extended Lagrangian theory of semigeostrophic frontogenesis. J. Atmopheric Sci. 41 (1984) 1477-1497.

[18] R.J. Douglas, Decomposition of weather forecast error using rearrangements of functions. (Preprint.)

[19] L.C. Evans, Partial differential equations and Monge-Kantorovich mass transfer. Lecture notes. | Zbl

[20] M. Fortin and R. Glowinski, Augmented Lagrangian methods. Applications to the numerical solution of boundary value problems. North-Holland Publishing Co. Studies in Mathematics and its Applications 15 (1983) 340. | Zbl | MR

[21] U. Frisch et al., Back to the early Universe by optimal mass transportation. Nature 417 (2002) 260-262.

[22] W. Gangbo and R.J. Mccann, The geometry of optimal transportation. Acta Math. 177 (1996) 113-161. | Zbl

[23] W. Gangbo and R.J. Mccann, Shape recognition via Wasserstein distance. Quart. Appl. Math. 58 (2000) 705-737. | Zbl

[24] K. Guittet, On the time-continuous mass transport problem and its approximation by augmented Lagrangian techniques. SIAM J. Numer. Anal. 41 (2003) 382-399. | Zbl

[25] K. Guittet, Ph.D. dissertation (2002).

[26] S. Haker, A. Tannenbaum and R. Kikinis, Mass preserving mapping and image registration. MICCAI (2001) 120-127. | Zbl

[27] R. Jonker and A. Volgenant, A shortest augmenting path algorithm for dense and sparse linear assignment problem. Computing 38 (1987) 325-340. | Zbl

[28] R. Jordan, D. Kinderlehrer and F. Otto, The variational formulation of the Fokker-Planck equation. SIAM J. Math. Anal. 29 (1998) 1-17. | Zbl

[29] T. Kaijser, Computing the Kantorovich distance for images. J. Math. Imaging Vision 9 (1998) 173-198. | Zbl

[30] L.V. Kantorovich, On the translocation of masses. C. R. (Doklady) Acad. Sci. URSS (N.S.) 37 (1942) 199-201. | Zbl

[31] D. Kinderlehrer and N. Walkington, Approximation of Parabolic Equations based upon a Wasserstein metric. ESAIM: M2AN 33 (1999) 837-852. | Zbl | Numdam

[32] S.A. Kochengin and V.I. Oliker, Determination of reflector surfaces from near-field scattering data. Inverse Problems 13 (1997) 363-373. | Zbl

[33] R.J. Mccann, Polar factorization of maps on Riemannian manifolds. Geom. Funct. Anal. 11 (2001) 589-608. | Zbl

[34] R. Menozzi, Utilisation de la distance de Wasserstein et application sismique. Rapport IUP Génie Mathématique et Informatique, Université Paris IX-Dauphine.

[35] G. Monge, Mémoire sur la théorie des déblais et des remblais. Mem. Acad. Sci. Paris (1781).

[36] F. Otto, The geometry of dissipative evolution equation: the porous medium equation. Comm. Partial Differential Equations 26 (2001) 101-174. | Zbl

[37] S.T. Rachev and L. Rüschendorf, Mass transportation problems, in Theory, Probability and its Applications, Vol. I. Springer-Verlag, New York (1998) 508. | Zbl | MR

[38] A. Shnirelman, Generalized fluid flows, their approximation and applications. Geom. Funct. Anal. 4 (1994) 586-620. | Zbl

[39] C. Villani, Topics in mass transport. Lecture notes (2000).