# RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 70 references that are in the map.
- First posted on arXiv 19 May 2025.

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

- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Non-convex Robust PCA](https://mlsanity.com/paper/1410.7660/) (2014)
- [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)
- [Global Optimality in Low-rank Matrix Optimization](https://mlsanity.com/paper/1702.07945/) (2017)
- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [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)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization](https://mlsanity.com/paper/2202.08788/) (2022)
- [Color image recovery using low-rank quaternion matrix completion algorithm](https://mlsanity.com/paper/1909.06567/) (2019)
- [Nearly-optimal Robust Matrix Completion](https://mlsanity.com/paper/1606.07315/) (2016)
- [A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples](https://mlsanity.com/paper/2106.02119/) (2021)
- [Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization](https://mlsanity.com/paper/2504.09708/) (2025)
- [Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries](https://mlsanity.com/paper/2002.01849/) (2020)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Matrix Completion with Noisy Entries and Outliers](https://mlsanity.com/paper/1503.00214/) (2015)
- [Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method](https://mlsanity.com/paper/2008.07740/) (2020)
- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2502.00463/) (2025)
- [Online Algorithms for Factorization-Based Structure from Motion](https://mlsanity.com/paper/1309.6964/) (2013)
- [Deeply Learned Robust Matrix Completion for Large-scale Low-rank Data Recovery](https://mlsanity.com/paper/2501.00677/) (2024)
- [Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functions](https://mlsanity.com/paper/2407.19446/) (2024)

## Abstract (arXiv)

Recovering a low rank matrix from a subset of its entries, some of which may be corrupted, is known as the robust matrix completion (RMC) problem. Existing RMC methods have several limitations: they require a relatively large number of observed entries; they may fail under overparametrization, when their assumed rank is higher than the correct one; and many of them fail to recover even mildly ill-conditioned matrices. In this paper we propose a novel RMC method, denoted textttRGNMR, which overcomes these limitations. textttRGNMR is a simple factorization-based iterative algorithm, which combines a Gauss-Newton linearization with removal of entries suspected to be outliers. On the theoretical front, we prove that under suitable assumptions, textttRGNMR is guaranteed exact recovery of the underlying low rank matrix. Our theoretical results improve upon the best currently known for factorization-based methods. On the empirical front, we show via several simulations the advantages of textttRGNMR over existing RMC methods, and in particular its ability to handle a small number of observed entries, overparameterization of the rank and ill-conditioned matrices.