Sharp bounds on the rate of convergence of the empirical covariance matrix

Radosław Adamczak; Alexander E. Litvak; Alain Pajor; Nicole Tomczak-Jaegermann

doi:10.1016/j.crma.2010.12.014

Functional Analysis/Probability Theory

Sharp bounds on the rate of convergence of the empirical covariance matrix
[Ordre asymptotique des valeurs singulières extrêmes de la matrice de covariance empirique]

Présenté par : Gilles Pisier

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

¹ Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland
² Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, Canada T6G 2G1
³ Équipe d'analyse et mathématiques appliquées, université Paris Est, 5, boulevard Descartes, Champs-sur-Marne, 77454 Marne-la-Vallee cedex 2, France

Comptes Rendus. Mathématique, Volume 349 (2011) no. 3-4, pp. 195-200.

Résumé
Abstract

Soient $X_{1}, \dots, X_{N} \in R^{n}$ des vecteurs aléatoires indépendants centrés, de matrice de covariance l'identité et à densité log-concave. On démontre qu'avec une grande probabilité, on a

\sup_{x \in S^{n - 1}} | \frac{1}{N} \sum_{i = 1}^{N} (| 〈 X_{i}, x 〉 |^{2} - E | 〈 X_{i}, x 〉 |^{2}) | ⩽ C \sqrt{\frac{n}{N}},

où

C > 0

est une constante numérique. Ce résultat reste vrai dans le cadre beaucoup plus général où les formes linéaires

{(〈 X_{i}, x 〉)}_{i ⩽ N}, x \in S^{n - 1}

et les normes euclidiennes

{(| X_{i} | / \sqrt{n})}_{i ⩽ N}

vérifient des inégalités de type sous-exponentiel. Il en résulte que si A désigne la matrice dont les colonnes sont

(X_{i})

, alors avec grande probabilité, les valeurs singulières extrêmes

λ_{\min}

et

λ_{\max}

de

A A^{⊤}

vérifient

1 - C \sqrt{\frac{n}{N}} ⩽ \frac{λ_{\min}}{N} ⩽ \frac{λ_{\max}}{N} ⩽ 1 + C \sqrt{\frac{n}{N}}

, ce qui est une version quantitative du théorème de Bai–Yin (Z.D. Bai, Y.Q. Yin, 1993 [4]) bien connu pour les matrices aléatoires à coefficients i.i.d.

Let $X_{1}, \dots, X_{N} \in R^{n}$ be independent centered random vectors with log-concave distribution and with the identity as covariance matrix. We show that with overwhelming probability one has

\sup_{x \in S^{n - 1}} | \frac{1}{N} \sum_{i = 1}^{N} (| 〈 X_{i}, x 〉 |^{2} - E | 〈 X_{i}, x 〉 |^{2}) | ⩽ C \sqrt{\frac{n}{N}},

where C is an absolute positive constant. This result is valid in a more general framework when the linear forms

{(〈 X_{i}, x 〉)}_{i ⩽ N}, x \in S^{n - 1}

and the Euclidean norms

{(| X_{i} | / \sqrt{n})}_{i ⩽ N}

exhibit uniformly a sub-exponential decay. As a consequence, if A denotes the random matrix with columns

(X_{i})

, then with overwhelming probability, the extremal singular values

λ_{\min}

and

λ_{\max}

of

A A^{⊤}

satisfy the inequalities

1 - C \sqrt{\frac{n}{N}} ⩽ \frac{λ_{\min}}{N} ⩽ \frac{λ_{\max}}{N} ⩽ 1 + C \sqrt{\frac{n}{N}}

which is a quantitative version of Bai–Yin theorem (Z.D. Bai, Y.Q. Yin, 1993 [4]) known for random matrices with i.i.d. entries.

Reçu le : 2010-11-20
Accepté le : 2010-12-21
Publié le : 2011-01-06

DOI : 10.1016/j.crma.2010.12.014

Affiliations des auteurs :

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

¹ Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland
² Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, Canada T6G 2G1
³ Équipe d'analyse et mathématiques appliquées, université Paris Est, 5, boulevard Descartes, Champs-sur-Marne, 77454 Marne-la-Vallee cedex 2, France

@article{CRMATH_2011__349_3-4_195_0,
     author = {Rados{\l}aw Adamczak and Alexander E. Litvak and Alain Pajor and Nicole Tomczak-Jaegermann},
     title = {Sharp bounds on the rate of convergence of the empirical covariance matrix},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {195--200},
     publisher = {Elsevier},
     volume = {349},
     number = {3-4},
     year = {2011},
     doi = {10.1016/j.crma.2010.12.014},
     language = {en},
}

TY  - JOUR
AU  - Radosław Adamczak
AU  - Alexander E. Litvak
AU  - Alain Pajor
AU  - Nicole Tomczak-Jaegermann
TI  - Sharp bounds on the rate of convergence of the empirical covariance matrix
JO  - Comptes Rendus. Mathématique
PY  - 2011
SP  - 195
EP  - 200
VL  - 349
IS  - 3-4
PB  - Elsevier
DO  - 10.1016/j.crma.2010.12.014
LA  - en
ID  - CRMATH_2011__349_3-4_195_0
ER  -

%0 Journal Article
%A Radosław Adamczak
%A Alexander E. Litvak
%A Alain Pajor
%A Nicole Tomczak-Jaegermann
%T Sharp bounds on the rate of convergence of the empirical covariance matrix
%J Comptes Rendus. Mathématique
%D 2011
%P 195-200
%V 349
%N 3-4
%I Elsevier
%R 10.1016/j.crma.2010.12.014
%G en
%F CRMATH_2011__349_3-4_195_0

Radosław Adamczak; Alexander E. Litvak; Alain Pajor; Nicole Tomczak-Jaegermann. Sharp bounds on the rate of convergence of the empirical covariance matrix. Comptes Rendus. Mathématique, Volume 349 (2011) no. 3-4, pp. 195-200. doi : 10.1016/j.crma.2010.12.014. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2010.12.014/

Bibliographie
Cité par

[1] R. Adamczak; A.E. Litvak; A. Pajor; N. Tomczak-Jaegermann Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles, J. Amer. Math. Soc., Volume 234 (2010), pp. 535-561

[2] G. Aubrun Random points in the unit ball of $ℓ_{p}^{n}$ , Positivity, Volume 10 (2006), pp. 755-759

[3] G. Aubrun Sampling convex bodies: a random matrix approach, Proc. Amer. Math. Soc., Volume 135 (2007), pp. 1293-1303

[4] Z.D. Bai; Y.Q. Yin Limit of the smallest eigenvalue of a large dimensional sample covariance matrix, Ann. Probab., Volume 21 (1993), pp. 1275-1294

[5] R. Kannan; L. Lovász; M. Simonovits Isoperimetric problems for convex bodies and a localization lemma, Discrete Comput. Geom., Volume 13 (1995) no. 3–4, pp. 541-559

[6] R. Kannan; L. Lovász; M. Simonovits Random walks and $O^{(} n^{5})$ volume algorithm for convex bodies, Random Structures Algorithms, Volume 2 (1997) no. 1, pp. 1-50

[7] G. Paouris Concentration of mass on convex bodies, Geom. Funct. Anal., Volume 16 (2006) no. 5, pp. 1021-1049

Cité par Sources :

^☆ The research was conducted while the authors participated in the Thematic Program on Asymptotic Geometric Analysis at the Fields Institute in Toronto in Fall 2010.

Commentaires - Politique