A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm

Abstract

We study the problem of list-decodable Gaussian covariance estimation. Given a multiset $$T$$ of $$n$$ points in $$\mathbb{R}^d$$ such that an unknown $$\alpha\leq 1/2$$ fraction of points in $$T$$ are i.i.d. samples from an unknown Gaussian $$\mathcal{N}(\mu, \Sigma)$$, the goal is to output a list of $$O(1/\alpha)$$ hypotheses at least one of which is close to $$\Sigma$$ in relative Frobenius norm. Our main result is a $$\mathrm{poly}(d,1/\alpha)$$ sample and time algorithm for this task that guarantees relative Frobenius norm error of $$\mathrm{poly}(1/\alpha)$$. Importantly, our algorithm relies purely on spectral techniques. As a corollary, we obtain an efficient spectral algorithm for robust partial clustering of Gaussian mixture models (GMMs) --- a key ingredient in the recent work of [BakDJKKV22] on robustly learning arbitrary GMMs. Combined with the other components of [BakDJKKV22], our new method yields the first Sum-of-Squares-free algorithm for robustly learning GMMs, resolving an open problem proposed by Vempala and Kothari. At the technical level, we develop a novel multi-filtering method for list-decodable covariance estimation that may be useful in other settings.