# Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2020.

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

- [SPECTRE: Defending Against Backdoor Attacks Using Robust Statistics](https://mlsanity.com/paper/2104.11315/) (2021)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [From Robustness to Privacy and Back](https://mlsanity.com/paper/2302.01855/) (2023)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time](https://mlsanity.com/paper/2105.05555/) (2021)
- [Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity](https://mlsanity.com/paper/2601.18245/) (2026)

## Abstract (arXiv)

Robust covariance estimation is the following, well-studied problem in high dimensional statistics: given N samples from a d-dimensional Gaussian N(boldsymbol0, Sigma), but where an varepsilon-fraction of the samples have been arbitrarily corrupted, output widehatSigma minimizing the total variation distance between N(boldsymbol0, Sigma) and N(boldsymbol0, widehatSigma). This corresponds to learning Sigma in a natural affine-invariant variant of the Frobenius norm known as the Mahalanobis norm. Previous work of Cheng et al demonstrated an algorithm that, given N = Omega (d2 / varepsilon2) samples, achieved a near-optimal error of O(varepsilon log 1 / varepsilon), and moreover, their algorithm ran in time widetildeO(T(N, d) log kappa / poly (varepsilon)), where T(N, d) is the time it takes to multiply a d × N matrix by its transpose, and kappa is the condition number of Sigma. When varepsilon is relatively small, their polynomial dependence on 1/varepsilon in the runtime is prohibitively large. In this paper, we demonstrate a novel algorithm that achieves the same statistical guarantees, but which runs in time widetildeO (T(N, d) log kappa). In particular, our runtime has no dependence on varepsilon. When Sigma is reasonably conditioned, our runtime matches that of the fastest algorithm for covariance estimation without outliers, up to poly-logarithmic factors, showing that we can get robustness essentially "for free."