Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time

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."