A fast and slightly robust covariance estimator

Let $\mathcal{Z} = \{Z_1, \dots, Z_n\} \stackrel{\mathrm{i.i.d.}}{\sim} P \subset \mathbb{R}^d$ from a distribution $P$ with mean zero and covariance $\Sigma$. Given a dataset $\mathcal{X}$ such that $d_{\mathrm{ham}}(\mathcal{X}, \mathcal{Z}) \leq \varepsilon n$, we are interested in finding an efficient estimator $\widehat{\Sigma}$ that achieves $\mathrm{err}(\widehat{\Sigma}, \Sigma) := \|\Sigma^{-\frac{1}{2}}\widehat{\Sigma}\Sigma^{-\frac{1}{2}} - I\| _{\mathrm{op}} \leq 1/2$. We focus on the low contamination regime $\varepsilon = o(1/\sqrt{d}$). In this regime, prior work required either $\Omega(d^{3/2})$ samples or runtime that is exponential in $d$. We present an algorithm that, for subgaussian data, has near-linear sample complexity $n = \widetilde{\Omega}(d)$ and runtime $O((n+d)^{\omega + \frac{1}{2}})$, where $\omega$ 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.