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

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

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

Adamczak, Radosław ¹ ; Litvak, Alexander E.² ; 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, 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, Tome 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}

λ_{\max}

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}

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 :

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

@article{CRMATH_2011__349_3-4_195_0,
     author = {Adamczak, Rados{\l}aw and Litvak, Alexander E. and Pajor, Alain and Tomczak-Jaegermann, Nicole},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2010.12.014/}
}

TY  - JOUR
AU  - Adamczak, Radosław
AU  - Litvak, Alexander E.
AU  - Pajor, Alain
AU  - Tomczak-Jaegermann, Nicole
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2010.12.014/
DO  - 10.1016/j.crma.2010.12.014
LA  - en
ID  - CRMATH_2011__349_3-4_195_0
ER  -

%0 Journal Article
%A Adamczak, Radosław
%A Litvak, Alexander E.
%A Pajor, Alain
%A Tomczak-Jaegermann, Nicole
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2010.12.014/
%R 10.1016/j.crma.2010.12.014
%G en
%F CRMATH_2011__349_3-4_195_0

Adamczak, Radosław; Litvak, Alexander E.; Pajor, Alain; Tomczak-Jaegermann, Nicole. Sharp bounds on the rate of convergence of the empirical covariance matrix. Comptes Rendus. Mathématique, Tome 349 (2011) no. 3-4, pp. 195-200. doi : 10.1016/j.crma.2010.12.014. http://www.numdam.org/articles/10.1016/j.crma.2010.12.014/

Bibliographie
Cité par

[1] Adamczak, R.; Litvak, A.E.; Pajor, A.; Tomczak-Jaegermann, N. 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] Aubrun, G. Random points in the unit ball of $ℓ_{p}^{n}$ , Positivity, Volume 10 (2006), pp. 755-759

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

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

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

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

[7] Paouris, G. 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.