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

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

Published 2010-12-01, updated 2012-10-30Version 3

Let $X_1,..., 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 at least $1 - 3 \exp(-c\sqrt{n}\r)$ one has $ \sup_{x\in S^{n-1}} \Big|\frac{1/N}\sum_{i=1}^N (|<X_i, x>|^2 - \E|<X_i, x>|^2\r)\Big| \leq 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\leq N, x\in S^{n-1}}$ and the Euclidean norms $(|X_i|/\sqrt n)_{i\leq 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 $\lambda_{\rm min}$ and $\lambda_{\rm max}$ of $AA^\top$ satisfy the inequalities $ 1 - C\sqrt{{n/N}} \le {\lambda_{\rm min}/N} \le \frac{\lambda_{\rm max}/N} \le 1 + C\sqrt{{n/N}} $ which is a quantitative version of Bai-Yin theorem \cite{BY} known for random matrices with i.i.d. entries.