A fast and slightly robust covariance estimator

Abstract

Let $\mathcal{Z}=\{Z_1,\dots ,Z_n\}\stackrel{i.i.d.}{\sim }P\subset {\mathbb{R}}^d$ from a distribution $P$ with mean zero and covariance $\hat{I}\pounds$. Given a dataset $\mathcal{X}$ such that $d_{\mathrm{ham}}(\mathcal{X},\mathcal{Z})\le \epsilon n$, we are interested in finding an efficient estimator $\hat{\hat{I}}\pounds$ that achieves $\mathrm{err}(\hat{\hat{I}}\pounds ,\hat{I}\pounds ):=\Vert \hat{I}{\pounds }^{-\frac{1}{2}}\hat{\hat{I}}\pounds \hat{I}{\pounds }^{-\frac{1}{2}}-I{\Vert }_{\mathrm{op}}\le 1/2$. We focus on the low contamination regime $\epsilon =o(1/\sqrt{d}$). In this regime, prior work required either $\hat{I}\text{c◯}(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=\tilde{\hat{I}}\text{c◯}(d)$ and runtime $O((n+d{)}^{\ddot{I}‰+\frac{1}{2}})$, where $\ddot{I}‰$ 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 $\epsilon$. Concurrent to our work, Diakonikolas et al. [2024] give Sum-of-Squares estimators that achieve similar sample complexity but with large polynomial runtime.

39 pages