Sample complexity of covariance estimation

NumericalIntermediate⏱ 30 minHigh-Dim Statisticscovariancesample complexityoperator norm

Problem

The operator-norm bound gives $\|\hat\Sigma-\Sigma\| \lesssim \|\Sigma\|\big(\sqrt{p/n}+p/n\big)$ with high probability.

How many samples are needed for a $10\%$ relative operator-norm error at $p = 1000$ ?
How does the requirement scale with the target accuracy, and with $p$ ?
Contrast with the sample complexity of estimating an arbitrary Lipschitz function on $[0,1]^p$ to accuracy $\eps$ .

Compute the requested quantities and say what they mean. A number without an interpretation is not an answer.

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Two different curses of dimensionality	Classical ML	Numerical	Beginner	15 min
Bounding the spectral norm by row and column sums	Foundations	Proof	Intermediate	30 min
Frobenius versus operator norm for random matrices	Random Matrices	Numerical	Intermediate	30 min
Measure the covariance estimation rate run	High-Dim Statistics	Coding	Intermediate	1 hour
Simulate the Marchenko–Pastur law run	Random Matrices	Coding	Intermediate	1 hour