American Institute of Mathematical Sciences

Advanced
December  2019, 39(12): 7291-7308. doi: 10.3934/dcds.2019304

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

Luigi Ambrosio 1, , Federico Glaudo 2, and  Dario Trevisan 3,

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  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, 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.  Google Scholar

[2]

L. Ambrosio and F. Glaudo, Finer estimates on the 2-dimensional matching problem, preprint, arXiv: 1810.07002. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5] S. H. Benton, The Hamilton-Jacobi Equation: A Global Approach, Academic Press, 1977.   Google Scholar
[6]

R. J. Berman, Convergence rates for discretized Monge-Ampère equations and quantitative stability of optimal transport, preprint, arXiv: 1803.00785. Google Scholar

[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.  Google Scholar

[8]

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

[9]

I. Chavel, Eigenvalues in Riemannian Geometry, vol. 115 of Pure and Applied Mathematics, Academic Press, 1984.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[16]

M. Goldman and F. Otto, A variational proof of partial regularity for optimal transportation maps, preprint, arXiv: 1704.05339. Google Scholar

[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.  Google Scholar

[18]

M. Ledoux, On optimal matching of Gaussian samples, Veroyatnost i Statistika, 457 (2017), 226-264.   Google Scholar

[19]

M. Ledoux, On optimal matching of Gaussian samples ii, https://perso.math.univ-toulouse.fr/ledoux/files/2019/03/SudakovII.pdf. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[22]

P.-L. Lions, Generalized Solutions of Hamilton-Jacobi Equations, vol. 69, London Pitman, 1982.  Google Scholar

[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.  Google Scholar

[24]

R. J. McCann, Polar factorization of maps on Riemannian manifolds, Geometric and Functional Analysis, 11 (2001), 589-608.  doi: 10.1007/PL00001679.  Google Scholar

[25]

W. Rudin, Principles of Mathematical Analysis, 3rd edition, McGraw-hill New York, 1976.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28]

M. Talagrand, Matching random samples in many dimensions, The Annals of Applied Probability, 2 (1992), 846-856.  doi: 10.1214/aoap/1177005578.  Google Scholar

[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.  Google Scholar

[30]

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

[31]

G. Teschl, Ordinary Differential Equations and Dynamical Systems, vol. 140, American Mathematical Soc., 2012. doi: 10.1090/gsm/140.  Google Scholar

[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.  Google Scholar

[33]

C. Villani, Optimal Transport, Old and New, Springer Verlag, Berlin, 2009. doi: 10.1007/978-3-540-71050-9.  Google Scholar

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.  Google Scholar

[2]

L. Ambrosio and F. Glaudo, Finer estimates on the 2-dimensional matching problem, preprint, arXiv: 1810.07002. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5] S. H. Benton, The Hamilton-Jacobi Equation: A Global Approach, Academic Press, 1977.   Google Scholar
[6]

R. J. Berman, Convergence rates for discretized Monge-Ampère equations and quantitative stability of optimal transport, preprint, arXiv: 1803.00785. Google Scholar

[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.  Google Scholar

[8]

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

[9]

I. Chavel, Eigenvalues in Riemannian Geometry, vol. 115 of Pure and Applied Mathematics, Academic Press, 1984.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[16]

M. Goldman and F. Otto, A variational proof of partial regularity for optimal transportation maps, preprint, arXiv: 1704.05339. Google Scholar

[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.  Google Scholar

[18]

M. Ledoux, On optimal matching of Gaussian samples, Veroyatnost i Statistika, 457 (2017), 226-264.   Google Scholar

[19]

M. Ledoux, On optimal matching of Gaussian samples ii, https://perso.math.univ-toulouse.fr/ledoux/files/2019/03/SudakovII.pdf. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[22]

P.-L. Lions, Generalized Solutions of Hamilton-Jacobi Equations, vol. 69, London Pitman, 1982.  Google Scholar

[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.  Google Scholar

[24]

R. J. McCann, Polar factorization of maps on Riemannian manifolds, Geometric and Functional Analysis, 11 (2001), 589-608.  doi: 10.1007/PL00001679.  Google Scholar

[25]

W. Rudin, Principles of Mathematical Analysis, 3rd edition, McGraw-hill New York, 1976.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28]

M. Talagrand, Matching random samples in many dimensions, The Annals of Applied Probability, 2 (1992), 846-856.  doi: 10.1214/aoap/1177005578.  Google Scholar

[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.  Google Scholar

[30]

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

[31]

G. Teschl, Ordinary Differential Equations and Dynamical Systems, vol. 140, American Mathematical Soc., 2012. doi: 10.1090/gsm/140.  Google Scholar

[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.  Google Scholar

[33]

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
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Ahmad El Hajj, Hassan Ibrahim, Vivian Rizik. $ BV $ solution for a non-linear Hamilton-Jacobi system. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3273-3293. doi: 10.3934/dcds.2020405
[2]

Olivier Ley, Erwin Topp, Miguel Yangari. Some results for the large time behavior of Hamilton-Jacobi equations with Caputo time derivative. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3555-3577. doi: 10.3934/dcds.2021007
[3]

Charlene Kalle, Niels Langeveld, Marta Maggioni, Sara Munday. Matching for a family of infinite measure continued fraction transformations. Discrete & Continuous Dynamical Systems, 2020, 40 (11) : 6309-6330. doi: 10.3934/dcds.2020281
[4]

Wei Wang, Degen Huang, Haitao Yu. Word sense disambiguation based on stretchable matching of the semantic template. Mathematical Foundations of Computing, 2021, 4 (1) : 1-13. doi: 10.3934/mfc.2020022
[5]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311
[6]

Shi'an Wang, N. U. Ahmed. Optimal control and stabilization of building maintenance units based on minimum principle. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1713-1727. doi: 10.3934/jimo.2020041
[7]

Yongjian Liu, Qiujian Huang, Zhouchao Wei. Dynamics at infinity and Jacobi stability of trajectories for the Yang-Chen system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3357-3380. doi: 10.3934/dcdsb.2020235
[8]

Rafael G. L. D'Oliveira, Marcelo Firer. Minimum dimensional Hamming embeddings. Advances in Mathematics of Communications, 2017, 11 (2) : 359-366. doi: 10.3934/amc.2017029
[9]

Christopher Bose, Rua Murray. Minimum 'energy' approximations of invariant measures for nonsingular transformations. Discrete & Continuous Dynamical Systems, 2006, 14 (3) : 597-615. doi: 10.3934/dcds.2006.14.597
[10]

Ágota P. Horváth. Discrete diffusion semigroups associated with Jacobi-Dunkl and exceptional Jacobi polynomials. Communications on Pure & Applied Analysis, 2021, 20 (3) : 975-994. doi: 10.3934/cpaa.2021002
[11]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[12]

Luigi Barletti, Giovanni Nastasi, Claudia Negulescu, Vittorio Romano. Mathematical modelling of charge transport in graphene heterojunctions. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021010
[13]

Scott Schmieding, Rodrigo Treviño. Random substitution tilings and deviation phenomena. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3869-3902. doi: 10.3934/dcds.2021020
[14]

Jingni Guo, Junxiang Xu, Zhenggang He, Wei Liao. Research on cascading failure modes and attack strategies of multimodal transport network. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2020159
[15]

F.J. Herranz, J. de Lucas, C. Sardón. Jacobi--Lie systems: Fundamentals and low-dimensional classification. Conference Publications, 2015, 2015 (special) : 605-614. doi: 10.3934/proc.2015.0605
[16]

Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034
[17]

Pablo D. Carrasco, Túlio Vales. A symmetric Random Walk defined by the time-one map of a geodesic flow. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2891-2905. doi: 10.3934/dcds.2020390
[18]

Yuta Tanoue. Improved Hoeffding inequality for dependent bounded or sub-Gaussian random variables. Probability, Uncertainty and Quantitative Risk, 2021, 6 (1) : 53-60. doi: 10.3934/puqr.2021003
[19]

Skyler Simmons. Stability of Broucke's isosceles orbit. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3759-3779. doi: 10.3934/dcds.2021015
[20]

Christophe Zhang. Internal rapid stabilization of a 1-D linear transport equation with a scalar feedback. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021006

2019 Impact Factor: 1.338

Tools

Metrics

  • PDF downloads (176)
  • HTML views (152)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences