# Scaled Gradient Descent for Ill-Conditioned Low-Rank Matrix Recovery with Optimal Sampling Complexity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 31 Mar 2026.

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

- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [Non-convex Robust PCA](https://mlsanity.com/paper/1410.7660/) (2014)
- [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016)
- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence](https://mlsanity.com/paper/1904.10020/) (2019)
- [Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number](https://mlsanity.com/paper/2010.13364/) (2020)
- [Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation](https://mlsanity.com/paper/1802.08397/) (2018)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization](https://mlsanity.com/paper/2504.09708/) (2025)
- [The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization](https://mlsanity.com/paper/2003.10981/) (2020)
- [Multi-View Matrix Completion for Multi-Label Image Classification](https://mlsanity.com/paper/1904.03901/) (2019)
- [Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity](https://mlsanity.com/paper/2408.13276/) (2024)

## Abstract (arXiv)

The low-rank matrix recovery problem seeks to reconstruct an unknown n1 × n2 rank-r matrix from m linear measurements, where mll n1n2. This problem has been extensively studied over the past few decades, leading to a variety of algorithms with solid theoretical guarantees. Among these, gradient descent based non-convex methods have become particularly popular due to their computational efficiency. However, these methods typically suffer from two key limitations: a sub-optimal sample complexity of O((n1 + n2)r2) and an iteration complexity of O(kappa log(1/ε)) to achieve ε-accuracy, resulting in slow convergence when the target matrix is ill-conditioned. Here, kappa denotes the condition number of the unknown matrix. Recent studies show that a preconditioned variant of GD, known as scaled gradient descent (ScaledGD), can significantly reduce the iteration complexity to O(log(1/ε)). Nonetheless, its sample complexity remains sub-optimal at O((n1 + n2)r2). In contrast, a delicate virtual sequence technique demonstrates that the standard GD in the positive semidefinite (PSD) setting achieves the optimal sample complexity O((n1 + n2)r), but converges more slowly with an iteration complexity O(kappa2 log(1/ε)). In this paper, through a more refined analysis, we show that ScaledGD achieves both the optimal sample complexity O((n1 + n2)r) and the improved iteration complexity O(log(1/ε)). Notably, our results extend beyond the PSD setting to general low-rank matrix recovery problem. Numerical experiments further validate that ScaledGD accelerates convergence for ill-conditioned matrices with the optimal sampling complexity.