|
Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles
Author(s):
Radosław
Adamczak;
Alexander
E.
Litvak;
Alain
Pajor;
Nicole
Tomczak-Jaegermann
Journal:
J. Amer. Math. Soc.
23
(2010),
535-561.
MSC (2000):
Primary 52A20, 46B09, 52A21;
Secondary 15A52, 60E15
Posted:
October 9, 2009
MathSciNet review:
2601042
Retrieve article in:
PDF
Abstract |
References |
Similar articles |
Additional information
Abstract:
Let be an isotropic convex body in . Given , how many independent points uniformly distributed on are needed for the empirical covariance matrix to approximate the identity up to with overwhelming probability? Our paper answers this question posed by Kannan, Lovász, and Simonovits. More precisely, let be a centered random vector with a log-concave distribution and with the identity as covariance matrix. An example of such a vector is a random point in an isotropic convex body. We show that for any , there exists , such that if and are i.i.d. copies of , then with probability larger than .
References:
-
- 1.
- 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.
- 2.
- G. Aubrun, Sampling convex bodies: A random matrix approach. Proc. Amer. Math. Soc. 135 (2007), 1293-1303. MR 2276637 (2007k:52005)
- 3.
- G. Aubrun, Private communication.
- 4.
- Z. D. Bai and Y. Q. Yin, Limit of the smallest eigenvalue of a large dimensional sample covariance matrix, Ann. Probab. 21 (1993), 1275-1294. MR 1235416 (94j:60060)
- 5.
- C. Borell, Convex set functions in
-space, Math. Hungar. 6 (1975), 111-136. MR 0404559 (53:8359) - 6.
- C. Borell, The Brunn-Minkowski inequality in Gauss space, Invent. Math. 30 (1975), 207-216. MR 0399402 (53:3246)
- 7.
- J. Bourgain, Random points in isotropic convex sets. In: ``Convex geometric analysis, Berkeley, CA, 1996'', Math. Sci. Res. Inst. Publ., Vol. 34, 53-58, Cambridge Univ. Press, Cambridge (1999). MR 1665576 (99m:60021)
- 8.
- K. R. Davidson and S. Szarek, Local operator theory, random matrices and Banach spaces. In ``Handbook on the Geometry of Banach spaces,'' Volume 1, 317-366; W. B. Johnson, J. Lindenstrauss, eds., Elsevier Science, 2001. MR 1863696 (2004f:47002a)
- 9.
- A. A. Giannopoulos, M. Hartzoulaki, and A. Tsolomitis, Random points in isotropic unconditional convex bodies. J. London Math. Soc. 72 (2005), 779-798. MR 2190337 (2006i:60012)
- 10.
- A. A. Giannopoulos and V. D. Milman, Concentration property on probability spaces. Adv. Math. 156 (2000), 77-106. MR 1800254 (2001m:28001)
- 11.
- O. Guédon and M. Rudelson,
-moments of random vectors via majorizing measures. Adv. Math. 208, no. 2 (2007), 798-823. MR 2304336 (2008m:46017) - 12.
- R. Kannan, L. Lovász, and M. Simonovits, Random walks and an
volume algorithm for convex bodies, Random structures and algorithms 11(1) (1997), 1-50. MR 1608200 (99h:68078) - 13.
- T. Klein and E. Rio, Concentration around the mean for maxima of empirical processes. Ann. Probab. 33 (2005), 1060-1077. MR 2135312 (2006c:60022)
- 14.
- M. Ledoux, On Talagrand's deviation inequalities for product measures. ESAIM: Probability and Statistics 1 (1996), 63-87. MR 1399224 (97j:60005)
- 15.
- M. Ledoux, The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI, 2001. MR 1849347 (2003k:28019)
- 16.
- M. Ledoux and M. Talagrand, Probability in Banach Spaces. Isoperimetry and processes, Volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3). Springer-Verlag, Berlin, 1991. MR 1102015 (93c:60001)
- 17.
- S. Mendelson, On weakly bounded empirical processes. Math. Ann. 340, no. 2 (2008), 293-314. MR 2368981 (2009d:62068)
- 18.
- S. Mendelson and A. Pajor, On singular values of matrices with independent rows, Bernoulli 12 (2006), 761-773. MR 2265341 (2008a:60160)
- 19.
- S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann, Reconstruction and subgaussian operators in asymptotic geometric analysis. Geom. Funct. Anal., 17 (2007), 1248-1282. MR 2373017 (2009j:46024)
- 20.
- V. Milman and A. Pajor, Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed
-dimensional space. Geom. Funct. Anal. (1987-88), 64-104, Lecture Notes in Math., 1376, Springer, Berlin, 1989. MR 1008717 (90g:52003) - 21.
- 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.
- 22.
- G. Paouris, Concentration of mass on convex bodies. Geom. Funct. Anal. 16, no. 5 (2006), 1021-1049. MR 2276533 (2007k:52009)
- 23.
- M. Rudelson, Random vectors in the isotropic position. J. Funct. Anal. 164, no. 1 (1999), 60-72. MR 1694526 (2000c:60059)
- 24.
- R. Schneider, Convex bodies: The Brunn-Minkowski theory. Encyclopedia of Mathematics and its Applications, 44. Cambridge University Press, Cambridge, 1993. MR 1216521 (94d:52007)
- 25.
- M. Talagrand, New concentration inequalities in product spaces. Invent. Math. 126, no. 3 (1996), 505-563. MR 1419006 (99b:60030)
- 26.
- A. W. van der Vaart and J.A. Wellner, Weak convergence and empirical processes. With applications to statistics. Springer Series in Statistics. Springer-Verlag, New York, 1996. MR 1385671 (97g:60035)
Similar Articles:
Retrieve articles in Journal of the American Mathematical Society
with
MSC (2000):
52A20, 46B09, 52A21,
15A52, 60E15
Retrieve articles in all Journals with
MSC (2000):
52A20, 46B09, 52A21,
15A52, 60E15
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
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
Email:
nicole.tomczak@ualberta.ca
DOI:
10.1090/S0894-0347-09-00650-X
PII:
S 0894-0347(09)00650-X
Keywords:
Convex bodies,
log-concave measures,
isotropic measures,
random matrices,
norm of random matrices,
uniform laws of large numbers,
approximation of covariance matrices
Received by editor(s):
December 4, 2008
Posted:
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 of article:
Copyright
2009,
American Mathematical Society
|