mlsanityData to 14 Oct 2026

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

arXiv 2410.16826 ↗First posted 22 Oct 2024math.OC cs.LGcited by 4

Not on the map. Why?

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.

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

25 of 54 references.

References · 25

  1. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 160
  2. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  3. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 78
  4. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 71
  5. 2024Riemannian Preconditioned LoRA for Fine-Tuning Foundation Modelscited by 52
  6. 2014Non-convex Robust PCAcited by 41
  7. 2016Non-square matrix sensing without spurious local minima via the Burer-Monteiro approachcited by 38
  8. 2021Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detectioncited by 34
  9. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 33
  10. 2019Low-rank matrix recovery with composite optimization: good conditioning and rapid convergencecited by 31
  11. 2020Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Numbercited by 28
  12. 2017Accelerated Alternating Projections for Robust Principal Component Analysiscited by 25
13 more
  1. 2015Global Optimality in Tensor Factorization, Deep Learning, and Beyondcited by 22
  2. 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 22
  3. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  4. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  5. 2020Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimationcited by 16
  6. 2021A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samplescited by 13
  7. 2022Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Samplingcited by 12
  8. 2023Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descentcited by 5
  9. 2024Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guaranteescited by 4
  10. 2024Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descentcited by 3
  11. 2016Provable Burer-Monteiro factorization for a class of norm-constrained matrix problemscited by 2
  12. 2023Sharpness and well-conditioning of nonsmooth convex formulations in statistical signal recoverycited by 2
  13. 2024S3Attention: Improving Long Sequence Attention with Smoothed Skeleton Sketchingcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 1.

4 papers.

  1. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  2. 2024Structured Sampling for Robust Euclidean Distance Geometrycited by 2
  3. 2025Learnable Scaled Gradient Descent for Guaranteed Robust Tensor PCAcited by 2
  4. 2026Robust Low-Tubal-Rank Tensor Completion under Cross-Concentrated Samplingcited by 0