# Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2020.

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

- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Truncated Matrix Completion - An Empirical Study](https://mlsanity.com/paper/2504.09873/) (2025)

## Abstract (arXiv)

We propose an iterative algorithm for low-rank matrix completion that can be interpreted as both an iteratively reweighted least squares (IRLS) algorithm and a saddle-escaping smoothing Newton method applied to a non-convex rank surrogate objective. It combines the favorable data efficiency of previous IRLS approaches with an improved scalability by several orders of magnitude. Our method attains a local quadratic convergence rate already for a number of samples that is close to the information theoretical limit. We show in numerical experiments that unlike many state-of-the-art approaches, our approach is able to complete very ill-conditioned matrices with a condition number of up to 1010 from few samples.