Luigi Ambrosio 1, , Federico Glaudo 2, and Dario Trevisan 3,
Scuola Normale Superiore, Piazza dei Cavalieri 7, 56126 Pisa, Italy
ETH, Rämistrasse 101, 8092 Zürich, Switzerland
Dipartimento di Matematica, Università di Pisa, Largo Bruno Pontecorvo 5, 56127 Pisa, Italy
Received March 2019 Revised May 2019 Published September 2019
Fund Project: 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
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: Minimum matching, random matching, optimal transport, Hamilton-Jacobi, stability.
Mathematics Subject Classification: Primary: 60D05; Secondary: 49J55, 58J35, 35F21.
Citation: Luigi Ambrosio, Federico Glaudo, Dario Trevisan. On the optimal map in the $ 2 $-dimensional random matching problem. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 7291-7308. doi: 10.3934/dcds.2019304
M. Ajtai, J. Komóls and G. Tusnády, On optimal matchings, Combinatorica, 4 (1984), 259-264. doi: 10.1007/BF02579135. Google Scholar
L. Ambrosio and F. Glaudo, Finer estimates on the 2-dimensional matching problem, preprint, arXiv: 1810.07002. Google Scholar
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. Google Scholar
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. Google Scholar
[5] S. H. Benton, The Hamilton-Jacobi Equation: A Global Approach, Academic Press, 1977. Google Scholar
R. J. Berman, Convergence rates for discretized Monge-Ampère equations and quantitative stability of optimal transport, preprint, arXiv: 1803.00785. Google Scholar
Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions, Comm. Pure Appl. Math., 44 (1991), 375-417. doi: 10.1002/cpa.3160440402. Google Scholar
S. Caracciolo, C. Lucibello, G. Parisi and G. Sicuro, Scaling hypothesis for the Euclidean bipartite matching problem, Physical Review E, 90 (2014), 012118. Google Scholar
I. Chavel, Eigenvalues in Riemannian Geometry, vol. 115 of Pure and Applied Mathematics, Academic Press, 1984. Google Scholar
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. Google Scholar
L. C. Evans and R. F. Gariepy, Measure Theory and Fine Properties of Functions, Studies in Advanced Mathematics, CRC Press, Boca Raton, FL, 1992. Google Scholar
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. Google Scholar
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. Google Scholar
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. Google Scholar
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. Google Scholar
M. Goldman and F. Otto, A variational proof of partial regularity for optimal transportation maps, preprint, arXiv: 1704.05339. Google Scholar
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. Google Scholar
M. Ledoux, On optimal matching of Gaussian samples, Veroyatnost i Statistika, 457 (2017), 226-264. Google Scholar
M. Ledoux, On optimal matching of Gaussian samples ii, https://perso.math.univ-toulouse.fr/ledoux/files/2019/03/SudakovII.pdf. Google Scholar
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. Google Scholar
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. Google Scholar
P.-L. Lions, Generalized Solutions of Hamilton-Jacobi Equations, vol. 69, London Pitman, 1982. Google Scholar
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. Google Scholar
R. J. McCann, Polar factorization of maps on Riemannian manifolds, Geometric and Functional Analysis, 11 (2001), 589-608. doi: 10.1007/PL00001679. Google Scholar
W. Rudin, Principles of Mathematical Analysis, 3rd edition, McGraw-hill New York, 1976. Google Scholar
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. Google Scholar
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. Google Scholar
M. Talagrand, Matching random samples in many dimensions, The Annals of Applied Probability, 2 (1992), 846-856. doi: 10.1214/aoap/1177005578. Google Scholar
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. Google Scholar
M. Talagrand, Scaling and non-standard matching theorems, Comptes Rendus Mathematique, 356 (2018), 692-695. doi: 10.1016/j.crma.2018.04.018. Google Scholar
G. Teschl, Ordinary Differential Equations and Dynamical Systems, vol. 140, American Mathematical Soc., 2012. doi: 10.1090/gsm/140. Google Scholar
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. Google Scholar
C. Villani, Optimal Transport, Old and New, Springer Verlag, Berlin, 2009. doi: 10.1007/978-3-540-71050-9. Google Scholar
Figure 1. The points considered in the proof of of Lemma 4.1
Brendan Pass. Multi-marginal optimal transport and multi-agent matching problems: Uniqueness and structure of solutions. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1623-1639. doi: 10.3934/dcds.2014.34.1623
Joan-Andreu Lázaro-Camí, Juan-Pablo Ortega. The stochastic Hamilton-Jacobi equation. Journal of Geometric Mechanics, 2009, 1 (3) : 295-315. doi: 10.3934/jgm.2009.1.295
J. M. Mazón, Julio D. Rossi, J. Toledo. Optimal matching problems with costs given by Finsler distances. Communications on Pure & Applied Analysis, 2015, 14 (1) : 229-244. doi: 10.3934/cpaa.2015.14.229
Paola B. Manasero. Equivalences between two matching models: Stability. Journal of Dynamics & Games, 2018, 5 (3) : 203-221. doi: 10.3934/jdg.2018013
Tomoki Ohsawa, Anthony M. Bloch. Nonholonomic Hamilton-Jacobi equation and integrability. Journal of Geometric Mechanics, 2009, 1 (4) : 461-481. doi: 10.3934/jgm.2009.1.461
Claudio Marchi. On the convergence of singular perturbations of Hamilton-Jacobi equations. Communications on Pure & Applied Analysis, 2010, 9 (5) : 1363-1377. doi: 10.3934/cpaa.2010.9.1363
Nalini Anantharaman, Renato Iturriaga, Pablo Padilla, Héctor Sánchez-Morgado. Physical solutions of the Hamilton-Jacobi equation. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 513-528. doi: 10.3934/dcdsb.2005.5.513
Isabeau Birindelli, J. Wigniolle. Homogenization of Hamilton-Jacobi equations in the Heisenberg group. Communications on Pure & Applied Analysis, 2003, 2 (4) : 461-479. doi: 10.3934/cpaa.2003.2.461
María Barbero-Liñán, Manuel de León, David Martín de Diego, Juan C. Marrero, Miguel C. Muñoz-Lecanda. Kinematic reduction and the Hamilton-Jacobi equation. Journal of Geometric Mechanics, 2012, 4 (3) : 207-237. doi: 10.3934/jgm.2012.4.207
Larry M. Bates, Francesco Fassò, Nicola Sansonetto. The Hamilton-Jacobi equation, integrability, and nonholonomic systems. Journal of Geometric Mechanics, 2014, 6 (4) : 441-449. doi: 10.3934/jgm.2014.6.441
Manuel de León, David Martín de Diego, Miguel Vaquero. A Hamilton-Jacobi theory on Poisson manifolds. Journal of Geometric Mechanics, 2014, 6 (1) : 121-140. doi: 10.3934/jgm.2014.6.121
Pengwen Chen, Changfeng Gui. Alpha divergences based mass transport models for image matching problems. Inverse Problems & Imaging, 2011, 5 (3) : 551-590. doi: 10.3934/ipi.2011.5.551
Angel Angelov, Marcus Wagner. Multimodal image registration by elastic matching of edge sketches via optimal control. Journal of Industrial & Management Optimization, 2014, 10 (2) : 567-590. doi: 10.3934/jimo.2014.10.567
Yoshikazu Giga, Przemysław Górka, Piotr Rybka. Nonlocal spatially inhomogeneous Hamilton-Jacobi equation with unusual free boundary. Discrete & Continuous Dynamical Systems - A, 2010, 26 (2) : 493-519. doi: 10.3934/dcds.2010.26.493
Laura Caravenna, Annalisa Cesaroni, Hung Vinh Tran. Preface: Recent developments related to conservation laws and Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems - S, 2018, 11 (5) : ⅰ-ⅲ. doi: 10.3934/dcdss.201805i
Yuxiang Li. Stabilization towards the steady state for a viscous Hamilton-Jacobi equation. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1917-1924. doi: 10.3934/cpaa.2009.8.1917
Fabio Camilli, Paola Loreti, Naoki Yamada. Systems of convex Hamilton-Jacobi equations with implicit obstacles and the obstacle problem. Communications on Pure & Applied Analysis, 2009, 8 (4) : 1291-1302. doi: 10.3934/cpaa.2009.8.1291
Alexander Quaas, Andrei Rodríguez. Analysis of the attainment of boundary conditions for a nonlocal diffusive Hamilton-Jacobi equation. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 5221-5243. doi: 10.3934/dcds.2018231
Giuseppe Marmo, Giuseppe Morandi, Narasimhaiengar Mukunda. The Hamilton-Jacobi theory and the analogy between classical and quantum mechanics. Journal of Geometric Mechanics, 2009, 1 (3) : 317-355. doi: 10.3934/jgm.2009.1.317
Yasuhiro Fujita, Katsushi Ohmori. Inequalities and the Aubry-Mather theory of Hamilton-Jacobi equations. Communications on Pure & Applied Analysis, 2009, 8 (2) : 683-688. doi: 10.3934/cpaa.2009.8.683
Luigi Ambrosio Federico Glaudo Dario Trevisan