# Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 31 references that are in the map.
- First posted on arXiv 28 Jul 2024.

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

- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent](https://mlsanity.com/paper/1605.07051/) (2016)
- [Fast Algorithms for Robust PCA via Gradient Descent](https://mlsanity.com/paper/1605.07784/) (2016)
- [De-biasing the Lasso: Optimal Sample Size for Gaussian Designs](https://mlsanity.com/paper/1508.02757/) (2015)
- [Near-optimal bounds for phase synchronization](https://mlsanity.com/paper/1703.06605/) (2017)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [Accelerated Alternating Projections for Robust Principal Component Analysis](https://mlsanity.com/paper/1711.05519/) (2017)
- [Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data](https://mlsanity.com/paper/2001.05484/) (2020)
- [Guarantees of Riemannian Optimization for Low Rank Matrix Completion](https://mlsanity.com/paper/1603.06610/) (2016)
- [Fast matrix completion without the condition number](https://mlsanity.com/paper/1407.4070/) (2014)
- [Fast Exact Matrix Completion with Finite Samples](https://mlsanity.com/paper/1411.1087/) (2014)
- [Robust Spectral Compressed Sensing via Structured Matrix Completion](https://mlsanity.com/paper/1304.8126/) (2013)
- [Nearly-optimal Robust Matrix Completion](https://mlsanity.com/paper/1606.07315/) (2016)
- [Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA](https://mlsanity.com/paper/1711.01742/) (2017)
- [Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion](https://mlsanity.com/paper/2108.07899/) (2021)

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

- [RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees](https://mlsanity.com/paper/2505.12919/) (2025)

## Abstract (arXiv)

We study the problem of robust matrix completion (RMC), where the partially observed entries of an underlying low-rank matrix is corrupted by sparse noise. Existing analysis of the non-convex methods for this problem either requires the explicit but empirically redundant regularization in the algorithm or requires sample splitting in the analysis. In this paper, we consider a simple yet efficient nonconvex method which alternates between a projected gradient step for the low-rank part and a thresholding step for the sparse noise part. Inspired by leave-one out analysis for low rank matrix completion, it is established that the method can achieve linear convergence for a general class of thresholding functions, including for example soft-thresholding and SCAD. To the best of our knowledge, this is the first leave-one-out analysis on a nonconvex method for RMC. Additionally, when applying our result to low rank matrix completion, it improves the sampling complexity of existing result for the singular value projection method.