mlsanityData to 7 Oct 2026

A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples

arXiv 2106.02119 ↗First posted 3 Jun 2021math.OC cs.NA math.NAcited by 13

Not on the map. Why?

Abstract (arXiv)

We propose an iterative algorithm for low-rank matrix completion that can be interpreted as an iteratively reweighted least squares (IRLS) algorithm, a saddle-escaping smoothing Newton method or a variable metric proximal gradient method applied to a non-convex rank surrogate. It combines the favorable data-efficiency of previous IRLS approaches with an improved scalability by several orders of magnitude. We establish the first local convergence guarantee from a minimal number of samples for that class of algorithms, showing that the method attains a local quadratic convergence rate. Furthermore, we show that the linear systems to be solved are well-conditioned even for very ill-conditioned ground truth matrices. We provide extensive experiments, indicating that unlike many state-of-the-art approaches, our method is able to complete very ill-conditioned matrices with a condition number of up to 1010 from few samples, while being competitive in its scalability.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 22 of its 86 references that are in the map. First posted on arXiv 3 Jun 2021.

Builds on

22 of 86 references.

References · 22

  1. 2014Identifying and attacking the saddle point problem in high-dimensional non-convex optimizationcited by 286
  2. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  3. 2013Manopt, a Matlab toolbox for optimization on manifoldscited by 112
  4. 2014Guaranteed Matrix Completion via Non-convex Factorizationcited by 81
  5. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 70
  6. 2015Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decompositioncited by 63
  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. 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 37
  10. 2013Incoherence-Optimal Matrix Completioncited by 27
  11. 2014Splitting methods with variable metric for KL functionscited by 26
  12. 2018Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimationcited by 25
10 more
  1. 2015Nonconvex Nonsmooth Low-Rank Minimization via Iteratively Reweighted Nuclear Normcited by 23
  2. 2016Guarantees of Riemannian Optimization for Low Rank Matrix Completioncited by 19
  3. 2015A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completioncited by 13
  4. 2017A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Pointscited by 12
  5. 2013R3MC: A Riemannian three-factor algorithm for low-rank matrix completioncited by 11
  6. 2020Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergencecited by 11
  7. 2020Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entriescited by 10
  8. 2017Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recoverycited by 7
  9. 2018Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithmscited by 5
  10. 2014Spectral Operators of Matricescited by 1

Built on by

Cited by year (2026 to 7 Oct)

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

13 papers.

Sort:

  1. 2021GNMR: A provable one-line algorithm for low rank matrix recoverycited by 10
  2. 2023Learning Sparse and Low-Rank Priors for Image Recovery via Iterative Reweighted Least Squares Minimizationcited by 10
  3. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  4. 2024Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recoverycited by 4
  5. 2024Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimizationcited by 3
  6. 2022Learning Transition Operators From Sparse Space-Time Samplescited by 1
  7. 2023Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squarescited by 1
  8. 2023Iterative Reweighted Least Squares Networks With Convergence Guarantees for Solving Inverse Imaging Problemscited by 1
  9. 2025A Flag Decomposition for Hierarchical Datasetscited by 1
  10. 2025Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Trainingcited by 1
  11. 2022PI-NLF: A Proportional-Integral Approach for Non-negative Latent Factor Analysiscited by 0
  12. 2025RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guaranteescited by 0
1 more
  1. 2026Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flowcited by 0