# Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 54 references that are in the map.
- First posted on arXiv 22 Oct 2024.

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

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [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)
- [Riemannian Preconditioned LoRA for Fine-Tuning Foundation Models](https://mlsanity.com/paper/2402.02347/) (2024)
- [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)
- [Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection](https://mlsanity.com/paper/2110.05649/) (2021)
- [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)
- [Accelerated Alternating Projections for Robust Principal Component Analysis](https://mlsanity.com/paper/1711.05519/) (2017)
- [Global Optimality in Tensor Factorization, Deep Learning, and Beyond](https://mlsanity.com/paper/1506.07540/) (2015)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization](https://mlsanity.com/paper/2310.01769/) (2023)
- [Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation](https://mlsanity.com/paper/2010.07422/) (2020)
- [A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples](https://mlsanity.com/paper/2106.02119/) (2021)
- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent](https://mlsanity.com/paper/2305.17224/) (2023)
- [Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees](https://mlsanity.com/paper/2410.06376/) (2024)
- [Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descent](https://mlsanity.com/paper/2406.07409/) (2024)
- [Provable Burer-Monteiro factorization for a class of norm-constrained matrix problems](https://mlsanity.com/paper/1606.01316/) (2016)
- [Sharpness and well-conditioning of nonsmooth convex formulations in statistical signal recovery](https://mlsanity.com/paper/2307.06873/) (2023)
- [S3Attention: Improving Long Sequence Attention with Smoothed Skeleton Sketching](https://mlsanity.com/paper/2408.08567/) (2024)

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

- [Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2502.00463/) (2025)
- [Structured Sampling for Robust Euclidean Distance Geometry](https://mlsanity.com/paper/2412.10664/) (2024)
- [Learnable Scaled Gradient Descent for Guaranteed Robust Tensor PCA](https://mlsanity.com/paper/2501.04565/) (2025)
- [Robust Low-Tubal-Rank Tensor Completion under Cross-Concentrated Sampling](https://mlsanity.com/paper/2608.03928/) (2026)

## Abstract (arXiv)

In this paper, we focus on a matrix factorization-based approach to recover low-rank it asymmetric matrices from corrupted measurements. We propose an it Overparameterized Preconditioned Subgradient Algorithm (OPSA) and provide, for the first time in the literature, linear convergence rates independent of the rank of the sought asymmetric matrix in the presence of gross corruptions. Our work goes beyond existing results in preconditioned-type approaches addressing their current limitation, i.e., the lack of convergence guarantees in the case of it asymmetric matrices of unknown rank. By applying our approach to (robust) matrix sensing, we highlight its merits when the measurement operator satisfies a mixed-norm restricted isometry property. Lastly, we present extensive numerical experiments that validate our theoretical results and demonstrate the effectiveness of our approach for different levels of overparameterization and outlier corruptions.