Randomized Robust Subspace Recovery for High Dimensional Data Matrices
arXiv:1505.05901 · doi:10.1109/TSP.2016.2645515
Abstract
This paper explores and analyzes two randomized designs for robust Principal Component Analysis (PCA) employing low-dimensional data sketching. In one design, a data sketch is constructed using random column sampling followed by low dimensional embedding, while in the other, sketching is based on random column and row sampling. Both designs are shown to bring about substantial savings in complexity and memory requirements for robust subspace learning over conventional approaches that use the full scale data. A characterization of the sample and computational complexity of both designs is derived in the context of two distinct outlier models, namely, sparse and independent outlier models. The proposed randomized approach can provably recover the correct subspace with computational and sample complexity that are almost independent of the size of the data. The results of the mathematical analysis are confirmed through numerical simulations using both synthetic and real data.
References in corpus (22)
- Robust Recovery of Subspace Structures by Low-Rank Representation
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Sparsity and Incoherence in Compressive Sampling
- A Simpler Approach to Matrix Completion
- Rank-Sparsity Incoherence for Matrix Decomposition
- Sketching as a Tool for Numerical Linear Algebra
- A geometric analysis of subspace clustering with outliers
- Robust PCA via Outlier Pursuit
- Fast Algorithms for Robust PCA via Gradient Descent
- Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
- Non-convex Robust PCA
- Robust PCA as Bilinear Decomposition with Outlier-Sparsity Regularization
- A Novel M-Estimator for Robust PCA
- Robust computation of linear models by convex relaxation
- Robust recovery of multiple subspaces by geometric l_p minimization
- Innovation Pursuit: A New Approach to Subspace Clustering
- Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling
- Fast, Robust and Non-convex Subspace Recovery
- Algorithms and Hardness for Robust Subspace Recovery
- Solving Principal Component Pursuit in Linear Time via Filtering
- Recovery of Coherent Data via Low-Rank Dictionary Pursuit
- A Sparse Johnson--Lindenstrauss Transform
Cited by in corpus (18)
- Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
- Non-Intrusive Energy Disaggregation Using Non-negative Matrix Factorization with Sum-to-k Constraint
- High Dimensional Low Rank plus Sparse Matrix Decomposition
- Innovation Pursuit: A New Approach to Subspace Clustering
- Evolutionary Self-Expressive Models for Subspace Clustering
- Scalable and Robust Community Detection with Randomized Sketching
- A Dictionary-Based Generalization of Robust PCA Part II: Applications to Hyperspectral Demixing
- A Dictionary-Based Generalization of Robust PCA with Applications to Target Localization in Hyperspectral Imaging
- Missing Spectrum-Data Recovery in Cognitive Radio Networks Using Piecewise Constant Nonnegative Matrix Factorization
- Spatial Random Sampling: A Structure-Preserving Data Sketching Tool
- Subspace Clustering via Optimal Direction Search
- Low Rank Matrix Recovery with Simultaneous Presence of Outliers and Sparse Corruption
- A Robust Regression Approach for Background/Foreground Segmentation
- A Dictionary Based Generalization of Robust PCA
- Robust and Scalable Column/Row Sampling from Corrupted Big Data
- Robust Low-Complexity Randomized Methods for Locating Outliers in Large Matrices
- Fast Randomized Algorithms for t-Product Based Tensor Operations and Decompositions with Applications to Imaging Data
- Multi-View Task-Driven Recognition in Visual Sensor Networks