# Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 43 references that are in the map.
- First posted on arXiv 26 May 2023.

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

- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [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)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [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)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013)
- [Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing](https://mlsanity.com/paper/2301.11500/) (2023)
- [Fast Algorithms for Robust PCA via Gradient Descent](https://mlsanity.com/paper/1605.07784/) (2016)
- [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016)
- [A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements](https://mlsanity.com/paper/1506.06081/) (2015)
- [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022)
- [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)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [When Are Nonconvex Problems Not Scary?](https://mlsanity.com/paper/1510.06096/) (2015)
- [Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data](https://mlsanity.com/paper/2001.05484/) (2020)
- [Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provably](https://mlsanity.com/paper/1606.03168/) (2016)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [A Validation Approach to Over-parameterized Matrix and Image Recovery](https://mlsanity.com/paper/2209.10675/) (2022)
- [Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion](https://mlsanity.com/paper/2208.11246/) (2022)
- [Scaled stochastic gradient descent for low-rank matrix completion](https://mlsanity.com/paper/1603.04989/) (2016)

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

- [A Stronger Mixture of Low-Rank Experts for Fine-Tuning Foundation Models](https://mlsanity.com/paper/2502.15828/) (2025)
- [AltLoRA: Towards Better Gradient Approximation in Low-Rank Adaptation with Alternating Projections](https://mlsanity.com/paper/2505.12455/) (2025)
- [Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery](https://mlsanity.com/paper/2410.16826/) (2024)
- [Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2502.00463/) (2025)
- [Blind Ultrasound Image Enhancement via Self-Supervised Physics-Guided Degradation Modeling](https://mlsanity.com/paper/2601.21856/) (2026)

## Abstract (arXiv)

Non-convex gradient descent is a common approach for estimating a low-rank n× n ground truth matrix from noisy measurements, because it has per-iteration costs as low as O(n) time, and is in theory capable of converging to a minimax optimal estimate. However, the practitioner is often constrained to just tens to hundreds of iterations, and the slow and/or inconsistent convergence of non-convex gradient descent can prevent a high-quality estimate from being obtained. Recently, the technique of preconditioning was shown to be highly effective at accelerating the local convergence of non-convex gradient descent when the measurements are noiseless. In this paper, we describe how preconditioning should be done for noisy measurements to accelerate local convergence to minimax optimality. For the symmetric matrix sensing problem, our proposed preconditioned method is guaranteed to locally converge to minimax error at a linear rate that is immune to ill-conditioning and/or over-parameterization. Using our proposed preconditioned method, we perform a 60 megapixel medical image denoising task, and observe significantly reduced noise levels compared to previous approaches.