How Close is the Sample Covariance Matrix to the Actual Covariance Matrix?

By Roman Vershynin. 2010

302 citations recorded by the source corpus.

Given a probability distribution in ℝn with general (nonwhite) covariance, a classical estimator of the covariance matrix is the sample covariance matrix obtained from a sample of N independent points. What is the optimal sample size N=N(n) that guarantees estimation with a fixed accuracy in the operator norm? Suppose that the distribution is supported in a centered Euclidean ball of radius $O(\sqrt{n})$. We conjecture that the optimal sample size is N=O(n) for all distributions with finite fourth moment, and we prove this up to an iterated logarithmic factor. This problem is motivated by the optimal theorem of Rudelson (J. Funct. Anal. 164:60–72, 1999), which states that N=O(nlog n) for distributions with finite second moment, and a recent result of Adamczak et al. (J. Am. Math. Soc. 234:535–561, 2010), which guarantees that N=O(n) for subexponential distributions.

Subfields: Computational Mechanics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/66e93ac2e955d8460dc0806af53fce15e501f1df

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Memory Limited, Streaming PCA (2013, background): “In this regime, it is well-known that batch-PCA is asymptotically consistent (hence recovering A up to unitary transformations) with number of samples scaling as n = O(p) Vershynin (2010b). It is interesting to note that in this high-dimensional regime, the signal-to-noise ratio quickly approaches z”
Semi-supervised inference: General theory and estimation of means (2016, background): “39 in Vershynin (2012b)) We have the following concentration inequality,”
Covariance estimation for distributions with 2+ε moments (2011, methodology): “The second author of the present paper speculated in [16] that N =O(n) should hold for a much wider class of distributions than sub-exponential, perhaps for all distributions with 2+ ε moments.”
Streaming PCA and Subspace Tracking: The Missing Data Case (2018, background): “Moreover, in this case, Ûn produces an order-wise near-optimal estimate to U∗ for a large family of distributions [46].”
Intermittent process analysis with scattering moments (2013, background): “θ in (64) gives an accurate estimation of the inverse of the covariance matrix of SYθ whose dimension is p. For large pit is suﬃcient to have a number nof independent realizations such that n≃ plog2 p[38]. This condition limits the maximum value of J. The Generalized Method of Simulated Moments can ”
Sample covariance matrices of heavy-tailed distributions (2016, result): “lassical works [33] and [3] regarding almost sure convergence of appropriately normalized singular values when the coordinates of the underlying distributions are i.i.d.; as well as more recent works [22, 14, 18, 25, 9, 1, 2, 29, 19, 26, 20, 17, 28, 11, 10, 31, 32, 21, 27, 8]. For a more comprehensi”
Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients (2015, background): “mini-batch size, but by assuming suitable data distributions, it is possible to obtain explicit bounds; see for example [23, 4].”
Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression (2018, background): “2 of Vershynin (2012), it is easy to see that RIPn(k) can be bounded by a finite maximum as”
Detecting Confounding in Multivariate Linear Models via Spectral Analysis (2017, result): “This observation for moderate dimensions is somehow in contrast to the asymptotic statement that the sample size required for non-regularized estimation of covariance matrices (given some fixed error bound in terms of the operator norm) grows only withO(d log d) [32, 33] for any distributionwith fin”