Congestion-driven dendritic growth
DCDS Home
Multi-marginal optimal transport and multi-agent matching problems: Uniqueness and structure of solutions
April 2014, 34(4): 1605-1621. doi: 10.3934/dcds.2014.34.1605
A glimpse into the differential topology and geometry of optimal transport
Robert J. McCann 1,
Department of Mathematics, University of Toronto, Toronto ON Canada M5R 2Y4, Canada
Received July 2012 Revised November 2012 Published October 2013
This note exposes the differential topology and geometry underlying some of the basic phenomena of optimal transportation. It surveys basic questions concerning Monge maps and Kantorovich measures: existence and regularity of the former, uniqueness of the latter, and estimates for the dimension of its support, as well as the associated linear programming duality. It shows the answers to these questions concern the differential geometry and topology of the chosen transportation cost. It also establishes new connections --- some heuristic and others rigorous --- based on the properties of the cross-difference of this cost, and its Taylor expansion at the diagonal.
Keywords: mean., Monge-Kantorovich, curvature, Optimal transport, optimal maps, Ricci, pseudo-Riemannian, regularity, Monge-Ampère type, sectional.
Mathematics Subject Classification: Primary: 49N60, 58E30; Secondary: 53C50, 90B06, 90C08, 91B3.
Citation: Robert J. McCann. A glimpse into the differential topology and geometry of optimal transport. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1605-1621. doi: 10.3934/dcds.2014.34.1605
N. Ahmad, "The Geometry of Shape Recognition Via a Monge-Kantorovich Optimal Transport Problem,'', PhD thesis, (2004). Google Scholar
N. Ahmad, H. K. Kim and R.J. McCann, Optimal transportation, topology and uniqueness,, Bull. Math. Sci., 1 (2011), 13. doi: 10.1007/s13373-011-0002-7. Google Scholar
G. Alberti and L. Ambrosio, A geometrical approach to monotone functions in $\mathbbR^n$,, Math. Z., 230 (1999), 259. doi: 10.1007/PL00004691. Google Scholar
L. Ambrosio, Lecture notes on optimal transport problems,, in, 1812 (2003), 1. doi: 10.1007/978-3-540-39189-0_1. Google Scholar
L. A. Ambrosio and N. Gigli, A user's guide to optimal transport,, Preprint., (). doi: 10.1007/978-3-642-32160-3_1. Google Scholar
J.-D. Benamou and Y. Brenier, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem,, Numer. Math., 84 (2000), 375. doi: 10.1007/s002110050002. Google Scholar
J.-P. Bourguignon, Ricci curvature and measures,, Japan. J. Math., 4 (2009), 27. doi: 10.1007/s11537-009-0855-7. Google Scholar
Y. Brenier, Décomposition polaire et réarrangement monotone des champs de vecteurs, (French) [Polar decomposition and monotone rearrangement of vector fields], C.R. Acad. Sci. Paris Sér. I Math., 305 (1987), 805. Google Scholar
Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions,, Comm. Pure Appl. Math., 44 (1991), 375. doi: 10.1002/cpa.3160440402. Google Scholar
L. A. Caffarelli, The regularity of mappings with a convex potential,, J. Amer. Math. Soc., 5 (1992), 99. doi: 10.1090/S0894-0347-1992-1124980-8. Google Scholar
L. A. Caffarelli, Boundary regularity of maps with convex potentials - II,, Ann. of Math. (2), 144 (1996), 453. doi: 10.2307/2118564. Google Scholar
L. A. Caffarelli, M. Feldman and R. J. McCann, Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs,, J. Amer. Math. Soc., 15 (2002), 1. doi: 10.1090/S0894-0347-01-00376-9. Google Scholar
T. Champion and L. De Pascale, The Monge problem in $\mathbbR^d$,, Duke Math. J., 157 (2011), 551. doi: 10.1215/00127094-1272939. Google Scholar
P.-A. Chiappori, R. J. McCann and L. Nesheim, Hedonic price equilibria, stable matching and optimal transport: Equivalence, topology and uniqueness,, Econom. Theory, 42 (2010), 317. doi: 10.1007/s00199-009-0455-z. Google Scholar
D. Cordero-Erausquin, R. J. McCann and M. Schmuckenschläger, A Riemannian interpolation inequality à la Borell, Brascamp and Lieb,, Invent. Math., 146 (2001), 219. doi: 10.1007/s002220100160. Google Scholar
M. J. P Cullen and R. J. Purser, An extended Lagrangian model of semi-geostrophic frontogenesis,, J. Atmos. Sci., 41 (1984), 1477. doi: 10.1175/1520-0469(1984)041<1477:AELTOS>2.0.CO;2. Google Scholar
P. Delanoë, Classical solvability in dimension two of the second boundary-value problem associated with the Monge-Ampère operator,, Ann. Inst. H. Poincarè Anal. Non Linèaire, 8 (1991), 443. doi: 10.1016/j.anihpc.2007.03.001. Google Scholar
P. Delanoë and Y. Ge, Regularity of optimal transportation maps on compact, locally nearly spherical, manifolds,, J. Reine Angew. Math., 646 (2010), 65. doi: 10.1515/CRELLE.2010.066. Google Scholar
P. Delanoë and F. Rouvière, Positively curved Riemannian locally symmetric spaces are positively square distance curved,, Canad. J. Math. 65 (2013), 65 (2013), 757. doi: 10.4153/CJM-2012-015-1. Google Scholar
R. M. Dudley, "Probabilities and Metrics - Convergence of Laws on Metric Spaces, with A View to Statistical Testing,'', Lecture Notes Series, (1976). Google Scholar
L. C. Evans and W. Gangbo, Differential equations methods for the Monge-Kantorovich mass transfer problem,, Mem. Amer. Math. Soc., 137 (1999), 1. doi: 10.1090/memo/0653. Google Scholar
M. Feldman and R.J. McCann, Uniqueness and transport density in Monge's transportation problem,, Calc. Var. Partial Differential Equations, 15 (2002), 81. doi: 10.1007/s005260100119. Google Scholar
A. Figalli, Regularity properties of optimal maps between nonconvex domains in the plane,, Comm. Partial Differential Equations, 35 (2010), 465. doi: 10.1080/03605300903307673. Google Scholar
A. Figalli and Y.-H. Kim, Partial regularity of Brenier solutions of the Monge-Ampère equation,, Discrete Contin. Dyn. Syst., 28 (2010), 559. doi: 10.3934/dcds.2010.28.559. Google Scholar
A. Figalli, Y.-H. Kim and R. J. McCann, Hölder continuity and injectivity of optimal maps,, Arch. Rational Mech. Anal., 209 (2013), 747. doi: 10.1007/s00205-013-0629-5. Google Scholar
A. Figalli, Y.-H. Kim and R. J. McCann, Regularity of optimal transport maps on multiple products of spheres,, J. Euro. Math. Soc., 15 (2013), 1131. doi: 10.4171/JEMS/388. Google Scholar
A. Figalli, Y.-H. Kim and R. J. McCann, When is multidimensional screening a convex program?,, J. Econom Theory, 146 (2011), 454. doi: 10.1016/j.jet.2010.11.006. Google Scholar
A. Figalli and L. Rifford, Continuity of optimal transport maps on small deformations of $\mathbbS^2$,, Comm. Pure Appl. Math., 62 (2009), 1670. doi: 10.1002/cpa.20293. Google Scholar
A. Figalli, L. Rifford and C. Villani, Nearly round spheres look convex,, Amer. J. Math., 134 (2012), 109. doi: 10.1353/ajm.2012.0000. Google Scholar
L. Forzani and D. Maldonado, Properties of the solutions to the Monge-Ampère equation,, Nonlinear Anal., 57 (2004), 815. doi: 10.1016/j.na.2004.03.019. Google Scholar
W. Gangbo., "Habilitation Thesis,", Université de Metz, (1995). Google Scholar
W. Gangbo and R. J. McCann, The geometry of optimal transportation,, Acta Math., 177 (1996), 113. doi: 10.1007/BF02392620. Google Scholar
W. Gangbo and R. J. McCann, Shape recognition via Wasserstein distance,, Quart. Appl. Math., 58 (2000), 705. Google Scholar
N. Gigli, On the inverse implication of Brenier-McCann theorems and the structure of $(P_2(M),W_2)$,, Methods Appl. Anal., 18 (2011), 127. Google Scholar
F. R. Harvey and H. B. Lawson, Jr, Split special Lagrangian geometry,, Progress in Mathematics 297 (2012), 297 (2012), 43. doi: 10.1007/978-3-0348-0257-4_3. Google Scholar
K. Hestir and S. C. Williams, Supports of doubly stochastic measures,, Bernoulli, 1 (1995), 217. doi: 10.2307/3318478. Google Scholar
L. Kantorovich, On the translocation of masses,, C. R. (Doklady) Acad. Sci. URSS (N. S.), 37 (1942), 199. Google Scholar
Y.-H. Kim and R. J. McCann, Towards the smoothness of optimal maps on Riemannian submersions and Riemannian products (of round spheres in particular),, J. Reine Angew. Math., 664 (2012), 1. doi: 10.1515/CRELLE.2011.105. Google Scholar
Y.-H. Kim and R. J. McCann, Continuity, curvature, and the general covariance of optimal transportation,, J. Eur. Math. Soc. (JEMS), 12 (2010), 1009. doi: 10.4171/JEMS/221. Google Scholar
Y.-H. Kim, R. J. McCann and M. Warren, Pseudo-Riemannian geometry calibrates optimal transportation,, Math. Res. Lett., 17 (2010), 1183. Google Scholar
J. Kitagawa and M. Warren, Regularity for the optimal transportation problem with Euclidean distance squared cost on the embedded sphere,, SIAM J. Math. Anal., 44 (2012), 2871. doi: 10.1137/120865409. Google Scholar
T. C. Koopmans and M. Beckmann, Assignment problems and the location of economic activities,, Econometrica, 25 (1957), 53. doi: 10.2307/1907742. Google Scholar
P. W. Y. Lee, New computable necessary conditions for the regularity theory of optimal transportation,, SIAM J. Math. Anal., 42 (2010), 3054. doi: 10.1137/100797722. Google Scholar
P. W. Y. Lee and J. Li, New examples on spaces of negative sectional curvature satisfying Ma-Trudinger-Wang conditions,, SIAM J. Math. Anal., 44 (2012), 61. doi: 10.1137/110820543. Google Scholar
P. W. Y. Lee and R. J. McCann, The Ma-Trudinger-Wang curvature for natural mechanical actions,, Calc. Var. Partial Differential Equations, 41 (2011), 285. doi: 10.1007/s00526-010-0362-y. Google Scholar
V. L. Levin, Abstract cyclical monotonicity and Monge solutions for the general Monge-Kantorovich problem,, Set-valued Anal., 7 (1999), 7. doi: 10.1023/A:1008753021652. Google Scholar
J. Li, "Smooth Optimal Transportation on Hyperbolic Space,'', Master's thesis, (2009). Google Scholar
J. Liu, Hölder regularity of optimal mappings in optimal transportation,, Calc Var. Partial Differential Equations, 34 (2009), 435. doi: 10.1007/s00526-008-0190-5. Google Scholar
J. Liu, N. S. Trudinger X.-J. Wang, Interior $C^{2,\alpha}$ regularity for potential functions in optimal transportation,, Comm. Partial Differential Equations, 35 (2010), 165. doi: 10.1080/03605300903236609. Google Scholar
G. Loeper, On the regularity of solutions of optimal transportation problems,, Acta Math., 202 (2009), 241. doi: 10.1007/s11511-009-0037-8. Google Scholar
G. Loeper, Regularity of optimal maps on the sphere: The quadratic cost and the reflector antenna,, Arch. Ration. Mech. Anal., 199 (2011), 269. doi: 10.1007/s00205-010-0330-x. Google Scholar
G. Loeper and C. Villani, Regularity of optimal transport in curved geometry: The non-focal case,, Duke Math. J., 151 (2010), 431. doi: 10.1215/00127094-2010-003. Google Scholar
G. G. Lorentz, An inequality for rearrangements,, Amer. Math. Monthly, 60 (1953), 176. doi: 10.2307/2307574. Google Scholar
J. Lott and C. Villani, Ricci curvature for metric measure spaces via optimal transport,, Annals Math. (2), 169 (2009), 903. doi: 10.4007/annals.2009.169.903. Google Scholar
X.-N. Ma, N. Trudinger and X.-J. Wang, Regularity of potential functions of the optimal transportation problem,, Arch. Rational Mech. Anal., 177 (2005), 151. doi: 10.1007/s00205-005-0362-9. Google Scholar
R. J. McCann, Existence and uniqueness of monotone measure-preserving maps,, Duke Math. J., 80 (1995), 309. doi: 10.1215/S0012-7094-95-08013-2. Google Scholar
R. J. McCann, A convexity principle for interacting gases,, Adv. Math., 128 (1997), 153. doi: 10.1006/aima.1997.1634. Google Scholar
R. J. McCann, Exact solutions to the transportation problem on the line,, R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci., 455 (1999), 1341. doi: 10.1098/rspa.1999.0364. Google Scholar
R. J. McCann, Polar factorization of maps on Riemannian manifolds,, Geom. Funct. Anal., 11 (2001), 589. doi: 10.1007/PL00001679. Google Scholar
R. J. McCann and N. Guillen, Five lectures on optimal transportation: geometry, regularity, and applications,, in, (2013), 145. Google Scholar
R. J. McCann and M. Sosio, Hölder continuity of optimal multivalued mappings,, SIAM J. Math. Anal., 43 (2011), 1855. doi: 10.1137/100802670. Google Scholar
R. J. McCann, B. Pass and M. Warren, Rectifiability of optimal transportation plans,, Canad. J. Math, 64 (2012), 924. doi: 10.4153/CJM-2011-080-6. Google Scholar
G. J. Minty, Monotone (nonlinear) operators in Hilbert space,, Duke Math. J., 29 (1962), 341. doi: 10.1215/S0012-7094-62-02933-2. Google Scholar
J. A. Mirrlees, An exploration in the theory of optimum income taxation,, Rev. Econom. Stud., 38 (1971), 175. Google Scholar
G. Monge, Mémoire sur la théorie des déblais et de remblais,, in, (1781), 666. Google Scholar
F. Otto, The geometry of dissipative evolution equations: The porous medium equation,, Comm. Partial Differential Equations, 26 (2001), 101. doi: 10.1081/PDE-100002243. Google Scholar
F. Otto and C. Villani, Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality,, J. Funct. Anal., 173 (2000), 361. doi: 10.1006/jfan.1999.3557. Google Scholar
B. Pass, On the local structure of optimal measures in the multi-marginal optimal transportation problem,, Calc. Var. Partial Differential Equations, 43 (2012), 529. doi: 10.1007/s00526-011-0421-z. Google Scholar
A. Pratelli, On the equality between Monge's infimum and Kantorovich's minimum in optimal mass transportation,, Ann. Inst. H. Poincaré Probab. Statist., 43 (2007), 1. doi: 10.1016/j.anihpb.2005.12.001. Google Scholar
A. Pratelli, On the sufficiency of c-cyclical monotonicity for optimality of transport plans,, Math. Z., 258 (2008), 677. doi: 10.1007/s00209-007-0191-7. Google Scholar
S. T. Rachev and L. Rüschendorf., "Mass Transportation Problems,", Vol. I. Theory. Probability and its Applications (New York). Springer-Verlag, (1998). Google Scholar
M.-K. von Renesse and K.-T. Sturm, Transport inequalities, gradient estimates, entropy and Ricci curvature,, Comm. Pure Appl. Math., 58 (2005), 923. doi: 10.1002/cpa.20060. Google Scholar
J.-C. Rochet, A necessary and sufficient condition for rationalizability in a quasi-linear context,, J. Math. Econom., 16 (1987), 191. doi: 10.1016/0304-4068(87)90007-3. Google Scholar
R. T. Rockafellar, Characterization of the subdifferentials of convex functions,, Pacific J. Math., 17 (1966), 497. doi: 10.2140/pjm.1966.17.497. Google Scholar
L. Rüschendorf and S.T. Rachev, A characterization of random variables with minimum $L^2$-distance,, J. Multivariate Anal., 32 (1990), 48. doi: 10.1016/0047-259X(90)90070-X. Google Scholar
W. Schachermayer and J. Teichmann, Characterization of optimal transport plans for the Monge-Kantorovich problem,, Proc. Amer. Math. Soc., 137 (2009), 519. doi: 10.1090/S0002-9939-08-09419-7. Google Scholar
C. Smith and M. Knott, Note on the optimal transportation of distributions,, J. Optim. Theory Appl., 52 (1987), 323. doi: 10.1007/BF00941290. Google Scholar
M. Spence, Job market signaling,, Quarterly J. Econom., 87 (1973), 355. doi: 10.2307/1882010. Google Scholar
K.-T. Sturm, On the geometry of metric measure spaces, I. ,, Acta Math., 196 (2006), 65. doi: 10.1007/s11511-006-0002-8. Google Scholar
N. S. Trudinger and X.-J. Wang, On the Monge mass transfer problem,, Calc. Var. Paritial Differential Equations, 13 (2001), 19. doi: 10.1007/PL00009922. Google Scholar
N. S. Trudinger and X.-J. Wang, On the second boundary value problem for Monge-Ampère type equations and optimal transportation,, Ann. Sc. Norm. Super. Pisa Cl. Sci. (5), 8 (2009), 143. Google Scholar
J. Urbas, On the second boundary value problem for equations of Monge-Ampère type,, J. Reine Angew. Math., 487 (1997), 115. doi: 10.1515/crll.1997.487.115. Google Scholar
C. Villani, "Topics in Optimal Transportation,", Graduate Studies in Mathematics, (2003). doi: 10.1007/b12016. Google Scholar
C. Villani, "Optimal Transport. Old and New,", Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], (2009). doi: 10.1007/978-3-540-71050-9. Google Scholar
X.-J. Wang, On the design of a reflector antenna,, Inverse Problems, 12 (1996), 351. doi: 10.1088/0266-5611/12/3/013. Google Scholar
X.-J. Wang, On the design of a reflector antenna II,, Calc. Var. Partial Differential Equations, 20 (2004), 329. doi: 10.1007/s00526-003-0239-4. Google Scholar
Y. Yu, Singular set of a convex potential in two dimensions,, Comm. Partial Differential Equations, 32 (2007), 1883. doi: 10.1080/03605300701318757. Google Scholar
Qi-Rui Li, Xu-Jia Wang. Regularity of the homogeneous Monge-Ampère equation. Discrete & Continuous Dynamical Systems - A, 2015, 35 (12) : 6069-6084. doi: 10.3934/dcds.2015.35.6069
Alessio Figalli, Young-Heon Kim. Partial regularity of Brenier solutions of the Monge-Ampère equation. Discrete & Continuous Dynamical Systems - A, 2010, 28 (2) : 559-565. doi: 10.3934/dcds.2010.28.559
Jiakun Liu, Neil S. Trudinger. On Pogorelov estimates for Monge-Ampère type equations. Discrete & Continuous Dynamical Systems - A, 2010, 28 (3) : 1121-1135. doi: 10.3934/dcds.2010.28.1121
Bo Guan, Qun Li. A Monge-Ampère type fully nonlinear equation on Hermitian manifolds. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1991-1999. doi: 10.3934/dcdsb.2012.17.1991
Limei Dai, Hongyu Li. Entire subsolutions of Monge-Ampère type equations. Communications on Pure & Applied Analysis, 2020, 19 (1) : 19-30. doi: 10.3934/cpaa.2020002
Jesus Garcia Azorero, Juan J. Manfredi, I. Peral, Julio D. Rossi. Limits for Monge-Kantorovich mass transport problems. Communications on Pure & Applied Analysis, 2008, 7 (4) : 853-865. doi: 10.3934/cpaa.2008.7.853
Cristian Enache. Maximum and minimum principles for a class of Monge-Ampère equations in the plane, with applications to surfaces of constant Gauss curvature. Communications on Pure & Applied Analysis, 2014, 13 (3) : 1347-1359. doi: 10.3934/cpaa.2014.13.1347
Abbas Moameni. Invariance properties of the Monge-Kantorovich mass transport problem. Discrete & Continuous Dynamical Systems - A, 2016, 36 (5) : 2653-2671. doi: 10.3934/dcds.2016.36.2653
Giuseppe Buttazzo, Eugene Stepanov. Transport density in Monge-Kantorovich problems with Dirichlet conditions. Discrete & Continuous Dynamical Systems - A, 2005, 12 (4) : 607-628. doi: 10.3934/dcds.2005.12.607
Jingang Xiong, Jiguang Bao. The obstacle problem for Monge-Ampère type equations in non-convex domains. Communications on Pure & Applied Analysis, 2011, 10 (1) : 59-68. doi: 10.3934/cpaa.2011.10.59
Barbara Brandolini, Carlo Nitsch, Cristina Trombetti. Shape optimization for Monge-Ampère equations via domain derivative. Discrete & Continuous Dynamical Systems - S, 2011, 4 (4) : 825-831. doi: 10.3934/dcdss.2011.4.825
Fan Cui, Huaiyu Jian. Symmetry of solutions to a class of Monge-Ampère equations. Communications on Pure & Applied Analysis, 2019, 18 (3) : 1247-1259. doi: 10.3934/cpaa.2019060
Luca Codenotti, Marta Lewicka. Visualization of the convex integration solutions to the Monge-Ampère equation. Evolution Equations & Control Theory, 2019, 8 (2) : 273-300. doi: 10.3934/eect.2019015
Zuo Quan Xu, Jia-An Yan. A note on the Monge-Kantorovich problem in the plane. Communications on Pure & Applied Analysis, 2015, 14 (2) : 517-525. doi: 10.3934/cpaa.2015.14.517
Adam M. Oberman. Wide stencil finite difference schemes for the elliptic Monge-Ampère equation and functions of the eigenvalues of the Hessian. Discrete & Continuous Dynamical Systems - B, 2008, 10 (1) : 221-238. doi: 10.3934/dcdsb.2008.10.221
Limei Dai. Multi-valued solutions to a class of parabolic Monge-Ampère equations. Communications on Pure & Applied Analysis, 2014, 13 (3) : 1061-1074. doi: 10.3934/cpaa.2014.13.1061
Diego Maldonado. On interior $C^2$-estimates for the Monge-Ampère equation. Discrete & Continuous Dynamical Systems - A, 2018, 38 (3) : 1427-1440. doi: 10.3934/dcds.2018058
Shouchuan Hu, Haiyan Wang. Convex solutions of boundary value problem arising from Monge-Ampère equations. Discrete & Continuous Dynamical Systems - A, 2006, 16 (3) : 705-720. doi: 10.3934/dcds.2006.16.705
Nassif Ghoussoub, Bernard Maurey. Remarks on multi-marginal symmetric Monge-Kantorovich problems. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1465-1480. doi: 10.3934/dcds.2014.34.1465
Yupeng Li, Wuchen Li, Guo Cao. Image segmentation via $ L_1 $ Monge-Kantorovich problem. Inverse Problems & Imaging, 2019, 13 (4) : 805-826. doi: 10.3934/ipi.2019037
Robert J. McCann