Research map / Learning theory and algorithms / Matrix and tensor methods

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

ICML 2025 · Learning theory and algorithms › Matrix and tensor methods · approach: Low-rank approximation theory · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes OPSA, an overparameterized preconditioned subgradient method for robust asymmetric low-rank matrix recovery with unknown rank, proving linear convergence independent of the condition number via Polyak step sizes and a regularized distance metric.

Problem

Robust recovery of low-rank asymmetric matrices from gross-outlier-corrupted measurements when the true rank is unknown and overparameterized, with non-smooth l1 loss; prior preconditioned methods lacked guarantees in this regime.

Approach

Combines overparameterized factorization with regularized preconditioners (R^T R + lambda I)^{-1} inside a non-smooth subgradient method with Polyak step sizes, and uses a novel regularized alignment distance metric to prove rank-independent linear convergence for asymmetric matrices.

Key results

• OPSA achieves linear convergence under overparameterization d>r where ScaledSM fails to converge at major overparameterization (matrix sensing experiments, n=100, r=5, kappa=20, 10% outliers).
• Theorem gives linear rate 1 - 0.12/chi^2 per iteration (chi = L/mu) independent of condition number kappa of X*.
• Under Gaussian mixed-norm RIP with outlier fraction p_s, iteration complexity O((1-2p_s)^{-2} log(1/eps)).

Measured effects reported in the paper

Limitations

• Convergence requires a good spectral initialization whose requirement worsens as condition number grows
• Theory relies on restricted Lipschitz and restricted sharpness assumptions and a positive regularization lambda
• Rate worsens with overparameterization through chi = L/mu

Experimental setup

Datasets: synthetic Gaussian matrix sensing data

Benchmarks: synthetic robust matrix sensing

Metrics: relative error ||LR^T - X*||_F / ||X*||_F

Baselines: ScaledSM Vanilla GD PrecGD ScaledGD(lambda)

Builds on: ScaledGD ScaledSM Polyak step size overparameterized robust matrix sensing subgradient method

Closest papers by meaning

• Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery (NeurIPS 2021 · similarity 0.93)
• Sharp Restricted Isometry Property Bounds for Low-Rank Matrix Recovery Problems with Corrupted Measurements (AAAI 2022 · similarity 0.91)
• Robust Matrix Sensing in the Semi-Random Model (NeurIPS 2023 · similarity 0.90)
• RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.88)
• How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization (ICLR 2024 · similarity 0.88)
• Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.87)