Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functions
Not on the map. Why?
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 16 of its 31 references that are in the map. First posted on arXiv 28 Jul 2024.
Builds on
16 of 31 references.
References · 16
- 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
- 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
- 2016Fast Algorithms for Robust PCA via Gradient Descentcited by 39
- 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 37
- 2015De-biasing the Lasso: Optimal Sample Size for Gaussian Designscited by 35
- 2017Near-optimal bounds for phase synchronizationcited by 32
- 2013Incoherence-Optimal Matrix Completioncited by 27
- 2017Accelerated Alternating Projections for Robust Principal Component Analysiscited by 25
- 2020Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Datacited by 23
- 2016Guarantees of Riemannian Optimization for Low Rank Matrix Completioncited by 19
- 2014Fast matrix completion without the condition numbercited by 17
- 2014Fast Exact Matrix Completion with Finite Samplescited by 15
4 more
- 2013Robust Spectral Compressed Sensing via Structured Matrix Completioncited by 13
- 2016Nearly-optimal Robust Matrix Completioncited by 13
- 2017Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCAcited by 12
- 2021Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completioncited by 9
Built on by
Citing papers per year: 2025: 1.
1 paper.