List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering. (arXiv:2206.05245v1 [cs.DS])

We study the problem of list-decodable sparse mean estimation. Specifically,
for a parameter $\alpha \in (0, 1/2)$, we are given $m$ points in
$\mathbb{R}^n$, $\lfloor \alpha m \rfloor$ of which are i.i.d. samples from a
distribution $D$ with unknown $k$-sparse mean $\mu$. No assumptions are made on
the remaining points, which form the majority of the dataset. The goal is to
return a small list of candidates containing a vector $\widehat \mu$ such that
$\| \widehat \mu - \mu \|_2$ …

arxiv decodable difference filtering list mean