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 $Σ$. 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Σ$ that achieves $\mathrm{err}(\widehatΣ, Σ) := \|Σ^{-\frac{1}{2}}\widehatΣΣ^{-\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 $Ω(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Ω(d)$ and runtime $O((n+d)^{ω+ \frac{1}{2}})$, where $ω$ 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.