High-Dimensional Robust Mean Estimation via Outlier-Sparsity Minimization

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 0-'norm' of an outlier indicator vector, under a second moment constraint on the datapoints. We further relax the 0-'norm' to the p-norm (0 < p ≤ 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 p-minimization and hard thresholding algorithm based on the proposed optimization problems. Empirical studies demonstrate that the proposed algorithm outperforms state-of-the-art robust mean estimation methods.