Figure 1.
The points considered in the proof of of Lemma 4.1
- Previous Article
- DCDS Home
- This Issue
-
Next Article
Sharp large time behaviour in $ N $-dimensional Fisher-KPP equations
December
2019, 39(12): 7291-7308.
doi: 10.3934/dcds.2019304
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 |
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 [
As part of our strategy, we prove a new stability result for the optimal transport map on a compact manifold.
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 and Continuous Dynamical Systems,
2019, 39
(12)
: 7291-7308.
doi: 10.3934/dcds.2019304
![]()
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. |
show all references
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. |
| [1] |
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 |
| [2] |
Brendan Pass. Multi-marginal optimal transport and multi-agent matching problems: Uniqueness and structure of solutions. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1623-1639. doi: 10.3934/dcds.2014.34.1623 |
| [3] |
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 |
| [4] |
Claudio Marchi. On the convergence of singular perturbations of Hamilton-Jacobi equations. Communications on Pure and Applied Analysis, 2010, 9 (5) : 1363-1377. doi: 10.3934/cpaa.2010.9.1363 |
| [5] |
Nalini Anantharaman, Renato Iturriaga, Pablo Padilla, Héctor Sánchez-Morgado. Physical solutions of the Hamilton-Jacobi equation. Discrete and Continuous Dynamical Systems - B, 2005, 5 (3) : 513-528. doi: 10.3934/dcdsb.2005.5.513 |
| [6] |
Isabeau Birindelli, J. Wigniolle. Homogenization of Hamilton-Jacobi equations in the Heisenberg group. Communications on Pure and Applied Analysis, 2003, 2 (4) : 461-479. doi: 10.3934/cpaa.2003.2.461 |
| [7] |
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 |
| [8] |
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 |
| [9] |
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 |
| [10] |
Gonzalo Dávila. Comparison principles for nonlocal Hamilton-Jacobi equations. Discrete and Continuous Dynamical Systems, 2022, 42 (9) : 4471-4488. doi: 10.3934/dcds.2022061 |
| [11] |
Paola B. Manasero. Equivalences between two matching models: Stability. Journal of Dynamics and Games, 2018, 5 (3) : 203-221. doi: 10.3934/jdg.2018013 |
| [12] |
J. M. Mazón, Julio D. Rossi, J. Toledo. Optimal matching problems with costs given by Finsler distances. Communications on Pure and Applied Analysis, 2015, 14 (1) : 229-244. doi: 10.3934/cpaa.2015.14.229 |
| [13] |
Pengwen Chen, Changfeng Gui. Alpha divergences based mass transport models for image matching problems. Inverse Problems and Imaging, 2011, 5 (3) : 551-590. doi: 10.3934/ipi.2011.5.551 |
| [14] |
Yoshikazu Giga, Przemysław Górka, Piotr Rybka. Nonlocal spatially inhomogeneous Hamilton-Jacobi equation with unusual free boundary. Discrete and Continuous Dynamical Systems, 2010, 26 (2) : 493-519. doi: 10.3934/dcds.2010.26.493 |
| [15] |
Nicolas Forcadel, Mamdouh Zaydan. A comparison principle for Hamilton-Jacobi equation with moving in time boundary. Evolution Equations and Control Theory, 2019, 8 (3) : 543-565. doi: 10.3934/eect.2019026 |
| [16] |
Laura Caravenna, Annalisa Cesaroni, Hung Vinh Tran. Preface: Recent developments related to conservation laws and Hamilton-Jacobi equations. Discrete and Continuous Dynamical Systems - S, 2018, 11 (5) : i-iii. doi: 10.3934/dcdss.201805i |
| [17] |
Yuxiang Li. Stabilization towards the steady state for a viscous Hamilton-Jacobi equation. Communications on Pure and Applied Analysis, 2009, 8 (6) : 1917-1924. doi: 10.3934/cpaa.2009.8.1917 |
| [18] |
Fabio Camilli, Paola Loreti, Naoki Yamada. Systems of convex Hamilton-Jacobi equations with implicit obstacles and the obstacle problem. Communications on Pure and Applied Analysis, 2009, 8 (4) : 1291-1302. doi: 10.3934/cpaa.2009.8.1291 |
| [19] |
Alexander Quaas, Andrei Rodríguez. Analysis of the attainment of boundary conditions for a nonlocal diffusive Hamilton-Jacobi equation. Discrete and Continuous Dynamical Systems, 2018, 38 (10) : 5221-5243. doi: 10.3934/dcds.2018231 |
| [20] |
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 |
2021 Impact Factor: 1.588
Tools
Metrics
Other articles
by authors
[Back to Top]