mlsanityData to 7 Oct 2026

Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent

arXiv 1605.07051 ↗First posted 23 May 2016stat.ML cs.LGcited by 37

Not on the map. Why?

Abstract (arXiv)

We address the rectangular matrix completion problem by lifting the unknown matrix to a positive semidefinite matrix in higher dimension, and optimizing a nonconvex objective over the semidefinite factor using a simple gradient descent scheme. With O( μ r2 kappa2 n max(μ, log n)) random observations of a n1 × n2 μ-incoherent matrix of rank r and condition number kappa, where n = max(n1, n2), the algorithm linearly converges to the global optimum with high probability.

Key facts. Cited by 37 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 May 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 5; 2023: 3; 2024: 10; 2025: 6; 2026: 3.

37 papers.

Sort:

By area:

  1. 2021Exploiting Shared Representations for Personalized Federated Learningcited by 537
  2. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
  3. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  4. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  5. 2024Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptationcited by 26
  6. 2021Inference for Heteroskedastic PCA with Missing Datacited by 21
  7. 2023The Law of Parsimony in Gradient Descent for Learning Deep Linear Networkscited by 19
  8. 2021Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorizationcited by 15
  9. 2021A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samplescited by 13
  10. 2022Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Samplingcited by 12
  11. 2023Convergence of Alternating Gradient Descent for Matrix Factorizationcited by 12
  12. 2021Implicit Regularization in Matrix Sensing via Mirror Descentcited by 11
25 more
  1. 2021Multi-source Learning via Completion of Block-wise Overlapping Noisy Matricescited by 10
  2. 2021GNMR: A provable one-line algorithm for low rank matrix recoverycited by 10
  3. 2024Low-Rank Contextual Reinforcement Learning from Heterogeneous Human Feedbackcited by 10
  4. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  5. 2022Towards a Theoretical Foundation of Policy Optimization for Learning Control Policiescited by 6
  6. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  7. 2024Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completioncited by 6
  8. 2022Robust Matrix Completion with Heavy-tailed Noisecited by 4
  9. 2024Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexitycited by 3
  10. 2021Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensingcited by 2
  11. 2024Low-Rank Online Dynamic Assortment with Dual Contextual Informationcited by 2
  12. 2024In-depth Analysis of Low-rank Matrix Factorisation in a Federated Settingcited by 2
  13. 2024Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functionscited by 1
  14. 2025Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorizationcited by 1
  15. 2025Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descentcited by 1
  16. 2026Learning Multi-type heterogeneous interacting particle systemscited by 1
  17. 2024Efficient Federated Low Rank Matrix Completioncited by 0
  18. 2024Predictive Low Rank Matrix Learning under Partial Observations: Mixed-Projection ADMMcited by 0
  19. 2024Matrix Completion via Residual Spectral Matchingcited by 0
  20. 2025Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approachcited by 0
  21. 2025AltGDmin: Alternating GD and Minimization for Partly-Decoupled (Federated) Optimizationcited by 0
  22. 2025RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guaranteescited by 0
  23. 2025Global Convergence Analysis of Vanilla Gradient Descent for Asymmetric Matrix Completioncited by 0
  24. 2026Sample-efficient inductive matrix completion with noise and inexact side-informationcited by 0
  25. 2026Latent Structural Categorical Matrix Completion with Application to Quasispecies Analysiscited by 0