mlsanityData to 14 Oct 2026

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

arXiv 2505.12919 ↗First posted 19 May 2025cs.LG cs.NA math.NAcited by 0

Not on the map. Why?

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.

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

24 of 70 references.

References · 24

  1. 2014Guaranteed Matrix Completion via Non-convex Factorizationcited by 82
  2. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 71
  3. 2014Non-convex Robust PCAcited by 41
  4. 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 39
  5. 2016Fast Algorithms for Robust PCA via Gradient Descentcited by 39
  6. 2017Global Optimality in Low-rank Matrix Optimizationcited by 36
  7. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 33
  8. 2017Accelerated Alternating Projections for Robust Principal Component Analysiscited by 25
  9. 2020Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Datacited by 23
  10. 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 22
  11. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  12. 2019Color image recovery using low-rank quaternion matrix completion algorithmcited by 14
12 more
  1. 2016Nearly-optimal Robust Matrix Completioncited by 13
  2. 2021A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samplescited by 13
  3. 2025Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorizationcited by 12
  4. 2020Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entriescited by 10
  5. 2021GNMR: A provable one-line algorithm for low rank matrix recoverycited by 10
  6. 2015Matrix Completion with Noisy Entries and Outlierscited by 7
  7. 2020Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Methodcited by 5
  8. 2022Robust Matrix Completion with Heavy-tailed Noisecited by 4
  9. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  10. 2013Online Algorithms for Factorization-Based Structure from Motioncited by 3
  11. 2024Deeply Learned Robust Matrix Completion for Large-scale Low-rank Data Recoverycited by 3
  12. 2024Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functionscited by 1

Built on by

Not cited yet.