On optimal matching of Gaussian samples

M. Ledoux

Zapiski Nauchnykh Seminarov POMI, Probability and statistics. Part 25, Tome 457 (2017), pp. 226-264

Résumé

Let $X_1,\dots,X_n$ be independent random variables with common distribution the standard Gaussian measure $\mu$ on $\mathbb R^2$, and let $\mu_n=\frac1n\sum_{i=1}^n\delta_{X_i}$ be the associated empirical measure. We show that, for some numerical constant $C>0$, $$ \frac1C\frac{\log n}n\leq\mathbb E(\mathrm W_2^2(\mu_n,\mu))\leq C\frac{(\log n)^2}n $$ where $\mathrm W_2$ is the quadratic Kantorovich metric, and conjecture that the left-hand side provides the correct order. The proof is based on the recent PDE and mass transportation approach developed by L. Ambrosio, F. Stra and D. Trevisan.

Bibliographie

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

[2] L. Ambrosio, N. Gigli, G. Savaré, “Bakry–Émery curvature-dimension condition and Riemannian Ricci curvature bounds”, Ann. Probab., 43 (2015), 339–404 | DOI | MR | Zbl

[3] L. Ambrosio, A. Mondino, G. Savaré, Nonlinear diffusion equations and curvature conditions in metric measure spaces, 2015 | MR

[4] L. Ambrosio, F. Stra, D. Trevisan, “A PDE approach to a $2$-dimensional matching problem”, Probab. Theory Related Fields (to appear)

[5] D. Bakry, “Étude des transformations de Riesz sur les variétés riemanniennes à courbure de Ricci minorée”, Séminaire de Probabilités, XXI, Lecture Notes in Math., 1247, Springer, 1987, 137–172 | DOI | MR

[6] D. Bakry, I. Gentil, M. Ledoux, Analysis and Geometry of Markov Diffusion Operators, Grundlehren der mathematischen Wissenschaften, 348, Springer, 2014 | DOI | MR | Zbl

[7] F. Barthe, C. Bordenave, “Combinatorial optimization over two random point sets”, Séminaire de Probabilités, XLV, Lecture Notes Math., 2078, Springer, 2013, 483–535 | DOI | MR | Zbl

[8] S. Bobkov, M. Ledoux, “One-dimensional empirical measures, order statistics, and Kantorovich transport distances”, Memoirs Amer. Math. Soc. (to appear)

[9] E. Boissard, T. Le Gouic, “On the mean speed of convergence of empirical and occupation measures in Wasserstein distance”, Ann. Inst. Henri Poincaré Probab. Stat., 50 (2014), 539–563 | DOI | MR | Zbl

[10] F. Bolley, A. Guillin, C. Villani, “Quantitative concentration inequalities for empirical measures on non-compact spaces”, Probab. Theory Related Fields, 137 (2007), 541–593 | DOI | MR | Zbl

[11] J. Boutet de Monvel, O. Martin, “Almost sure convergence of the minimum bipartite matching functional in Euclidean space”, Combinatorica, 22 (2002), 523–530 | DOI | MR | Zbl

[12] S. Caracciolo, C. Lucibello, G. Parisi, G. Sicuro, “Scaling hypothesis for the Euclidean bipartite matching problem”, Physical Review E, 90 (2014), 012118 | DOI | MR

[13] I. Chavel, A modern introduction in Riemannian Geometry, Cambridge Studies in Advanced Mathematics, 98, 2nd edn., Cambridge University Press, 2006 | MR

[14] E. B. Davies, Heat kernels and spectral theory, Cambridge Tracts in Mathematics, 92, Cambridge University Press, 1989 | MR | Zbl

[15] S. Dereich, M. Scheutzow, R. Schottstedt, “Constructive quantization: approximation by empirical measures”, Ann. Inst. Henri Poincaré Probab. Stat., 49 (2013), 1183–1203 | DOI | MR | Zbl

[16] V. Dobrić, J. Yukich, “Asymptotics for transportation cost in high dimensions”, J. Theoret. Probab., 8 (1995), 97–118 | DOI | MR | Zbl

[17] R. Dudley, “The speed of mean Glivenko-Cantelli convergence”, Ann. Math. Statist., 40 (1968), 40–50 | DOI | MR

[18] 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), 993–1071 | DOI | MR | Zbl

[19] L. Evans, Partial Differential Equations, Graduate Studies in Mathematics, 19, American Mathematical Society, 1998 | MR | Zbl

[20] N. Fournier, A. Guillin, “On the rate of convergence in Wasserstein distance of the empirical measure”, Probab. Theory Related Fields, 162 (2015), 707–738 | DOI | MR | Zbl

[21] M. Hahn, Y. Shao, “An exposition of Talagrand's mini-course on matching theorems”, Probability in Banach spaces, v. 8, Progr. Probab., 30, Birkhäuser, 1992, 3–38 | MR | Zbl

[22] N. Holden, Y. Peres, A. Zhai, Gravitational allocation for uniform points on the sphere, 2017

[23] W. Johnson, G. Schechtman, J. Zinn, “Best constants in moment inequalities for linear combinations of independent and exchangeable random variables”, Ann. Probab., 13 (1985), 234–253 | DOI | MR | Zbl

[24] K. Kuwada, “Duality on gradient estimates and Wasserstein controls”, J. Funct. Anal., 258 (2010), 3758–3774 | DOI | MR | Zbl

[25] T. Leighton, P. Shor, “Tight bounds for minimax grid matching with applications to the average case analysis of algorithms”, Combinatorica, 9 (1989), 161–187 | DOI | MR | Zbl

[26] P.-A. Meyer, “Transformations de Riesz pour les lois gaussiennes”, Séminaire de Probabilités, XV, Lecture Notes in Math., 1059, Springer, 1984, 179–193 | DOI | MR

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

[28] H. P. Rosenthal, “On the subspaces of $L^p$ $(p>2)$ spanned by sequences of independent random variables”, Israel J. Math., 8 (1970), 273–303 | DOI | MR | Zbl

[29] P. Shor, “How to pack better than Best Fit: Tight bounds for average-case on-line bin packing”, Proc. 32nd Annual Symposium on Foundations of Computer Sciences, 1991, 752–759 | DOI

[30] P. Shor, J. Yukich, “Minimax grid matching and empirical measures”, Ann. Probab., 19 (1991), 1338–1348 | DOI | MR | Zbl

[31] M. Talagrand, “Matching random samples in many dimensions”, Ann. App. Probab., 2 (1992), 846–856 | DOI | MR | Zbl

[32] M. Talagrand, “The transportation cost from the uniform measure to the empirical measure in dimension $\geq3$”, Ann. Probab., 22 (1994), 919–959 | DOI | MR | Zbl

[33] M. Talagrand, “Matching theorems and discrepency computations using majorising measures”, J. Amer. Math. Soc., 17 (1994), 455–537 | DOI | MR

[34] M. Talagrand, Upper and Lower Bounds of Stochastic Processes, Modern Surveys in Mathematics, 60, Springer-Verlag, 2014 | MR

[35] N. Varopoulos, “Hardy–Littlewood theory for semi-groups”, J. Funct. Anal., 11 (1985), 240–260 | DOI | MR

[36] C. Villani, Optimal Transport. Old and New, Grundlehren der mathematischen Wissenschaften, 338, Springer, 2009 | DOI | MR | Zbl

[37] F.-Y. Wang, Analysis for Diffusion Processes on Riemannian Manifolds, World Scientific, 2014 | MR | Zbl

[38] J. Yukich, “Some generalizations of the Euclidean two-sample matching problem”, Probability in Banach spaces, v. 8, Progr. Probab., 30, Birkhäuser, 1992, 55–66 | MR | Zbl

[39] J. Yukich, Probability theory of classical Euclidean optimization problems, Lecture Notes in Mathematics, 1675, Springer, 1998 | DOI | MR | Zbl