Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles

Adamczak, Radosław¹ ; Litvak, Alexander² ; Pajor, Alain³ ; Tomczak-Jaegermann, Nicole²

¹ Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland
² Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta T6G 2G1, Canada
³ Université Paris-Est, Équipe d’Analyse et Mathématiques Appliquées, 5, boulevard Descartes, Champs sur Marne, 77454 Marne-la-Vallée, Cedex 2, France

Journal of the American Mathematical Society, Tome 23 (2010) no. 2, pp. 535-561

Résumé

Let $K$ be an isotropic convex body in $\mathbb {R}^n$. Given $\varepsilon >0$, how many independent points $X_i$ uniformly distributed on $K$ are needed for the empirical covariance matrix to approximate the identity up to $\varepsilon$ with overwhelming probability? Our paper answers this question posed by Kannan, Lovász, and Simonovits. More precisely, let $X\in \mathbb {R}^n$ be a centered random vector with a log-concave distribution and with the identity as covariance matrix. An example of such a vector $X$ is a random point in an isotropic convex body. We show that for any $\varepsilon >0$, there exists $C(\varepsilon )>0$, such that if $N\sim C(\varepsilon ) n$ and $(X_i)_{i\le N}$ are i.i.d. copies of $X$, then $\Big \|\frac {1}{N}\sum _{i=1}^N X_i\otimes X_i - \operatorname {Id}\Big \| \le \varepsilon ,$ with probability larger than $1-\exp (-c\sqrt n)$.

Détail

DOI : 10.1090/S0894-0347-09-00650-X

Bibliographie

[1] Aubrun, Guillaume Sampling convex bodies: a random matrix approach Proc. Amer. Math. Soc. 2007 1293 1303

[2] Bai, Z. D., Yin, Y. Q. Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix Ann. Probab. 1993 1275 1294

[3] Borell, C. Convex set functions in 𝑑-space Period. Math. Hungar. 1975 111 136

[4] Borell, Christer The Brunn-Minkowski inequality in Gauss space Invent. Math. 1975 207 216

[5] Bourgain, Jean Random points in isotropic convex sets 1999 53 58

[6] Davidson, Kenneth R., Szarek, Stanislaw J. Local operator theory, random matrices and Banach spaces 2001 317 366

[7] Giannopoulos, A., Hartzoulaki, M., Tsolomitis, A. Random points in isotropic unconditional convex bodies J. London Math. Soc. (2) 2005 779 798

[8] Giannopoulos, A. A., Milman, V. D. Concentration property on probability spaces Adv. Math. 2000 77 106

[9] Guã©Don, Olivier, Rudelson, Mark 𝐿_{𝑝}-moments of random vectors via majorizing measures Adv. Math. 2007 798 823

[10] Kannan, Ravi, Lovã¡Sz, Lã¡Szlã³, Simonovits, Miklã³S Random walks and an 𝑂*(𝑛⁵) volume algorithm for convex bodies Random Structures Algorithms 1997 1 50

[11] Klein, T., Rio, E. Concentration around the mean for maxima of empirical processes Ann. Probab. 2005 1060 1077

[12] Ledoux, Michel On Talagrand’s deviation inequalities for product measures ESAIM Probab. Statist. 1995/97 63 87

[13] Ledoux, Michel The concentration of measure phenomenon 2001

[14] Ledoux, Michel, Talagrand, Michel Probability in Banach spaces 1991

[15] Mendelson, Shahar On weakly bounded empirical processes Math. Ann. 2008 293 314

[16] Mendelson, Shahar, Pajor, Alain On singular values of matrices with independent rows Bernoulli 2006 761 773

[17] Mendelson, Shahar, Pajor, Alain, Tomczak-Jaegermann, Nicole Reconstruction and subgaussian operators in asymptotic geometric analysis Geom. Funct. Anal. 2007 1248 1282

[18] Milman, V. D., Pajor, A. Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed 𝑛-dimensional space 1989 64 104

[19] Paouris, G. Concentration of mass on convex bodies Geom. Funct. Anal. 2006 1021 1049

[20] Rudelson, M. Random vectors in the isotropic position J. Funct. Anal. 1999 60 72

[21] Schneider, Rolf Convex bodies: the Brunn-Minkowski theory 1993

[22] Talagrand, Michel New concentration inequalities in product spaces Invent. Math. 1996 505 563

[23] Van Der Vaart, Aad W., Wellner, Jon A. Weak convergence and empirical processes 1996