# Faster Algorithms for High-Dimensional Robust Covariance Estimation

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2019.

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

- [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)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation](https://mlsanity.com/paper/2106.08537/) (2021)
- [Streaming Algorithms for High-Dimensional Robust Statistics](https://mlsanity.com/paper/2204.12399/) (2022)
- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [Robust Nonparametric Regression under Poisoning Attack](https://mlsanity.com/paper/2305.16771/) (2023)
- [Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA](https://mlsanity.com/paper/2305.02544/) (2023)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression](https://mlsanity.com/paper/2312.01547/) (2023)
- [Robust and Sparse Estimation of Linear Regression Coefficients with Heavy-tailed Noises and Covariates](https://mlsanity.com/paper/2206.07594/) (2022)
- [Efficient List-Decodable Regression using Batches](https://mlsanity.com/paper/2211.12743/) (2022)
- [Outlier Robust and Sparse Estimation of Linear Regression Coefficients](https://mlsanity.com/paper/2208.11592/) (2022)
- [Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error](https://mlsanity.com/paper/2302.12289/) (2023)
- [Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination](https://mlsanity.com/paper/2403.10416/) (2024)
- [Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time](https://mlsanity.com/paper/2105.05555/) (2021)
- [Nearly minimax robust estimator of the mean vector by iterative spectral dimension reduction](https://mlsanity.com/paper/2204.02323/) (2022)
- [Robust empirical risk minimization via Newton's method](https://mlsanity.com/paper/2301.13192/) (2023)
- [A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation](https://mlsanity.com/paper/2403.04726/) (2024)
- [Adversarial Robustness of Nonparametric Regression](https://mlsanity.com/paper/2505.17356/) (2025)
- [Sparse Mean Estimation in Adversarial Settings via Incremental Learning](https://mlsanity.com/paper/2305.15276/) (2023)
- [Bayesian Reinforcement Learning for Automatic Voltage Control under Cyber-Induced Uncertainty](https://mlsanity.com/paper/2305.16469/) (2023)
- [Iterative thresholding for non-linear learning in the strong varepsilon-contamination model](https://mlsanity.com/paper/2409.03703/) (2024)
- [Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians](https://mlsanity.com/paper/2502.06564/) (2025)
- [Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming](https://mlsanity.com/paper/2509.16915/) (2025)
- [Computable Bernstein Certificates for Cross-Fitted Clipped Covariance Estimation](https://mlsanity.com/paper/2602.14020/) (2026)

## Abstract (arXiv)

We study the problem of estimating the covariance matrix of a high-dimensional distribution when a small constant fraction of the samples can be arbitrarily corrupted. Recent work gave the first polynomial time algorithms for this problem with near-optimal error guarantees for several natural structured distributions. Our main contribution is to develop faster algorithms for this problem whose running time nearly matches that of computing the empirical covariance. Given N = tildeOmega(d2/ε2) samples from a d-dimensional Gaussian distribution, an ε-fraction of which may be arbitrarily corrupted, our algorithm runs in time tildeO(d3.26)/poly(ε) and approximates the unknown covariance matrix to optimal error up to a logarithmic factor. Previous robust algorithms with comparable error guarantees all have runtimes tildeOmega(d2 ω) when ε = Omega(1), where ω is the exponent of matrix multiplication. We also provide evidence that improving the running time of our algorithm may require new algorithmic techniques.