Fast, robust and non-convex subspace recovery

Gilad Lerman, Tyler Maunu

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)277-336
Number of pages60
JournalInformation and Inference
Volume7
Issue number2
DOIs
StatePublished - Jun 7 2018

Bibliographical note

Funding 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.

Publisher Copyright:
© The authors 2017.

Keywords

  • Dimension reduction
  • Iteratively reweighted least squares
  • Minimization on the Grassmannian
  • Non-convex optimization
  • Robust subspace recovery

Fingerprint Dive into the research topics of 'Fast, robust and non-convex subspace recovery'. Together they form a unique fingerprint.

Cite this