Algorithms and Hardness for Robust Subspace Recovery

Moritz Hardt, Ankur Moitra

We consider a fundamental problem in unsupervised learning called \emph{subspace recovery}: given a collection of $m$ points in ${\mathbb{R}}^n$, if many but not necessarily all of t…