Fast, Robust and Non-convex Subspace Recovery

Abstract

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.

References in corpus (11)

• Proceedings of the 29th International Conference on Machine Learning (ICML-12)
• When Are Nonconvex Problems Not Scary?
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling
• Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
• Principal Component Analysis with Contaminated Data: The High Dimensional Case
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• Reliable Eigenspectra for New Generation Surveys
• Robust PCA in High-dimension: A Deterministic Approach
• Input Sparsity and Hardness for Robust Subspace Approximation
• Fast Exact Matrix Completion with Finite Samples

Cited by in corpus (18)

• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
• An Overview of Robust Subspace Recovery
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• Structured and Unstructured Outlier Identification for Robust PCA: A Non iterative, Parameter free Algorithm
• Robust Subspace Recovery Layer for Unsupervised Anomaly Detection
• Consensus-Based Optimization on the Sphere: Convergence to Global Minimizers and Machine Learning
• Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search
• Low Rank Matrix Recovery with Simultaneous Presence of Outliers and Sparse Corruption
• On spectral and numerical properties of random butterfly matrices
• Dual Principal Component Pursuit
• Robust PCA via Regularized REAPER with a Matrix-Free Proximal Algorithm
• Novelty Detection via Robust Variational Autoencoding
• Outlier Detection and Data Clustering via Innovation Search
• Dual Principal Component Pursuit: Probability Analysis and Efficient Algorithms
• Distributed Robust Subspace Recovery
• Depth Descent Synchronization in $\mathrm{SO}(D)$