Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation

Abstract

Robust principal component analysis (RPCA) is a widely used tool for dimension reduction. In this work, we propose a novel non-convex algorithm, coined Iterated Robust CUR (IRCUR), for solving RPCA problems, which dramatically improves the computational efficiency in comparison with the existing algorithms. IRCUR achieves this acceleration by employing CUR decomposition when updating the low rank component, which allows us to obtain an accurate low rank approximation via only three small submatrices. Consequently, IRCUR is able to process only the small submatrices and avoid expensive computing on the full matrix through the entire algorithm. Numerical experiments establish the computational advantage of IRCUR over the state-of-art algorithms on both synthetic and real-world datasets.

References in corpus (11)

• Rank-Sparsity Incoherence for Matrix Decomposition
• Robust PCA via Outlier Pursuit
• Fast Algorithms for Robust PCA via Gradient Descent
• Non-convex Robust PCA
• Accelerated Structured Alternating Projections for Robust Spectrally Sparse Signal Recovery
• Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects
• Accelerated Alternating Projections for Robust Principal Component Analysis
• CUR from a Sparse Optimization Viewpoint
• Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Perturbations of CUR Decompositions

Cited by in corpus (12)

• Robust CUR Decomposition: Theory and Imaging Applications
• Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion
• Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection
• Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling
• Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruption
• Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions
• On the Robustness of Cross-Concentrated Sampling for Matrix Completion
• S${}^3$Attention: Improving Long Sequence Attention with Smoothed Skeleton Sketching
• Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition
• Structured Sampling for Robust Euclidean Distance Geometry
• LSDAT: Low-Rank and Sparse Decomposition for Decision-based Adversarial Attack
• Deep Unrolling for Nonconvex Robust Principal Component Analysis