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

HTML articles powered by AMS MathViewer

- by Radosław Adamczak, Alexander E. Litvak, Alain Pajor and Nicole Tomczak-Jaegermann PDF
- J. Amer. Math. Soc.
**23**(2010), 535-561 Request permission

## Abstract:

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)$.## References

- R. Adamczak, A. E. Litvak, A. Pajor, and N. Tomczak-Jaegermann, Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, preprint; available at http://arxiv.org/abs/0904.4723.
- Guillaume Aubrun,
*Sampling convex bodies: a random matrix approach*, Proc. Amer. Math. Soc.**135**(2007), no. 5, 1293–1303. MR**2276637**, DOI 10.1090/S0002-9939-06-08615-1 - G. Aubrun, Private communication.
- Z. D. Bai and Y. Q. Yin,
*Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix*, Ann. Probab.**21**(1993), no. 3, 1275–1294. MR**1235416** - C. Borell,
*Convex set functions in $d$-space*, Period. Math. Hungar.**6**(1975), no. 2, 111–136. MR**404559**, DOI 10.1007/BF02018814 - Christer Borell,
*The Brunn-Minkowski inequality in Gauss space*, Invent. Math.**30**(1975), no. 2, 207–216. MR**399402**, DOI 10.1007/BF01425510 - Jean Bourgain,
*Random points in isotropic convex sets*, Convex geometric analysis (Berkeley, CA, 1996) Math. Sci. Res. Inst. Publ., vol. 34, Cambridge Univ. Press, Cambridge, 1999, pp. 53–58. MR**1665576** - Kenneth R. Davidson and Stanislaw J. Szarek,
*Local operator theory, random matrices and Banach spaces*, Handbook of the geometry of Banach spaces, Vol. I, North-Holland, Amsterdam, 2001, pp. 317–366. MR**1863696**, DOI 10.1016/S1874-5849(01)80010-3 - A. Giannopoulos, M. Hartzoulaki, and A. Tsolomitis,
*Random points in isotropic unconditional convex bodies*, J. London Math. Soc. (2)**72**(2005), no. 3, 779–798. MR**2190337**, DOI 10.1112/S0024610705006897 - A. A. Giannopoulos and V. D. Milman,
*Concentration property on probability spaces*, Adv. Math.**156**(2000), no. 1, 77–106. MR**1800254**, DOI 10.1006/aima.2000.1949 - Olivier Guédon and Mark Rudelson,
*$L_p$-moments of random vectors via majorizing measures*, Adv. Math.**208**(2007), no. 2, 798–823. MR**2304336**, DOI 10.1016/j.aim.2006.03.013 - Ravi Kannan, László Lovász, and Miklós Simonovits,
*Random walks and an $O^*(n^5)$ volume algorithm for convex bodies*, Random Structures Algorithms**11**(1997), no. 1, 1–50. MR**1608200**, DOI 10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X - T. Klein and E. Rio,
*Concentration around the mean for maxima of empirical processes*, Ann. Probab.**33**(2005), no. 3, 1060–1077. MR**2135312**, DOI 10.1214/009117905000000044 - Michel Ledoux,
*On Talagrand’s deviation inequalities for product measures*, ESAIM Probab. Statist.**1**(1995/97), 63–87. MR**1399224**, DOI 10.1051/ps:1997103 - Michel Ledoux,
*The concentration of measure phenomenon*, Mathematical Surveys and Monographs, vol. 89, American Mathematical Society, Providence, RI, 2001. MR**1849347**, DOI 10.1090/surv/089 - Michel Ledoux and Michel Talagrand,
*Probability in Banach spaces*, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 23, Springer-Verlag, Berlin, 1991. Isoperimetry and processes. MR**1102015**, DOI 10.1007/978-3-642-20212-4 - Shahar Mendelson,
*On weakly bounded empirical processes*, Math. Ann.**340**(2008), no. 2, 293–314. MR**2368981**, DOI 10.1007/s00208-007-0152-9 - Shahar Mendelson and Alain Pajor,
*On singular values of matrices with independent rows*, Bernoulli**12**(2006), no. 5, 761–773. MR**2265341**, DOI 10.3150/bj/1161614945 - Shahar Mendelson, Alain Pajor, and Nicole Tomczak-Jaegermann,
*Reconstruction and subgaussian operators in asymptotic geometric analysis*, Geom. Funct. Anal.**17**(2007), no. 4, 1248–1282. MR**2373017**, DOI 10.1007/s00039-007-0618-7 - V. D. Milman and A. Pajor,
*Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed $n$-dimensional space*, Geometric aspects of functional analysis (1987–88), Lecture Notes in Math., vol. 1376, Springer, Berlin, 1989, pp. 64–104. MR**1008717**, DOI 10.1007/BFb0090049 - A. Pajor and L. Pastur, On the Limiting Empirical Measure of the sum of rank one matrices with log-concave distribution,
*Studia Math.*to appear. - G. Paouris,
*Concentration of mass on convex bodies*, Geom. Funct. Anal.**16**(2006), no. 5, 1021–1049. MR**2276533**, DOI 10.1007/s00039-006-0584-5 - M. Rudelson,
*Random vectors in the isotropic position*, J. Funct. Anal.**164**(1999), no. 1, 60–72. MR**1694526**, DOI 10.1006/jfan.1998.3384 - Rolf Schneider,
*Convex bodies: the Brunn-Minkowski theory*, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, Cambridge, 1993. MR**1216521**, DOI 10.1017/CBO9780511526282 - Michel Talagrand,
*New concentration inequalities in product spaces*, Invent. Math.**126**(1996), no. 3, 505–563. MR**1419006**, DOI 10.1007/s002220050108 - Aad W. van der Vaart and Jon A. Wellner,
*Weak convergence and empirical processes*, Springer Series in Statistics, Springer-Verlag, New York, 1996. With applications to statistics. MR**1385671**, DOI 10.1007/978-1-4757-2545-2

## Additional Information

**Radosław Adamczak**- Affiliation: Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland
- Email: radamcz@mimuw.edu.pl
**Alexander E. Litvak**- Affiliation: Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta T6G 2G1, Canada
- MR Author ID: 367520
- Email: alexandr@math.ualberta.ca
**Alain Pajor**- Affiliation: 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
- Email: Alain.Pajor@univ-mlv.fr
**Nicole Tomczak-Jaegermann**- Affiliation: Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta T6G 2G1, Canada
- MR Author ID: 173265
- Email: nicole.tomczak@ualberta.ca
- Received by editor(s): December 4, 2008
- Published electronically: October 9, 2009
- Additional Notes: Work on this paper began when the first author held a postdoctoral position at the Department of Mathematical and Statistical Sciences, University of Alberta in Edmonton, Alberta. The position was partially sponsored by the Pacific Institute for the Mathematical Sciences.

The fourth author holds the Canada Research Chair in Geometric Analysis - © Copyright 2009 American Mathematical Society
- Journal: J. Amer. Math. Soc.
**23**(2010), 535-561 - MSC (2000): Primary 52A20, 46B09, 52A21; Secondary 15A52, 60E15
- DOI: https://doi.org/10.1090/S0894-0347-09-00650-X
- MathSciNet review: 2601042