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

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2016.

## Built on by (most cited first, 30 of 39)

- [Exploiting Shared Representations for Personalized Federated Learning](https://mlsanity.com/paper/2102.07078/) (2021)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptation](https://mlsanity.com/paper/2406.04112/) (2024)
- [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (2021)
- [The Law of Parsimony in Gradient Descent for Learning Deep Linear Networks](https://mlsanity.com/paper/2306.01154/) (2023)
- [Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization](https://mlsanity.com/paper/2102.12430/) (2021)
- [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)
- [Convergence of Alternating Gradient Descent for Matrix Factorization](https://mlsanity.com/paper/2305.06927/) (2023)
- [Implicit Regularization in Matrix Sensing via Mirror Descent](https://mlsanity.com/paper/2105.13831/) (2021)
- [Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices](https://mlsanity.com/paper/2105.10360/) (2021)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Low-Rank Contextual Reinforcement Learning from Heterogeneous Human Feedback](https://mlsanity.com/paper/2412.19436/) (2024)
- [Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion](https://mlsanity.com/paper/2208.11246/) (2022)
- [Towards a Theoretical Foundation of Policy Optimization for Learning Control Policies](https://mlsanity.com/paper/2210.04810/) (2022)
- [Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization](https://mlsanity.com/paper/2310.06159/) (2023)
- [Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion](https://mlsanity.com/paper/2402.06756/) (2024)
- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity](https://mlsanity.com/paper/2408.13276/) (2024)
- [Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing](https://mlsanity.com/paper/2101.05113/) (2021)
- [Low-Rank Online Dynamic Assortment with Dual Contextual Information](https://mlsanity.com/paper/2404.17592/) (2024)
- [In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting](https://mlsanity.com/paper/2409.08771/) (2024)
- [Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functions](https://mlsanity.com/paper/2407.19446/) (2024)
- [Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization](https://mlsanity.com/paper/2502.20033/) (2025)
- [Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent](https://mlsanity.com/paper/2504.19530/) (2025)
- [Learning Multi-type heterogeneous interacting particle systems](https://mlsanity.com/paper/2602.03954/) (2026)
- [Efficient Federated Low Rank Matrix Completion](https://mlsanity.com/paper/2405.06569/) (2024)
- [Predictive Low Rank Matrix Learning under Partial Observations: Mixed-Projection ADMM](https://mlsanity.com/paper/2407.13731/) (2024)

## 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.