Finer estimates on the 2-dimensional matching problem
[Estimations plus fines sur le problème de couplage]
Ambrosio, Luigi1 ; Glaudo, Federico2
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
Ambrosio, Luigi 1 ; Glaudo, Federico 2

1 Scuola Normale Superiore Piazza dei Cavalieri 7, 56126 Pisa, Italy
2 ETH Zürich Rämistrasse 101, 8092 Zürich, Switzerland 
@article{JEP_2019__6__737_0,
     author = {Ambrosio, Luigi and Glaudo, Federico},
     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 = {http://www.numdam.org/articles/10.5802/jep.105/}
}
TY  - JOUR
AU  - Ambrosio, Luigi
AU  - Glaudo, Federico
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  - Ecole polytechnique
UR  - http://www.numdam.org/articles/10.5802/jep.105/
DO  - 10.5802/jep.105
LA  - en
ID  - JEP_2019__6__737_0
ER  - 
%0 Journal Article
%A Ambrosio, Luigi
%A Glaudo, Federico
%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 Ecole polytechnique
%U http://www.numdam.org/articles/10.5802/jep.105/
%R 10.5802/jep.105
%G en
%F JEP_2019__6__737_0
Ambrosio, Luigi; Glaudo, Federico. 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. http://www.numdam.org/articles/10.5802/jep.105/

[AKT84] Ajtai, Miklós; Komlós, János; Tusnády, Gábor On optimal matchings, Combinatorica, Volume 4 (1984) no. 4, pp. 259-264 | DOI | MR | Zbl

[AST18] Ambrosio, Luigi; Stra, Federico; Trevisan, Dario A PDE approach to a 2-dimensional matching problem, Probab. Theory Related Fields (2018), pp. 1-45 | Zbl

[BB00] Benamou, Jean-David; Brenier, Yann A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numer. Math., Volume 84 (2000) no. 3, pp. 375-393 | DOI | MR | Zbl

[BB13] Barthe, Franck; Bordenave, Charles Combinatorial optimization over two random point sets, Séminaire de Probabilités XLV (Lect. Notes in Math.), Volume 2078, Springer, Cham, 2013, pp. 483-535 | DOI | MR | Zbl

[Ber46] Bernstein, Sergei N. Probability theory, Moscow-Leningrad, 1946 (In Russian)

[BL14] Bobkov, Sergey; Ledoux, Michel One-dimensional empirical measures, order statistics and Kantorovich transport distances (2014) (preprint)

[BLG14] Boissard, Emmanuel; Le Gouic, Thibaut On the mean speed of convergence of empirical and occupation measures in Wasserstein distance, Ann. Inst. H. Poincaré Probab. Statist., Volume 50 (2014) no. 2, pp. 539-563 | DOI | MR | Zbl

[BLM03] Boucheron, Stéphane; Lugosi, Gábor; Massart, Pascal Concentration inequalities using the entropy method, Ann. Probab., Volume 31 (2003) no. 3, pp. 1583-1614 | DOI | MR | Zbl

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

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

[CL06] Chung, Fan; Lu, Linyuan Concentration inequalities and martingale inequalities: a survey, Internet Math., Volume 3 (2006) no. 1, pp. 79-127 https://projecteuclid.org:443/euclid.im/1175266369 | DOI | MR | Zbl

[CLPS14] Caracciolo, Sergio; Lucibello, Carlo; Parisi, Giorgio; Sicuro, Gabriele Scaling hypothesis for the Euclidean bipartite matching problem, Phys. Rev. E, Volume 90 (2014) no. 1, 012118

[CLY81] Cheng, Siu Yuen; Li, Peter; Yau, Shing Tung On the upper estimate of the heat kernel of a complete Riemannian manifold, Amer. J. Math., Volume 103 (1981) no. 5, pp. 1021-1063 | DOI | MR | Zbl

[CR17] Charalambous, Nelia; Rowlett, Julie The heat trace for the drifting Laplacian and Schrödinger operators on manifolds, 2017 | arXiv

[CS14] Caracciolo, Sergio; Sicuro, Gabriele One-dimensional Euclidean matching problem: exact solutions, correlation functions, and universality, Phys. Rev. E, Volume 90 (2014) no. 4, 042112

[DSS13] Dereich, Steffen; Scheutzow, Michael; Schottstedt, Reik Constructive quantization: approximation by empirical measures, Ann. Inst. H. Poincaré Probab. Statist., Volume 49 (2013) no. 4, pp. 1183-1203 | DOI | MR | Zbl

[DY95] Dobrić, Vladimir; Yukich, Joseph E. Asymptotics for transportation cost in high dimensions, J. Theoret. Probab., Volume 8 (1995) no. 1, pp. 97-118 | DOI | MR | Zbl

[EKS15] Erbar, Matthias; Kuwada, Kazumasa; Sturm, Karl-Theodor On the equivalence of the entropic curvature-dimension condition and Bochner’s inequality on metric measure spaces, Invent. Math., Volume 201 (2015) no. 3, pp. 993-1071 | DOI | MR | Zbl

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

[FG15] Fournier, Nicolas; Guillin, Arnaud On the rate of convergence in Wasserstein distance of the empirical measure, Probab. Theory Related Fields, Volume 162 (2015) no. 3-4, pp. 707-738 | DOI | MR | Zbl

[GHO18] Goldman, Michael; Huesmann, Martin; Otto, Felix A large-scale regularity theory for the Monge-Ampère equation with rough data and application to the optimal matching problem, 2018 | arXiv

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

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

[Gri06] Grigor’yan, Alexander Heat kernels on weighted manifolds and applications, The ubiquitous heat kernel (Contemp. Math.), Volume 398, American Mathematical Society, 2006, pp. 93-191 | DOI | MR | Zbl

[Hoe63] Hoeffding, Wassily Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., Volume 58 (1963) no. 301, pp. 13-30 http://www.jstor.org/stable/2282952? | DOI | MR

[HS13] Huesmann, Martin; Sturm, Karl-Theodor Optimal transport from Lebesgue to Poisson, Ann. Probab., Volume 41 (2013) no. 4, pp. 2426-2478 | DOI | MR | Zbl

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

[JKO98] Jordan, Richard; Kinderlehrer, David; Otto, Felix The variational formulation of the Fokker-Planck equation, SIAM J. Math. Anal., Volume 29 (1998) no. 1, pp. 1-17 | DOI | MR | Zbl

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

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

[MS67] McKean, H. P. Jr.; Singer, I. M. Curvature and the eigenvalues of the Laplacian, J. Differential Geometry, Volume 1 (1967) no. 1, pp. 43-69 http://projecteuclid.org/euclid.jdg/1214427880 | DOI | MR | Zbl

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

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

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

[SC10] Saloff-Coste, Laurent The heat kernel and its estimates, Probabilistic approach to geometry (Adv. Stud. Pure Math.), Volume 57, Math. Soc. Japan, Tokyo, 2010, pp. 405-436 | DOI | MR | Zbl

[ST98] Stroock, Daniel W.; Turetsky, James Upper bounds on derivatives of the logarithm of the heat kernel, Comm. Anal. Geom., Volume 6 (1998) no. 4, pp. 669-685 | DOI | MR | Zbl

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

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

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

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

[WB17] Weed, Jonathan; Bach, Francis Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance, 2017 | arXiv | Zbl

[ZLJ16] Zhang, Huichun; Li, Huaiqian; Jiang, Renjin Heat kernel bounds on metric measure spaces and some applications, Potential Anal., Volume 44 (2016) no. 3, pp. 601-627 | MR | Zbl

Cité par Sources :