Consistent Estimation for PCA and Sparse Regression with Oblivious Outliers

Previous works could obtain non-trivial guarantees only under the assumptions that the measurement noise corresponding to the inliers is polynomially small in n (e.g., Gaussian with variance 1/n 2).To devise our estimators, we equip the Huber loss with non-smooth regularizers such as the \ell_1 norm or the nuclear norm, and extend d'Orsi et al.'s approach \cite{ICML-linear-regression} in a novel way to analyze the loss function.Our machinery appears to be easily applicable to a wide range of estimation problems.We complement these algorithmic results with statistical lower bounds showing that the fraction of inliers that our PCA estimator can deal with is optimal up to a constant factor.