Fast Algorithms for Robust PCA via Gradient Descent

2016/05/25 by Xinyang Yi, Dohyung Park, Yi, Xinyang +5 · 8 citations
Computer Science · Engineering · Mathematics · #Advanced Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Medical Image Segmentation Techniques #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #cs.IT #cs.LG #math.IT #math.ST #stat.ML #stat.TH

paper · pdf · doi:10.48550/arxiv.1605.07784

openalex publication_date 2016/05/25 · arxiv created 2016/09/19 · arxiv updated 2016/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 O(r²d²log(1/ε)) to O(rd²log(1/ε)) -- a big savings when the rank is big. For the partially observed case, we show the complexity of our algorithm is no more than O(r⁴d log d log(1/ε)). 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.

Citations

• Low Rank Approximation and Regression in Input Sparsity Time

Cited by

• Deep Unfolding: Recent Developments, Theory, and Design Guidelines
• Deep Unfolding with Approximated Computations for Rapid Optimization
• RPCANet++: Deep Interpretable Robust PCA for Sparse Object Segmentation
• A Dual Basis Approach for Structured Robust Euclidean Distance Geometry
• New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming
• RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees
• AltGDmin: Alternating GD and Minimization for Partly-Decoupled (Federated) Optimization
• Structured and Unstructured Outlier Identification for Robust PCA: A Fast Parameter Free Algorithm
• Randomized Robust Subspace Recovery and Outlier Detection for High Dimensional Data Matrices
• Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization

Related

• Nearly-optimal Robust Matrix Completion
• Non-convex Robust PCA
• Pseudo-Bayesian Robust PCA: Algorithms and Analyses
• Robust PCA by Manifold Optimization
• Provable Inductive Robust PCA via Iterative Hard Thresholding