  We study the robust mean estimation problem in high dimensions, where less
than half of the datapoints can be arbitrarily corrupted. Motivated by
compressive sensing, we formulate the robust mean estimation problem as the
minimization of the $\ell_0$-`norm' of an \emph{outlier indicator vector},
under a second moment constraint on the datapoints. We further relax the
$\ell_0$-`norm' to the $\ell_p$-norm ($0<p\leq 1$) in the objective and prove
that the global minima for each of these objectives are order-optimal for the
robust mean estimation problem. Then we propose a computationally tractable
iterative $\ell_p$-minimization and hard thresholding algorithm that outputs an
order-optimal robust estimate of the population mean. Both synthetic and real
data experiments demonstrate that the proposed algorithm outperforms
state-of-the-art robust mean estimation methods. The source code will be made
available at GitHub.
