Covariance estimation for distributions with $2+\epsilon$ moments

Abstract

We study the minimal sample size N=N(n) that suffices to estimate the covariance matrix of an n-dimensional distribution by the sample covariance matrix in the operator norm, with an arbitrary fixed accuracy. We establish the optimal bound N=O(n) for every distribution whose k-dimensional marginals have uniformly bounded $2+\epsilon$ moments outside the sphere of radius $O(\sqrt{k})$. In the specific case of log-concave distributions, this result provides an alternative approach to the Kannan-Lovasz-Simonovits problem, which was recently solved by Adamczak et al. [J. Amer. Math. Soc. 23 (2010) 535-561]. Moreover, a lower estimate on the covariance matrix holds under a weaker assumption - uniformly bounded $2+\epsilon$ moments of one-dimensional marginals. Our argument consists of randomizing the spectral sparsifier, a deterministic tool developed recently by Batson, Spielman and Srivastava [SIAM J. Comput. 41 (2012) 1704-1721]. The new randomized method allows one to control the spectral edges of the sample covariance matrix via the Stieltjes transform evaluated at carefully chosen random points.

arXiv commentPublished in at http://dx.doi.org/10.1214/12-AOP760 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

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

Cited by in corpus (11)

• Structured Random Matrices
• Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices
• Generalized Canonical Correlation Analysis for Classification
• Almost sure convergence of the largest and smallest eigenvalues of high-dimensional sample correlation matrices
• Lower bounds on the smallest eigenvalue of a sample covariance matrix
• On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence
• The smallest singular value of a shifted $d$-regular random square matrix
• The relative effects of dimensionality and multiplicity of hypotheses on the F-test in linear regression
• Covariance Matrix Estimation from Linearly-Correlated Gaussian Samples
• Estimating covariance and precision matrices along subspaces
• Concentration and moment inequalities for sums of independent heavy-tailed random matrices