mlsanityData to 7 Oct 2026

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

arXiv 2106.12933 ↗First posted 24 Jun 2021math.OC cs.LG cs.NAcited by 10

Not on the map. Why?

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.

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

Builds on

33 of 92 references.

References · 33

  1. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  2. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  3. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  4. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  5. 2014Guaranteed Matrix Completion via Non-convex Factorizationcited by 81
  6. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 70
  7. 2017Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolutioncited by 63
  8. 2019Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimizationcited by 58
  9. 2016Fast Algorithms for Robust PCA via Gradient Descentcited by 39
  10. 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 37
  11. 2017Global Optimality in Low-rank Matrix Optimizationcited by 35
  12. 2015A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurementscited by 34
21 more
  1. 2013Understanding Alternating Minimization for Matrix Completioncited by 32
  2. 2013Provable Inductive Matrix Completioncited by 31
  3. 2019Low-rank matrix recovery with composite optimization: good conditioning and rapid convergencecited by 31
  4. 2013Incoherence-Optimal Matrix Completioncited by 27
  5. 2020Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Numbercited by 27
  6. 2020Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Datacited by 23
  7. 2016Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provablycited by 22
  8. 2014Fast matrix completion without the condition numbercited by 17
  9. 2014Fast Exact Matrix Completion with Finite Samplescited by 15
  10. 2015A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completioncited by 13
  11. 2016Nearly-optimal Robust Matrix Completioncited by 13
  12. 2021A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samplescited by 13
  13. 2013R3MC: A Riemannian three-factor algorithm for low-rank matrix completioncited by 11
  14. 2020Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergencecited by 11
  15. 2017Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descentcited by 10
  16. 2020Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entriescited by 10
  17. 2018Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flowcited by 8
  18. 2017Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recoverycited by 7
  19. 2018On the Quadratic Convergence of the Cubic Regularization Method under a Local Error Bound Conditioncited by 7
  20. 2020The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularizationcited by 7
  21. 2020Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Methodcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 1; 2024: 2; 2025: 3; 2026: 2.

10 papers.

  1. 2022Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithmcited by 4
  2. 2024Symmetric Matrix Completion with ReLU Samplingcited by 4
  3. 2024Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexitycited by 3
  4. 2023A Majorization-Minimization Gauss-Newton Method for 1-Bit Matrix Completioncited by 2
  5. 2022Learning Transition Operators From Sparse Space-Time Samplescited by 1
  6. 2025Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Trainingcited by 1
  7. 2025Truncated Matrix Completion - An Empirical Studycited by 0
  8. 2025RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guaranteescited by 0
  9. 2026One-Sided Matrix Completion from Ultra-Sparse Samplescited by 0
  10. 2026Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structurecited by 0