COVARIANCE ESTIMATION FOR DISTRIBUTIONS WITH 2+ε MOMENTS

• 成果类型: Article
• 署名作者: Srivastava, Nikhil; Vershynin, Roman
• 署名单位: Institute for Advanced Study - USA; University of Michigan System; University of Michigan
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/12-AOP760
• 发表日期: 2013
• 页码: 3081-3111
• 关键词: eigenvalue

摘要

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(root 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.