# A fast and slightly robust covariance estimator

arXiv: https://arxiv.org/abs/2502.20708 · HTML: https://mlsanity.com/paper/2502.20708/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2025.

## Built on by (most cited first, 1 of 1)

- [Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity](https://mlsanity.com/paper/2601.18245/) (2026)

## Abstract (arXiv)

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.