# Robust PCA via Nonconvex Rank Approximation

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2015.

## Built on by (most cited first, 11 of 11)

- [Universal Background Subtraction based on Arithmetic Distribution Neural Network](https://mlsanity.com/paper/2104.08390/) (2021)
- [MOS: Model Synergy for Test-Time Adaptation on LiDAR-Based 3D Object Detection](https://mlsanity.com/paper/2406.14878/) (2024)
- [Hyperspectral Image Denoising Using Non-convex Local Low-rank and Sparse Separation with Spatial-Spectral Total Variation Regularization](https://mlsanity.com/paper/2201.02812/) (2022)
- [Robust Principal Component Analysis: A Median of Means Approach](https://mlsanity.com/paper/2102.03403/) (2021)
- [Learning Temporal Distribution and Spatial Correlation Towards Universal Moving Object Segmentation](https://mlsanity.com/paper/2304.09949/) (2023)
- [Self-paced Principal Component Analysis](https://mlsanity.com/paper/2106.13880/) (2021)
- [Efficient Differentiable Approximation of Generalized Low-rank Regularization](https://mlsanity.com/paper/2505.15407/) (2025)
- [Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers](https://mlsanity.com/paper/2109.12713/) (2021)
- [A low-rank non-convex norm method for multiview graph clustering](https://mlsanity.com/paper/2312.11157/) (2023)
- [Depth-Aided Color Image Inpainting in Quaternion Domain](https://mlsanity.com/paper/2503.16818/) (2025)
- [Matrix Completion Via Reweighted Logarithmic Norm Minimization](https://mlsanity.com/paper/2512.21050/) (2025)

## Abstract (arXiv)

Numerous applications in data mining and machine learning require recovering a matrix of minimal rank. Robust principal component analysis (RPCA) is a general framework for handling this kind of problems. Nuclear norm based convex surrogate of the rank function in RPCA is widely investigated. Under certain assumptions, it can recover the underlying true low rank matrix with high probability. However, those assumptions may not hold in real-world applications. Since the nuclear norm approximates the rank by adding all singular values together, which is essentially a ℓ1-norm of the singular values, the resulting approximation error is not trivial and thus the resulting matrix estimator can be significantly biased. To seek a closer approximation and to alleviate the above-mentioned limitations of the nuclear norm, we propose a nonconvex rank approximation. This approximation to the matrix rank is tighter than the nuclear norm. To solve the associated nonconvex minimization problem, we develop an efficient augmented Lagrange multiplier based optimization algorithm. Experimental results demonstrate that our method outperforms current state-of-the-art algorithms in both accuracy and efficiency.