Quantitative estimates of the convergence of the empirical covariance matrix in Log-concave Ensembles

2009/03/31 by Radosław Adamczak, Alexander E. Litvak, Alain Pajor +1
Mathematics · #math.PR #math.FA #msc:52A20 #msc:46B09 #msc:52A21 #msc:15A52 #msc:60E15

paper · pdf · doi:10.1090/s0894-0347-09-00650-x

Exposition changed, several explanatory remarks added, some proofs simplified

arxiv created 2009/08/27 · arxiv updated 2015/05/13

Abstract

Let K be an isotropic convex body in \Rⁿ. Given \eps>0, how many independent points X_i uniformly distributed on K are needed for the empirical covariance matrix to approximate the identity up to \eps with overwhelming probability? Our paper answers this question posed by Kannan, Lovasz and Simonovits. More precisely, let X∈\Rⁿ 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 \eps>0, there exists C(\eps)>0, such that if N∼ C(\eps) n and (X_i)_{i≤ N} are i.i.d. copies of X, then ‖(1)/(N)∑_i=1^N X_i⊗ X_i - \Id‖ ≤ ε, with probability larger than 1-exp(-c√ n).

Cited by

• Algorithms with Polynomially-Improved Approximation Factors for the 2 → q Norm, and Applications