logo Journal de l'École Polytechnique
Finer estimates on the 2-dimensional matching problem
[Estimations plus fines sur le problème de couplage]
Luigi Ambrosio1 ; Federico Glaudo2
1 Scuola Normale Superiore Piazza dei Cavalieri 7, 56126 Pisa, Italy
2 ETH Zürich Rämistrasse 101, 8092 Zürich, Switzerland
Journal de l’École polytechnique — Mathématiques, Tome 6 (2019), pp. 737-765.

Nous étudions le comportement asymptotique de l’espérance du coût du problème de couplage aléatoire dans une variété compacte de dimension 2, améliorant en de nombreux points les résultats de [AST18]. En particulier, nous simplifions la preuve originale et nous déterminons le coefficient dominant du développement asymptotique de l’espérance du coût du couplage aléatoire biparti dans une variété compacte de dimension 2. Nous précisons aussi l’estimation du terme d’erreur dans [Led18] pour le couplage semi-discret. Nous développons une estimation de contraction plus fine pour le flot de la chaleur sur des données aléatoires qui peut avoir un intérêt indépendant du reste de l’article.

We study the asymptotic behaviour of the expected cost of the random matching problem on a 2-dimensional compact manifold, improving in several aspects the results of [AST18]. In particular, we simplify the original proof (by treating at the same time upper and lower bounds) and we obtain the coefficient of the leading term of the asymptotic expansion of the expected cost for the random bipartite matching on a general 2-dimensional closed manifold. We also sharpen the estimate of the error term given in [Led18] for the semi-discrete matching. As a technical tool, we develop a refined contractivity estimate for the heat flow on random data that might be of independent interest.

Reçu le :
Accepté le :
Publié le :
DOI : 10.5802/jep.105
Classification : 60D05, 49J55, 60H15
Keywords: Optimal transport, matching problem, heat semigroup
Mot clés : Transport optimal, problème de couplage, semi-groupe de la chaleur
Luigi Ambrosio 1 ; Federico Glaudo 2

1 Scuola Normale Superiore Piazza dei Cavalieri 7, 56126 Pisa, Italy
2 ETH Zürich Rämistrasse 101, 8092 Zürich, Switzerland
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{JEP_2019__6__737_0,
     author = {Luigi Ambrosio and Federico Glaudo},
     title = {Finer estimates on the~$2$-dimensional~matching~problem},
     journal = {Journal de l{\textquoteright}\'Ecole polytechnique {\textemdash} Math\'ematiques},
     pages = {737--765},
     publisher = {\'Ecole polytechnique},
     volume = {6},
     year = {2019},
     doi = {10.5802/jep.105},
     zbl = {07114037},
     language = {en},
     url = {https://jep.centre-mersenne.org/articles/10.5802/jep.105/}
}
TY  - JOUR
AU  - Luigi Ambrosio
AU  - Federico Glaudo
TI  - Finer estimates on the $2$-dimensional matching problem
JO  - Journal de l’École polytechnique — Mathématiques
PY  - 2019
SP  - 737
EP  - 765
VL  - 6
PB  - École polytechnique
UR  - https://jep.centre-mersenne.org/articles/10.5802/jep.105/
DO  - 10.5802/jep.105
LA  - en
ID  - JEP_2019__6__737_0
ER  - 
%0 Journal Article
%A Luigi Ambrosio
%A Federico Glaudo
%T Finer estimates on the $2$-dimensional matching problem
%J Journal de l’École polytechnique — Mathématiques
%D 2019
%P 737-765
%V 6
%I École polytechnique
%U https://jep.centre-mersenne.org/articles/10.5802/jep.105/
%R 10.5802/jep.105
%G en
%F JEP_2019__6__737_0
Luigi Ambrosio; Federico Glaudo. Finer estimates on the $2$-dimensional matching problem. Journal de l’École polytechnique — Mathématiques, Tome 6 (2019), pp. 737-765. doi : 10.5802/jep.105. https://jep.centre-mersenne.org/articles/10.5802/jep.105/

[AKT84] M. Ajtai, J. Komlós & G. Tusnády - “On optimal matchings”, Combinatorica 4 (1984) no. 4, p. 259-264 | DOI | MR | Zbl

[AST18] L. Ambrosio, F. Stra & D. Trevisan - “A PDE approach to a 2-dimensional matching problem”, Probab. Theory Related Fields (2018), p. 1-45 | Zbl

[BB00] J.-D. Benamou & Y. Brenier - “A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem”, Numer. Math. 84 (2000) no. 3, p. 375-393 | DOI | MR | Zbl

[BB13] F. Barthe & C. Bordenave - “Combinatorial optimization over two random point sets”, in Séminaire de Probabilités XLV, Lect. Notes in Math., vol. 2078, Springer, Cham, 2013, p. 483-535 | DOI | MR | Zbl

[Ber46] S. N. Bernstein - Probability theory, Moscow-Leningrad, 1946, In Russian

[BL14] S. Bobkov & M. Ledoux - “One-dimensional empirical measures, order statistics and Kantorovich transport distances” (2014), preprint

[BLG14] E. Boissard & T. Le Gouic - “On the mean speed of convergence of empirical and occupation measures in Wasserstein distance”, Ann. Inst. H. Poincaré Probab. Statist. 50 (2014) no. 2, p. 539-563 | DOI | MR | Zbl

[BLM03] S. Boucheron, G. Lugosi & P. Massart - “Concentration inequalities using the entropy method”, Ann. Probab. 31 (2003) no. 3, p. 1583-1614 | DOI | MR | Zbl

[Bro93] R. M. Brown - “The trace of the heat kernel in Lipschitz domains”, Trans. Amer. Math. Soc. 339 (1993) no. 2, p. 889-900 | DOI | MR | Zbl

[Cha84] I. Chavel - Eigenvalues in Riemannian geometry, Pure and Applied Math., vol. 115, Academic Press, Inc., Orlando, FL, 1984 | MR | Zbl

[CL06] F. Chung & L. Lu - “Concentration inequalities and martingale inequalities: a survey”, Internet Math. 3 (2006) no. 1, p. 79-127 | DOI | MR | Zbl

[CLPS14] S. Caracciolo, C. Lucibello, G. Parisi & G. Sicuro - “Scaling hypothesis for the Euclidean bipartite matching problem”, Phys. Rev. E 90 (2014) no. 1, article ID 012118

[CLY81] S. Y. Cheng, P. Li & S. T. Yau - “On the upper estimate of the heat kernel of a complete Riemannian manifold”, Amer. J. Math. 103 (1981) no. 5, p. 1021-1063 | DOI | MR | Zbl

[CR17] N. Charalambous & J. Rowlett - “The heat trace for the drifting Laplacian and Schrödinger operators on manifolds”, 2017 | arXiv | Zbl

[CS14] S. Caracciolo & G. Sicuro - “One-dimensional Euclidean matching problem: exact solutions, correlation functions, and universality”, Phys. Rev. E 90 (2014) no. 4, article ID 042112

[DSS13] S. Dereich, M. Scheutzow & R. Schottstedt - “Constructive quantization: approximation by empirical measures”, Ann. Inst. H. Poincaré Probab. Statist. 49 (2013) no. 4, p. 1183-1203 | DOI | MR | Zbl

[DY95] V. Dobrić & J. E. Yukich - “Asymptotics for transportation cost in high dimensions”, J. Theoret. Probab. 8 (1995) no. 1, p. 97-118 | DOI | MR | Zbl

[EKS15] M. Erbar, K. Kuwada & K.-T. Sturm - “On the equivalence of the entropic curvature-dimension condition and Bochner’s inequality on metric measure spaces”, Invent. Math. 201 (2015) no. 3, p. 993-1071 | DOI | MR | Zbl

[Erb10] M. Erbar - “The heat equation on manifolds as a gradient flow in the Wasserstein space”, Ann. Inst. H. Poincaré Probab. Statist. 46 (2010) no. 1, p. 1-23 | DOI | MR | Zbl

[FG15] N. Fournier & A. Guillin - “On the rate of convergence in Wasserstein distance of the empirical measure”, Probab. Theory Related Fields 162 (2015) no. 3-4, p. 707-738 | DOI | MR | Zbl

[GHO18] M. Goldman, M. Huesmann & F. Otto - “A large-scale regularity theory for the Monge-Ampère equation with rough data and application to the optimal matching problem”, 2018 | arXiv

[Gla19] F. Glaudo - “On the c-concavity with respect to the quadratic cost on a manifold”, Nonlinear Anal. 178 (2019), p. 145-151 | DOI | MR | Zbl

[Gri99] A. Grigor’yan - “Estimates of heat kernels on Riemannian manifolds”, in Spectral theory and geometry (Edinburgh, 1998), London Math. Soc. Lecture Note Ser., vol. 273, Cambridge Univ. Press, Cambridge, 1999, p. 140-225 | DOI | MR | Zbl

[Gri06] A. Grigor’yan - “Heat kernels on weighted manifolds and applications”, in The ubiquitous heat kernel, Contemp. Math., vol. 398, American Mathematical Society, 2006, p. 93-191 | DOI | MR | Zbl

[Hoe63] W. Hoeffding - “Probability inequalities for sums of bounded random variables”, J. Amer. Statist. Assoc. 58 (1963) no. 301, p. 13-30 | DOI | MR | Zbl

[HS13] M. Huesmann & K.-T. Sturm - “Optimal transport from Lebesgue to Poisson”, Ann. Probab. 41 (2013) no. 4, p. 2426-2478 | DOI | MR | Zbl

[Hsu99] E. P. Hsu - “Estimates of derivatives of the heat kernel on a compact Riemannian manifold”, Proc. Amer. Math. Soc. 127 (1999) no. 12, p. 3739-3744 | MR | Zbl

[JKO98] R. Jordan, D. Kinderlehrer & F. Otto - “The variational formulation of the Fokker-Planck equation”, SIAM J. Math. Anal. 29 (1998) no. 1, p. 1-17 | DOI | MR | Zbl

[Led17] M. Ledoux - “On optimal matching of Gaussian samples”, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 457 (2017), p. 226-264, Reprinted in J. Math. Sci. (N.Y.) 38 (2019), no. 4, p. 495–522 | Zbl

[Led18] M. Ledoux - “On optimal matching of Gaussian samples II” (2018), http://perso.math.univ-toulouse.fr/ledoux/files/2019/03/SudakovII.pdf | Zbl

[MS67] H. P. McKean & I. M. Singer - “Curvature and the eigenvalues of the Laplacian”, J. Differential Geometry 1 (1967) no. 1, p. 43-69 | DOI | MR | Zbl

[OV00] F. Otto & C. Villani - “Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality”, J. Funct. Anal. 173 (2000) no. 2, p. 361-400 | DOI | MR | Zbl

[Pet98] P. Petersen - Riemannian geometry, Graduate Texts in Math., vol. 171, Springer-Verlag, New York, 1998 | MR | Zbl

[San15] F. Santambrogio - Optimal transport for applied mathematicians, Progress in Nonlinear Differential Equations and their Applications, vol. 87, Birkhäuser/Springer, Cham, 2015 | DOI | MR | Zbl

[SC10] L. Saloff-Coste - “The heat kernel and its estimates”, in Probabilistic approach to geometry, Adv. Stud. Pure Math., vol. 57, Math. Soc. Japan, Tokyo, 2010, p. 405-436 | DOI | MR | Zbl

[ST98] D. W. Stroock & J. Turetsky - “Upper bounds on derivatives of the logarithm of the heat kernel”, Comm. Anal. Geom. 6 (1998) no. 4, p. 669-685 | DOI | MR | Zbl

[Tal92] M. Talagrand - “Matching random samples in many dimensions”, Ann. Appl. Probab. 2 (1992) no. 4, p. 846-856 | DOI | MR | Zbl

[Tal14] M. Talagrand - Upper and lower bounds of stochastic processes, Modern Surveys in Math., vol. 60, Springer-Verlag, Berlin, 2014 | MR | Zbl

[Tal18] M. Talagrand - “Scaling and non-standard matching theorems”, Comptes Rendus Mathématique 356 (2018) no. 6, p. 692-695 | DOI | MR | Zbl

[Vil09] C. Villani - Optimal transport. Old and new, Grundlehren Math. Wiss., vol. 338, Springer Verlag, Berlin, 2009 | Zbl

[WB17] J. Weed & F. Bach - “Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance”, 2017 | arXiv | Zbl

[ZLJ16] H. Zhang, H. Li & R. Jiang - “Heat kernel bounds on metric measure spaces and some applications”, Potential Anal. 44 (2016) no. 3, p. 601-627 | MR | Zbl

Cité par Sources :