A fast and slightly robust covariance estimator

Let Z = Z1, dots, Zn stackreli.i.d.~ P subset ℝd from a distribution P with mean zero and covariance Sigma. Given a dataset X such that dham(X, Z) ≤ varepsilon n, we are interested in finding an efficient estimator widehatSigma that achieves err(widehatSigma, Sigma) := |Sigma^-frac12widehatSigmaSigma^-frac12 - I| op ≤ 1/2. We focus on the low contamination regime varepsilon = o(1/√d). In this regime, prior work required either Omega(d3/2) samples or runtime that is exponential in d. We present an algorithm that, for subgaussian data, has near-linear sample complexity n = widetildeOmega(d) and runtime O((n+d)^ω + frac12), where ω is the matrix multiplication exponent. We also show that this algorithm works for heavy-tailed data with near-linear sample complexity, but in a smaller regime of varepsilon. Concurrent to our work, Diakonikolas et al. [2024] give Sum-of-Squares estimators that achieve similar sample complexity but with large polynomial runtime.