Non-convex Robust PCA

Abstract

We propose a new method for robust PCA -- the task of recovering a low-rank matrix from sparse corruptions that are of unknown value and support. Our method involves alternating between projecting appropriate residuals onto the set of low-rank matrices, and the set of sparse matrices; each projection is {\em non-convex} but easy to compute. In spite of this non-convexity, we establish exact recovery of the low-rank matrix, under the same conditions that are required by existing methods (which are based on convex optimization). For an $m\times n$ input matrix ($m\le n)$, our method has a running time of $O(r^{2}mn)$ per iteration, and needs $O(\log (1/\epsilon ))$ iterations to reach an accuracy of $\epsilon$. This is close to the running time of simple PCA via the power method, which requires $O(rmn)$ per iteration, and $O(\log (1/\epsilon ))$ iterations. In contrast, existing methods for robust PCA, which are based on convex optimization, have $O(m^{2}n)$ complexity per iteration, and take $O(1/\epsilon )$ iterations, i.e., exponentially more iterations for the same accuracy. Experiments on both synthetic and real data establishes the improved speed and accuracy of our method over existing convex implementations.

Extended abstract to appear in NIPS 2014

References in corpus (3)

• The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
• Incoherence-Optimal Matrix Completion
• Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers

Cited by in corpus (44)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
• Guaranteed Matrix Completion via Non-convex Factorization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• 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
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
• Online Nonnegative Matrix Factorization with Outliers
• Accelerated Structured Alternating Projections for Robust Spectrally Sparse Signal Recovery
• Introduction to Nonnegative Matrix Factorization
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• Matrix Completion with Deterministic Sampling: Theories and Methods
• Provable Subspace Tracking from Missing Data and Matrix Completion
• Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Federated Over-Air Subspace Tracking from Incomplete and Corrupted Data
• Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise
• Low Rank Approximation with Entrywise ${\ell }_1$-Norm Error
• Exponentially convergent stochastic k-PCA without variance reduction
• Best Pair Formulation & Accelerated Scheme for Non-convex Principal Component Pursuit
• Alternating projections gridless covariance-based estimation for DOA
• Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory
• Nonconvex Robust Low-rank Matrix Recovery
• How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery
• Alternating minimization for dictionary learning: Local Convergence Guarantees
• Low Rank Forecasting
• Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition
• Higher-order Count Sketch: Dimensionality Reduction That Retains Efficient Tensor Operations
• A Survey on Nonconvex Regularization Based Sparse and Low-Rank Recovery in Signal Processing, Statistics, and Machine Learning
• Generalized Minkowski sets for the regularization of inverse problems
• On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization
• Self-paced Principal Component Analysis
• Distributed Stochastic Non-Convex Optimization: Momentum-Based Variance Reduction
• Non-Convex Structured Phase Retrieval
• A PTAS for ${\ell }_p$-Low Rank Approximation
• Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers
• Learning Mixtures of Low-Rank Models
• Submodular + Concave
• Provable Low Rank Phase Retrieval