# Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries

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

## Key facts

- Cited by 10 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 5 Feb 2020.

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

- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples](https://mlsanity.com/paper/2106.02119/) (2021)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization](https://mlsanity.com/paper/2410.16982/) (2024)
- [A Majorization-Minimization Gauss-Newton Method for 1-Bit Matrix Completion](https://mlsanity.com/paper/2304.13940/) (2023)
- [Over-Parametrized Matrix Factorization in the Presence of Spurious Stationary Points](https://mlsanity.com/paper/2112.13269/) (2021)
- [Learning Transition Operators From Sparse Space-Time Samples](https://mlsanity.com/paper/2212.00746/) (2022)
- [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)

## Abstract (arXiv)

We present a new, simple and computationally efficient iterative method for low rank matrix completion. Our method is inspired by the class of factorization-type iterative algorithms, but substantially differs from them in the way the problem is cast. Precisely, given a target rank r, instead of optimizing on the manifold of rank r matrices, we allow our interim estimated matrix to have a specific over-parametrized rank 2r structure. Our algorithm, denoted R2RILS for rank 2r iterative least squares, has low memory requirements, and at each iteration it solves a computationally cheap sparse least-squares problem. We motivate our algorithm by its theoretical analysis for the simplified case of a rank-1 matrix. Empirically, R2RILS is able to recover ill conditioned low rank matrices from very few observations -- near the information limit, and it is stable to additive noise.