This work 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 accurate methods. We prove convergence of the FMS iterates to a stationary point. Further, under two special models of data, FMS converges to a point which is near to the global minimum with overwhelming probability. Under these models, we show that the iteration complexity is globally sublinear and locally r-linear. For one of the models, these results hold for any fixed fraction of outliers (< 1). Numerical experiments on synthetic and real data demonstrate its competitive speed and accuracy.
Bibliographical noteFunding Information:
This work was supported by NSF awards DMS-09-56072 and DMS-14-18386 and the Feinberg Foundation Visiting Faculty Program Fellowship of the Weizmann Institute of Science.
© The authors 2017.
- Dimension reduction
- Iteratively reweighted least squares
- Minimization on the Grassmannian
- Non-convex optimization
- Robust subspace recovery