mlsanityData to 7 Oct 2026

On the computational and statistical complexity of over-parameterized matrix sensing

arXiv 2102.02756 ↗First posted 27 Jan 2021cs.LG stat.MLcited by 31

Not on the map. Why?

Abstract (arXiv)

We consider solving the low rank matrix sensing problem with Factorized Gradient Descend (FGD) method when the true rank is unknown and over-specified, which we refer to as over-parameterized matrix sensing. If the ground truth signal X^* ∈ ℝd*d is of rank r, but we try to recover it using F F^top where F ∈ ℝd*k and k>r, the existing statistical analysis falls short, due to a flat local curvature of the loss function around the global maxima. By decomposing the factorized matrix F into separate column spaces to capture the effect of extra ranks, we show that |Ft Ft - X^*|F2 converges to a statistical error of tildeO (k d σ2/n) after tildeO(fracσrσ√fracnd) number of iterations where Ft is the output of FGD after t iterations, σ2 is the variance of the observation noise, σr is the r-th largest eigenvalue of X^*, and n is the number of sample. Our results, therefore, offer a comprehensive picture of the statistical and computational complexity of FGD for the over-parameterized matrix sensing problem.

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). Builds on 17 of its 46 references that are in the map. First posted on arXiv 27 Jan 2021.

Builds on

17 of 46 references.

References · 17

  1. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  2. 2014Statistical guarantees for the EM algorithm: From population to sample-based analysiscited by 131
  3. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  4. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  5. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  6. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 81
  7. 2015Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guaranteescited by 68
  8. 2014On Iterative Hard Thresholding Methods for High-dimensional M-Estimationcited by 53
  9. 2015Dropping Convexity for Faster Semi-definite Optimizationcited by 40
  10. 2018Singularity, Misspecification, and the Convergence Rate of EMcited by 38
  11. 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 37
  12. 2015A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurementscited by 34
5 more
  1. 2013Understanding Alternating Minimization for Matrix Completioncited by 32
  2. 2019Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recoverycited by 26
  3. 2020On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regressioncited by 24
  4. 2019Sharp Analysis of Expectation-Maximization for Weakly Identifiable Modelscited by 23
  5. 2020How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?cited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 9; 2023: 6; 2024: 4; 2025: 4; 2026: 4.

31 papers.

Sort:

By area:

  1. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  2. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  3. 2026Preconditioning Benefits of Spectral Orthogonalization in Muoncited by 28
  4. 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 21
  5. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  6. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  7. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  8. 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
  9. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  10. 2021Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recoverycited by 10
  11. 2022A Validation Approach to Over-parameterized Matrix and Image Recoverycited by 8
  12. 2024Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descentcited by 7
19 more
  1. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  2. 2024Toward Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixture Modelscited by 6
  3. 2021Towards Understanding Generalization via Decomposing Excess Risk Dynamicscited by 5
  4. 2023Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descentcited by 5
  5. 2022Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decompositioncited by 4
  6. 2023Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regressioncited by 4
  7. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  8. 2021Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regimecited by 3
  9. 2024Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexitycited by 3
  10. 2025On the Benefits of Weight Normalization for Overparameterized Matrix Sensingcited by 3
  11. 2025Convergence Dynamics of Over-Parameterized Score Matching for a Single Gaussiancited by 2
  12. 2023Greedy Pruning with Group Lasso Provably Generalizes for Matrix Sensingcited by 1
  13. 2023Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensingcited by 1
  14. 2024The Implicit Bias of Heterogeneity towards Invariance: A Study of Multi-Environment Matrix Sensingcited by 1
  15. 2025Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descentcited by 1
  16. 2022Improving Computational Complexity in Statistical Models with Second-Order Informationcited by 0
  17. 2026A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexitycited by 0
  18. 2026Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamicscited by 0
  19. 2026Strict-Saddle Landscapes and Multi-Rank Geometry in Low-Tubal-Rank Tensor Sensingcited by 0