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

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.

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
References:
[1]

M. AjtaiJ. 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. AmbrosioF. 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. HoldenY. 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. AjtaiJ. 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. AmbrosioF. 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. HoldenY. 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
[1]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024

[2]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[3]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

[4]

Shiqi Ma. On recent progress of single-realization recoveries of random Schrödinger systems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020121

[5]

José Madrid, João P. G. Ramos. On optimal autocorrelation inequalities on the real line. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020271

[6]

Reza Chaharpashlou, Abdon Atangana, Reza Saadati. On the fuzzy stability results for fractional stochastic Volterra integral equation. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020432

[7]

Scipio Cuccagna, Masaya Maeda. A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020450

[8]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[9]

Yangrong Li, Shuang Yang, Qiangheng Zhang. Odd random attractors for stochastic non-autonomous Kuramoto-Sivashinsky equations without dissipation. Electronic Research Archive, 2020, 28 (4) : 1529-1544. doi: 10.3934/era.2020080

[10]

Wenmeng Geng, Kai Tao. Large deviation theorems for dirichlet determinants of analytic quasi-periodic jacobi operators with Brjuno-Rüssmann frequency. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5305-5335. doi: 10.3934/cpaa.2020240

[11]

Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020375

[12]

Tommi Brander, Joonas Ilmavirta, Petteri Piiroinen, Teemu Tyni. Optimal recovery of a radiating source with multiple frequencies along one line. Inverse Problems & Imaging, 2020, 14 (6) : 967-983. doi: 10.3934/ipi.2020044

[13]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

[14]

Xin-Guang Yang, Lu Li, Xingjie Yan, Ling Ding. The structure and stability of pullback attractors for 3D Brinkman-Forchheimer equation with delay. Electronic Research Archive, 2020, 28 (4) : 1395-1418. doi: 10.3934/era.2020074

[15]

Chao Xing, Jiaojiao Pan, Hong Luo. Stability and dynamic transition of a toxin-producing phytoplankton-zooplankton model with additional food. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020275

[16]

A. M. Elaiw, N. H. AlShamrani, A. Abdel-Aty, H. Dutta. Stability analysis of a general HIV dynamics model with multi-stages of infected cells and two routes of infection. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020441

[17]

Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347

[18]

Bernard Bonnard, Jérémy Rouot. Geometric optimal techniques to control the muscular force response to functional electrical stimulation using a non-isometric force-fatigue model. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020032

[19]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

2019 Impact Factor: 1.338

Metrics

  • PDF downloads (145)
  • HTML views (149)
  • Cited by (1)

Other articles
by authors

[Back to Top]