Fast Algorithms for Robust PCA via Gradient Descent

Abstract

We consider the problem of Robust PCA in the fully and partially observed settings. Without corruptions, this is the well-known matrix completion problem. From a statistical standpoint this problem has been recently well-studied, and conditions on when recovery is possible (how many observations do we need, how many corruptions can we tolerate) via polynomial-time algorithms is by now understood. This paper presents and analyzes a non-convex optimization approach that greatly reduces the computational complexity of the above problems, compared to the best available algorithms. In particular, in the fully observed case, with $r$ denoting rank and $d$ dimension, we reduce the complexity from $\mathcal{O}(r^2{d}^2\log (1/\epsilon ))$ to $\mathcal{O}(r{d}^2\log (1/\epsilon ))$ -- a big savings when the rank is big. For the partially observed case, we show the complexity of our algorithm is no more than $\mathcal{O}(r^{4}d\log d\log (1/\epsilon ))$. Not only is this the best-known run-time for a provable algorithm under partial observation, but in the setting where $r$ is small compared to $d$, it also allows for near-linear-in-$d$ run-time that can be exploited in the fully-observed case as well, by simply running our algorithm on a subset of the observations.

References in corpus (1)

• Low Rank Approximation and Regression in Input Sparsity Time

Cited by in corpus (33)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
• Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
• An Overview of Robust Subspace Recovery
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation
• Accelerated Structured Alternating Projections for Robust Spectrally Sparse Signal Recovery
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• Structured and Unstructured Outlier Identification for Robust PCA: A Non iterative, Parameter free Algorithm
• Provable Subspace Tracking from Missing Data and Matrix Completion
• Fast Low Rank column-wise Compressive Sensing for Accelerated Dynamic MRI
• Robust PCA by Manifold Optimization
• Estimating Differential Latent Variable Graphical Models with Applications to Brain Connectivity
• Robust Wirtinger Flow for Phase Retrieval with Arbitrary Corruption
• Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• Speeding Up Latent Variable Gaussian Graphical Model Estimation via Nonconvex Optimizations
• Best Pair Formulation & Accelerated Scheme for Non-convex Principal Component Pursuit
• Thresholding based Efficient Outlier Robust PCA
• Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems
• A Unified Framework for Low-Rank plus Sparse Matrix Recovery
• Fast Low-Rank Matrix Estimation without the Condition Number
• Matrix Completion and Related Problems via Strong Duality
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Spectral Compressed Sensing via Projected Gradient Descent
• On the Robustness of Cross-Concentrated Sampling for Matrix Completion
• Low Rank Approximation in the Presence of Outliers
• Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
• On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems
• PCA in Data-Dependent Noise (Correlated-PCA): Nearly Optimal Finite Sample Guarantees
• Unorganized Malicious Attacks Detection
• Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variants