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
$\mathcal{N}(\boldsymbol{0}, \Sigma)$, but where an $\varepsilon$-fraction of
the samples have been arbitrarily corrupted, output $\widehat{\Sigma}$
minimizing the total variation distance between $\mathcal{N}(\boldsymbol{0},
\Sigma)$ and $\mathcal{N}(\boldsymbol{0}, \widehat{\Sigma})$. This corresponds
to learning $\Sigma$ in a natural affine-invariant variant of the Frobenius
norm known as the \emph{Mahalanobis norm}. Previous work of Cheng et al
demonstrated an algorithm that, given $N = \Omega (d^2 / \varepsilon^2)$
samples, achieved a near-optimal error of $O(\varepsilon \log 1 /
\varepsilon)$, and moreover, their algorithm ran in time $\widetilde{O}(T(N, d)
\log \kappa / \mathrm{poly} (\varepsilon))$, where $T(N, d)$ is the time it
takes to multiply a $d \times 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 $\widetilde{O} (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."
