A Unified Framework for Low-Rank plus Sparse Matrix Recovery

Abstract

We propose a unified framework to solve general low-rank plus sparse matrix recovery problems based on matrix factorization, which covers a broad family of objective functions satisfying the restricted strong convexity and smoothness conditions. Based on projected gradient descent and the double thresholding operator, our proposed generic algorithm is guaranteed to converge to the unknown low-rank and sparse matrices at a locally linear rate, while matching the best-known robustness guarantee (i.e., tolerance for sparsity). At the core of our theory is a novel structural Lipschitz gradient condition for low-rank plus sparse matrices, which is essential for proving the linear convergence rate of our algorithm, and we believe is of independent interest to prove fast rates for general superposition-structured models. We illustrate the application of our framework through two concrete examples: robust matrix sensing and robust PCA. Experiments on both synthetic and real datasets corroborate our theory.

49 pages, 3 figures, 3 tables

References in corpus (12)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Fast Algorithms for Robust PCA via Gradient Descent
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Fast matrix completion without the condition number
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• Nearly-optimal Robust Matrix Completion
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Speeding Up Latent Variable Gaussian Graphical Model Estimation via Nonconvex Optimizations
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Matrix ALPS: Accelerated Low Rank and Sparse Matrix Reconstruction
• High Dimensional Structured Superposition Models

Cited by in corpus (2)

• Matrix Completion and Related Problems via Strong Duality
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent