Abstract
Robust estimation is much more challenging in high dimensions than it is inone dimension: Most techniques either lead to intractable optimization problemsor estimators that can tolerate only a tiny fraction of errors. Recent work intheoretical computer science has shown that, in appropriate distributionalmodels, it is possible to robustly estimate the mean and covariance withpolynomial time algorithms that can tolerate a constant fraction ofcorruptions, independent of the dimension. However, the sample and timecomplexity of these algorithms is prohibitively large for high-dimensionalapplications. In this work, we address both of these issues by establishingsample complexity bounds that are optimal, up to logarithmic factors, as wellas giving various refinements that allow the algorithms to tolerate a muchlarger fraction of corruptions. Finally, we show on both synthetic and realdata that our algorithms have state-of-the-art performance and suddenly makehigh-dimensional robust estimation a realistic possibility.