# GNMR: A provable one-line algorithm for low rank matrix recovery

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 92 references that are in the map.
- First posted on arXiv 24 Jun 2021.

## Builds on (most cited first, 30 of 33)

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [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)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [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)
- [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)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [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)
- [A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements](https://mlsanity.com/paper/1506.06081/) (2015)
- [Provable Inductive Matrix Completion](https://mlsanity.com/paper/1306.0626/) (2013)
- [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013)
- [Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence](https://mlsanity.com/paper/1904.10020/) (2019)
- [Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number](https://mlsanity.com/paper/2010.13364/) (2020)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data](https://mlsanity.com/paper/2001.05484/) (2020)
- [Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provably](https://mlsanity.com/paper/1606.03168/) (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)
- [A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion](https://mlsanity.com/paper/1503.02596/) (2015)
- [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)
- [R3MC: A Riemannian three-factor algorithm for low-rank matrix completion](https://mlsanity.com/paper/1306.2672/) (2013)
- [Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence](https://mlsanity.com/paper/2011.08360/) (2020)
- [Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent](https://mlsanity.com/paper/1709.08114/) (2017)
- [Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries](https://mlsanity.com/paper/2002.01849/) (2020)
- [Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow](https://mlsanity.com/paper/1803.01233/) (2018)
- [Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery](https://mlsanity.com/paper/1703.05038/) (2017)

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

- [Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithm](https://mlsanity.com/paper/2201.13052/) (2022)
- [Symmetric Matrix Completion with ReLU Sampling](https://mlsanity.com/paper/2406.05822/) (2024)
- [Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity](https://mlsanity.com/paper/2408.13276/) (2024)
- [A Majorization-Minimization Gauss-Newton Method for 1-Bit Matrix Completion](https://mlsanity.com/paper/2304.13940/) (2023)
- [Learning Transition Operators From Sparse Space-Time Samples](https://mlsanity.com/paper/2212.00746/) (2022)
- [Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Training](https://mlsanity.com/paper/2511.04485/) (2025)
- [Truncated Matrix Completion - An Empirical Study](https://mlsanity.com/paper/2504.09873/) (2025)
- [RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees](https://mlsanity.com/paper/2505.12919/) (2025)
- [One-Sided Matrix Completion from Ultra-Sparse Samples](https://mlsanity.com/paper/2601.12213/) (2026)
- [Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure](https://mlsanity.com/paper/2608.21607/) (2026)

## Abstract (arXiv)

Low rank matrix recovery problems, including matrix completion and matrix sensing, appear in a broad range of applications. In this work we present GNMR -- an extremely simple iterative algorithm for low rank matrix recovery, based on a Gauss-Newton linearization. On the theoretical front, we derive recovery guarantees for GNMR in both the matrix sensing and matrix completion settings. Some of these results improve upon the best currently known for other methods. A key property of GNMR is that it implicitly keeps the factor matrices approximately balanced throughout its iterations. On the empirical front, we show that for matrix completion with uniform sampling, GNMR performs better than several popular methods, especially when given very few observations close to the information limit.