A Novel M-Estimator for Robust PCA
arXiv:1112.4863
Abstract
We study the basic problem of robust subspace recovery. That is, we assume a data set that some of its points are sampled around a fixed subspace and the rest of them are spread in the whole ambient space, and we aim to recover the fixed underlying subspace. We first estimate "robust inverse sample covariance" by solving a convex minimization procedure; we then recover the subspace by the bottom eigenvectors of this matrix (their number correspond to the number of eigenvalues close to 0). We guarantee exact subspace recovery under some conditions on the underlying data. Furthermore, we propose a fast iterative algorithm, which linearly converges to the matrix minimizing the convex problem. We also quantify the effect of noise and regularization and discuss many other practical and theoretical issues for improving the subspace recovery in various settings. When replacing the sum of terms in the convex energy function (that we minimize) with the sum of squares of terms, we obtain that the new minimizer is a scaled version of the inverse sample covariance (when exists). We thus interpret our minimizer and its subspace (spanned by its bottom eigenvectors) as robust versions of the empirical inverse covariance and the PCA subspace respectively. We compare our method with many other algorithms for robust PCA on synthetic and real data sets and demonstrate state-of-the-art speed and accuracy.
References in corpus (4)
Cited by in corpus (36)
- Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
- Geometric median and robust estimation in Banach spaces
- An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
- Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
- Randomized Robust Subspace Recovery for High Dimensional Data Matrices
- Innovation Pursuit: A New Approach to Subspace Clustering
- Fast, Robust and Non-convex Subspace Recovery
- Robust PCA with Partial Subspace Knowledge
- A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
- Algorithms and Hardness for 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
- Fast estimation of approximate matrix ranks using spectral densities
- Principal component analysis for big data
- Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
- Subspace Clustering via Optimal Direction Search
- Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
- Robust Subspace Recovery with Adversarial Outliers
- Low Rank Matrix Recovery with Simultaneous Presence of Outliers and Sparse Corruption
- RANSAC Algorithms for Subspace Recovery and Subspace Clustering
- Robust Group Synchronization via Cycle-Edge Message Passing
- Dual Principal Component Pursuit
- Exact Camera Location Recovery by Least Unsquared Deviations
- Mixture Models, Robustness, and Sum of Squares Proofs
- Robust Camera Location Estimation by Convex Programming
- Novelty Detection via Robust Variational Autoencoding
- Dual Principal Component Pursuit: Probability Analysis and Efficient Algorithms
- Subspace clustering based on low rank representation and weighted nuclear norm minimization
- Outlier Detection and Data Clustering via Innovation Search
- Fast, Parameter free Outlier Identification for Robust PCA
- Self-Paced Probabilistic Principal Component Analysis for Data with Outliers
- Laplacian regularized low rank subspace clustering
- Robust Low-Complexity Randomized Methods for Locating Outliers in Large Matrices
- Adaptive Stochastic Gradient Descent on the Grassmannian for Robust Low-Rank Subspace Recovery and Clustering
- Robust Orthogonal Complement Principal Component Analysis
- Modal Principal Component Analysis