Fast, Robust and Non-convex Subspace Recovery
This work addresses the problem of efficiently and robustly identifying low-dimensional subspaces in high-dimensional data with outliers, which is incremental as it builds on existing methods with lower computational complexity.
The paper tackles robust subspace recovery from data with outliers by proposing the Fast Median Subspace (FMS) algorithm, which achieves competitive speed and accuracy in numerical experiments on synthetic and real data.
This work presents a fast and non-convex algorithm for robust subspace recovery. The data sets 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 data sets, 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, FMS converges to a point which is near to the global minimum with overwhelming probability. Under this model, we show that the iteration complexity is globally bounded and locally $r$-linear. 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.