# Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number

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

## Key facts

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

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

- [Riemannian Preconditioned LoRA for Fine-Tuning Foundation Models](https://mlsanity.com/paper/2402.02347/) (2024)
- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [Preconditioning Benefits of Spectral Orthogonalization in Muon](https://mlsanity.com/paper/2601.13474/) (2026)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization](https://mlsanity.com/paper/2504.09708/) (2025)
- [Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descent](https://mlsanity.com/paper/2206.09109/) (2022)
- [Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery](https://mlsanity.com/paper/2102.02969/) (2021)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [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)
- [Deep Unfolded Tensor Robust PCA with Self-supervised Learning](https://mlsanity.com/paper/2212.11346/) (2022)
- [Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion](https://mlsanity.com/paper/2208.11246/) (2022)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression](https://mlsanity.com/paper/2305.06199/) (2023)
- [Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decomposition](https://mlsanity.com/paper/2406.06002/) (2024)
- [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)
- [Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks](https://mlsanity.com/paper/2410.09640/) (2024)
- [Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing](https://mlsanity.com/paper/2101.05113/) (2021)
- [Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?](https://mlsanity.com/paper/2302.10963/) (2023)
- [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024)
- [Uncertainty Quantification For Low-Rank Matrix Completion With Heterogeneous and Sub-Exponential Noise](https://mlsanity.com/paper/2110.12046/) (2021)
- [Reassessing Muon for Matrix Factorization](https://mlsanity.com/paper/2607.13246/) (2026)
- [Unrolling SVT to obtain computationally efficient SVT for n-qubit quantum state tomography](https://mlsanity.com/paper/2212.08852/) (2022)
- [Scaled Gradient Descent for Ill-Conditioned Low-Rank Matrix Recovery with Optimal Sampling Complexity](https://mlsanity.com/paper/2604.00060/) (2026)
- [Over-parameterization Is Neither Robust nor Fragile in Matrix Sensing: A Geometric Theory of Solution Robustness](https://mlsanity.com/paper/2610.18318/) (2026)

## Abstract (arXiv)

Many problems in data science can be treated as estimating a low-rank matrix from highly incomplete, sometimes even corrupted, observations. One popular approach is to resort to matrix factorization, where the low-rank matrix factors are optimized via first-order methods over a smooth loss function, such as the residual sum of squares. While tremendous progresses have been made in recent years, the natural smooth formulation suffers from two sources of ill-conditioning, where the iteration complexity of gradient descent scales poorly both with the dimension as well as the condition number of the low-rank matrix. Moreover, the smooth formulation is not robust to corruptions. In this paper, we propose scaled subgradient methods to minimize a family of nonsmooth and nonconvex formulations -- in particular, the residual sum of absolute errors -- which is guaranteed to converge at a fast rate that is almost dimension-free and independent of the condition number, even in the presence of corruptions. We illustrate the effectiveness of our approach when the observation operator satisfies certain mixed-norm restricted isometry properties, and derive state-of-the-art performance guarantees for a variety of problems such as robust low-rank matrix sensing and quadratic sampling.