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

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

## Key facts

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

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

- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013)
- [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)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [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)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [Splitting methods with variable metric for KL functions](https://mlsanity.com/paper/1405.1357/) (2014)
- [Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation](https://mlsanity.com/paper/1802.08397/) (2018)
- [Nonconvex Nonsmooth Low-Rank Minimization via Iteratively Reweighted Nuclear Norm](https://mlsanity.com/paper/1510.06895/) (2015)
- [Guarantees of Riemannian Optimization for Low Rank Matrix Completion](https://mlsanity.com/paper/1603.06610/) (2016)
- [A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion](https://mlsanity.com/paper/1503.02596/) (2015)
- [A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points](https://mlsanity.com/paper/1707.08028/) (2017)
- [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)
- [Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries](https://mlsanity.com/paper/2002.01849/) (2020)
- [Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery](https://mlsanity.com/paper/1703.05038/) (2017)
- [Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms](https://mlsanity.com/paper/1801.08227/) (2018)
- [Spectral Operators of Matrices](https://mlsanity.com/paper/1401.2269/) (2014)

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

- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Learning Sparse and Low-Rank Priors for Image Recovery via Iterative Reweighted Least Squares Minimization](https://mlsanity.com/paper/2304.10536/) (2023)
- [Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion](https://mlsanity.com/paper/2208.11246/) (2022)
- [Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery](https://mlsanity.com/paper/2410.16826/) (2024)
- [Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization](https://mlsanity.com/paper/2410.16982/) (2024)
- [Learning Transition Operators From Sparse Space-Time Samples](https://mlsanity.com/paper/2212.00746/) (2022)
- [Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares](https://mlsanity.com/paper/2306.04961/) (2023)
- [Iterative Reweighted Least Squares Networks With Convergence Guarantees for Solving Inverse Imaging Problems](https://mlsanity.com/paper/2308.05745/) (2023)
- [A Flag Decomposition for Hierarchical Datasets](https://mlsanity.com/paper/2502.07782/) (2025)
- [Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Training](https://mlsanity.com/paper/2511.04485/) (2025)
- [PI-NLF: A Proportional-Integral Approach for Non-negative Latent Factor Analysis](https://mlsanity.com/paper/2205.02591/) (2022)
- [RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees](https://mlsanity.com/paper/2505.12919/) (2025)
- [Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow](https://mlsanity.com/paper/2609.09295/) (2026)

## 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.