# Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers

arXiv: https://arxiv.org/abs/2109.12713 · HTML: https://mlsanity.com/paper/2109.12713/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 39 references that are in the map.
- First posted on arXiv 26 Sep 2021.

## Builds on (most cited first, 11 of 11)

- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Non-convex Robust PCA](https://mlsanity.com/paper/1410.7660/) (2014)
- [Fast Algorithms for Robust PCA via Gradient Descent](https://mlsanity.com/paper/1605.07784/) (2016)
- [Support recovery without incoherence: A case for nonconvex regularization](https://mlsanity.com/paper/1412.5632/) (2014)
- [Nonconvex Nonsmooth Low-Rank Minimization via Iteratively Reweighted Nuclear Norm](https://mlsanity.com/paper/1510.06895/) (2015)
- [Optimal computational and statistical rates of convergence for sparse nonconvex learning problems](https://mlsanity.com/paper/1306.4960/) (2013)
- [Robust PCA via Nonconvex Rank Approximation](https://mlsanity.com/paper/1511.05261/) (2015)
- [Generalized Singular Value Thresholding](https://mlsanity.com/paper/1412.2231/) (2014)
- [Low-Rank Factorization for Rank Minimization with Nonconvex Regularizers](https://mlsanity.com/paper/2006.07702/) (2020)

## Abstract (arXiv)

This paper considers a large class of problems where we seek to recover a low rank matrix and/or sparse vector from some set of measurements. While methods based on convex relaxations suffer from a (possibly large) estimator bias, and other nonconvex methods require the rank or sparsity to be known a priori, we use nonconvex regularizers to minimize the rank and l0 norm without the estimator bias from the convex relaxation. We present a novel analysis of the alternating proximal gradient descent algorithm applied to such problems, and bound the error between the iterates and the ground truth sparse and low rank matrices. The algorithm and error bound can be applied to sparse optimization, matrix completion, and robust principal component analysis as special cases of our results.