Fast, Robust and Non-convex Subspace Recovery

Monday, March 7, 2016 - 2:25pm - 3:25pm
Lind 305
Gilad Lerman (University of Minnesota, Twin Cities)
This joint work with Tyler Maunu presents a fast and non-convex algorithm for robust subspace recovery. The datasets considered include inliers drawn around a low-dimensional subspace of a higher dimensional ambient space, and a possibly large portion of outliers that do not lie nearby this subspace. The proposed algorithm, which we refer to as Fast Median Subspace (FMS), is designed to robustly determine the underlying subspace of such datasets, while having lower computational complexity than existing methods. We prove convergence of the FMS iterates to a stationary point. Further, under a special model of data, we prove that FMS converges globally sublinearly, and locally $r$-linearly with overwhelming probability to a point which is near to the global minimum. The latter theorem holds for any fixed fraction of outliers (less than 1) and any fixed positive distance between the limit point and the global minimum. Numerical experiments on synthetic and real data demonstrate its competitive speed and accuracy. The real data experiments emphasize the usefulness of FMS for dimension reduction.