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.
Categories: cs.DS