On the optimal map in the $ 2 $-dimensional random matching problem

Luigi Ambrosio; Federico Glaudo; Dario Trevisan

doi:10.3934/dcds.2019304

Article Contents

2019, Volume 39, Issue 12: 7291-7308. Doi: 10.3934/dcds.2019304

This issue Previous Article Sharp large time behaviour in $ N $-dimensional Fisher-KPP equations Next Article

On the optimal map in the $ 2 $-dimensional random matching problem

1.
Scuola Normale Superiore, Piazza dei Cavalieri 7, 56126 Pisa, Italy
2.
ETH, Rämistrasse 101, 8092 Zürich, Switzerland
3.
Dipartimento di Matematica, Università di Pisa, Largo Bruno Pontecorvo 5, 56127 Pisa, Italy

Received: February 28, 2019

Revised: April 30, 2019

Published: September 2019

L. Ambrosio acknowledges the support of the MIUR PRIN 2015 project. F. Glaudo has received funding from the European Research Council under the Grant Agreement No 721675. D. Trevisan is a member of INdAM GNAMPA group

Abstract Full Text(HTML) Figure(1) Related Papers Cited by

Abstract

We show that, on a $ 2 $-dimensional compact manifold, the optimal transport map in the semi-discrete random matching problem is well-approximated in the $ L^2 $-norm by identity plus the gradient of the solution to the Poisson problem $ - {\Delta} f^{n, t} = \mu^{n, t}-1 $, where $ \mu^{n, t} $ is an appropriate regularization of the empirical measure associated to the random points. This shows that the ansatz of [8] is strong enough to capture the behavior of the optimal map in addition to the value of the optimal matching cost.

As part of our strategy, we prove a new stability result for the optimal transport map on a compact manifold.

Keywords:

Mathematics Subject Classification: Primary: 60D05; Secondary: 49J55, 58J35, 35F21.

Citation:

Full Text(HTML)

Figure 1. The points considered in the proof of of Lemma 4.1

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	M. Ajtai, J. Komóls and G. Tusnády, On optimal matchings, Combinatorica, 4 (1984), 259-264. doi: 10.1007/BF02579135.
[2]	L. Ambrosio and F. Glaudo, Finer estimates on the 2-dimensional matching problem, preprint, arXiv: 1810.07002.
[3]	L. Ambrosio, F. Stra and D. Trevisan, A PDE approach to a 2-dimensional matching problem, Probability Theory and Related Fields, 173 (2019), 433-477. doi: 10.1007/s00440-018-0837-x.
[4]	M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhäuser Boston, Boston, MA, 1997. doi: 10.1007/978-0-8176-4755-1.
[5]	S. H. Benton, The Hamilton-Jacobi Equation: A Global Approach, Academic Press, 1977.
[6]	R. J. Berman, Convergence rates for discretized Monge-Ampère equations and quantitative stability of optimal transport, preprint, arXiv: 1803.00785.
[7]	Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions, Comm. Pure Appl. Math., 44 (1991), 375-417. doi: 10.1002/cpa.3160440402.
[8]	S. Caracciolo, C. Lucibello, G. Parisi and G. Sicuro, Scaling hypothesis for the Euclidean bipartite matching problem, Physical Review E, 90 (2014), 012118.
[9]	I. Chavel, Eigenvalues in Riemannian Geometry, vol. 115 of Pure and Applied Mathematics, Academic Press, 1984.
[10]	V. Dobrić and J. E. Yukich, Asymptotics for transportation cost in high dimensions, Journal of Theoretical Probability, 8 (1995), 97-118. doi: 10.1007/BF02213456.
[11]	L. C. Evans and R. F. Gariepy, Measure Theory and Fine Properties of Functions, Studies in Advanced Mathematics, CRC Press, Boca Raton, FL, 1992.
[12]	A. Fathi, Regularity of $C^1$ solutions of the Hamilton-Jacobi equation, in Annales de la Faculté des Sciences de Toulouse: Mathématiques, vol. 12, Université Paul Sabatier, Institut de Mathématiques, 2003, 479–516. doi: 10.5802/afst.1059.
[13]	N. Gigli, On Hölder continuity-in-time of the optimal transport map towards measures along a curve, Proceedings of the Edinburgh Mathematical Society, 54 (2011), 401-409. doi: 10.1017/S001309150800117X.
[14]	F. Glaudo, On the c-concavity with respect to the quadratic cost on a manifold, Nonlinear Analysis, 178 (2019), 145-151. doi: 10.1016/j.na.2018.07.015.
[15]	M. Goldman, M. Huesmann and F. Otto, A large-scale regularity theory for the Monge-Ampère equation with rough data and application to the optimal matching problem, preprint, arXiv: 1808.09250.
[16]	M. Goldman and F. Otto, A variational proof of partial regularity for optimal transportation maps, preprint, arXiv: 1704.05339.
[17]	N. Holden, Y. Peres and A. Zhai, Gravitational allocation on the sphere, Proceedings of the National Academy of Sciences, 115 (2018), 9666-9671. doi: 10.1073/pnas.1720804115.
[18]	M. Ledoux, On optimal matching of Gaussian samples, Veroyatnost i Statistika, 457 (2017), 226-264.
[19]	M. Ledoux, On optimal matching of Gaussian samples ii, https://perso.math.univ-toulouse.fr/ledoux/files/2019/03/SudakovII.pdf.
[20]	M. Ledoux, A fluctuation result in dual Sobolev norm for the optimal matching problem, https://perso.math.univ-toulouse.fr/ledoux/files/2019/02/matchingclt.pdf.
[21]	T. Leighton and P. Shor, Tight bounds for minimax grid matching with applications to the average case analysis of algorithms, Combinatorica, 9 (1989), 161-187. doi: 10.1007/BF02124678.
[22]	P.-L. Lions, Generalized Solutions of Hamilton-Jacobi Equations, vol. 69, London Pitman, 1982.
[23]	J. Lott and C. Villani, Hamilton–Jacobi semigroup on length spaces and applications, Journal de Mathématiques Pures et Appliquées, 88 (2007), 219–229. doi: 10.1016/j.matpur.2007.06.003.
[24]	R. J. McCann, Polar factorization of maps on Riemannian manifolds, Geometric and Functional Analysis, 11 (2001), 589-608. doi: 10.1007/PL00001679.
[25]	W. Rudin, Principles of Mathematical Analysis, 3rd edition, McGraw-hill New York, 1976.
[26]	F. Santambrogio, Optimal Transport for Applied Mathematicians, Calculus of variations, PDEs, and modeling. Progress in Nonlinear Differential Equations and their Applications, 87. Birkhäuser/Springer, Cham, 2015. doi: 10.1007/978-3-319-20828-2.
[27]	P. W. Shor and J. E. Yukich, Minimax grid matching and empirical measures, The Annals of Probability, 19 (1991), 1338-1348. doi: 10.1214/aop/1176990347.
[28]	M. Talagrand, Matching random samples in many dimensions, The Annals of Applied Probability, 2 (1992), 846-856. doi: 10.1214/aoap/1177005578.
[29]	M. Talagrand, Upper and Lower Bounds of Stochastic Processes, vol. 60 of Modern Surveys in Mathematics, Springer-Verlag, Berlin, 2014. doi: 10.1007/978-3-642-54075-2.
[30]	M. Talagrand, Scaling and non-standard matching theorems, Comptes Rendus Mathematique, 356 (2018), 692-695. doi: 10.1016/j.crma.2018.04.018.
[31]	G. Teschl, Ordinary Differential Equations and Dynamical Systems, vol. 140, American Mathematical Soc., 2012. doi: 10.1090/gsm/140.
[32]	N. G. Trillos and D. Slepčev, On the rate of convergence of empirical measures in $\infty$-transportation distance, Canadian Journal of Mathematics, 67 (2015), 1358-1383. doi: 10.4153/CJM-2014-044-6.
[33]	C. Villani, Optimal Transport, Old and New, Springer Verlag, Berlin, 2009. doi: 10.1007/978-3-540-71050-9.