Covariance Estimation and Sample Complexity

How many samples are needed to estimate a covariance matrix in operator norm, and what the answer says about the curse of dimensionality.

High-Dim StatisticsGraduate⏱ 3 hours9 min readcovariancesample complexityoperator normminimaxshrinkage

4 problems →

AssumesSample Covariance and the Marchenko–Pastur Law

The question

Let $x_1,\dots,x_n$ be i.i.d. mean-zero random vectors in $\R^p$ with covariance $\Sigma$ , and let

\hat\Sigma = \frac1n\sum_{i=1}^n x_ix_i^\top .

$\hat\Sigma$ is unbiased: $\E\hat\Sigma = \Sigma$ . The question is how large $\norm{\hat\Sigma - \Sigma}$ is, in operator norm, as a function of $n$ and $p$ .

Operator norm is the right choice because it is what downstream uses need: it controls the error in every quadratic form $v^\top\hat\Sigma v$ uniformly over $v$ , hence the error in every projection, every eigenvalue (by Weyl's inequality), and every linear predictor.

TheoremOperator-norm rate for sample covariance estimation

Suppose $x_i$ are i.i.d., mean zero, with covariance $\Sigma$ , and that $\ip{x_i}{v}$ is sub-Gaussian with $\norm{\ip{x_i}{v}}_{\psi_2} \le K\norm{\Sigma^{1/2}v}_2$ for all $v$ (which holds for Gaussian data with $K$ absolute). Then there is an absolute constant $C$ such that for every $t\ge0$ , with probability at least $1 - 2e^{-t^2}$ ,

\norm{\hat\Sigma - \Sigma} \le CK^2\norm{\Sigma}\left(\sqrt{\frac{p + t^2}{n}} + \frac{p+t^2}{n}\right).

CorollarySample complexity of covariance estimation

For $\eps \in (0,1)$ , if $n \ge C K^4 p/\eps^2$ then with probability at least $1 - 2e^{-p}$ ,

\norm{\hat\Sigma - \Sigma} \le \eps\norm{\Sigma},

i.e. $(1-\eps)\Sigma \preceq \hat\Sigma \preceq (1+\eps)\Sigma$ when $\Sigma \succ 0$ .

Key idea

$n \asymp p/\eps^2$ . The sample complexity of covariance estimation is linear in the dimension, not exponential. This is worth emphasising because "curse of dimensionality" is often used as though every high-dimensional problem were exponentially hard. Estimating $p(p+1)/2$ covariance parameters to fixed relative accuracy in operator norm takes $O(p)$ samples — each sample carries $p$ numbers, so this is the information-theoretic minimum up to constants.

HeuristicThe curse of dimensionality, stated as an exponent

Heuristic — a reasoning shortcut that predicts the right answer in the regimes discussed here. It is not a proof and can fail outside them.

The phrase covers at least two different phenomena with very different severity, and keeping them apart resolves most confusion:

Parametric estimation in high dimension. Covariance, linear regression, and any model with $O(p)$ effective parameters need $n \asymp p$ samples. Linear in $p$ , and manageable.
Nonparametric estimation in high dimension. Estimating an arbitrary Lipschitz function on $[0,1]^p$ to accuracy $\eps$ needs $n \asymp \eps^{-p}$ samples. Exponential in $p$ , and hopeless beyond small $p$ .

$k$ -nearest neighbours, kernel smoothing and histogram methods are in the second class, which is why they degrade so sharply — see the nearest neighbours page.

Shrinkage

The theorem above says $\hat\Sigma$ is accurate when $n \gg p$ . When it is not, $\hat\Sigma$ is poorly conditioned (the Marchenko–Pastur spread) and can be improved by biasing it towards a well-conditioned target.

PropositionLinear shrinkage strictly improves the sample covariance

Consider $\hat\Sigma_\alpha = (1-\alpha)\hat\Sigma + \alpha\,\hat\mu I_p$ with $\hat\mu = \tr(\hat\Sigma)/p$ and $\alpha\in[0,1]$ . If $\Sigma = I_p$ , then

\E\norm{\hat\Sigma_\alpha - \Sigma}_F^2 = (1-\alpha)^2\,\E\norm{\hat\Sigma - \Sigma}_F^2 + \alpha^2\,p\,\E(\hat\mu - 1)^2 + \text{cross term},

and there exists $\alpha^\star \in (0,1)$ strictly reducing the expected squared Frobenius error whenever $\E\norm{\hat\Sigma - \Sigma}_F^2 > 0$ .

Problems

Sample complexity of covariance estimationNumerical · Intermediate · 30 min Optimal linear shrinkageProof · Advanced · 1 hour Weyl's inequality and eigenvalue perturbationProof · Advanced · 30 min Measure the covariance estimation rateCoding · Intermediate · 1 hour

References

BookMartin J. Wainwright (2019). High-Dimensional Statistics: A Non-Asymptotic ViewpointChapter 6 gives covariance estimation in the generality used here, with matching lower bounds.
PaperRoman Vershynin (2012). How close is the sample covariance matrix to the actual covariance matrix?
PaperOlivier Ledoit and Michael Wolf (2004). A well-conditioned estimator for large-dimensional covariance matricesThe origin of the linear-shrinkage estimator discussed below.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

TheoremOperator-norm rate for sample covariance estimationproof includedFor sub-Gaussian data the sample covariance satisfies an operator-norm error of order sqrt(p/n) + p/n.
CorollarySample complexity of covariance estimationproof includedAchieving relative operator-norm error epsilon requires order p/epsilon^2 samples.
PropositionLinear shrinkage strictly improves the sample covarianceproof includedFor any aspect ratio there is a shrinkage intensity whose expected squared error is strictly below that of the unshrunk estimator.
HeuristicThe curse of dimensionality, stated as an exponentThe number of samples needed grows linearly in the dimension for covariance estimation and exponentially for nonparametric estimation, and conflating the two causes most confusion about the phrase.

Problems (4)

All problems