List-Decodable Sparse Mean Estimation
Robust mean estimation is one of the most important problems in statistics:
given a set of samples $\{x_1, \dots, x_n\} \subset \mathbb{R}^d$ where an
$\alpha$ fraction are drawn from some distribution $D$ and the rest are
adversarially corrupted, it aims to estimate the mean of $D$. A surge of recent
research interest has been focusing on the list-decodable setting where $\alpha
\in (0, \frac12]$, and the goal is to output a finite number of estimates among
which at least one approximates the target mean. In this paper, we consider
that the underlying distribution is Gaussian and the target mean is $k$-sparse.
Our main contribution is the first polynomial-time algorithm that enjoys sample
complexity $O\big(\mathrm{poly}(k, \log d)\big)$, i.e. poly-logarithmic in the
dimension. One of the main algorithmic ingredients is using low-degree sparse
polynomials to filter outliers, which may be of independent interest.