# Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 29 references that are in the map.
- First posted on arXiv 4 Feb 2021.

## Builds on (most cited first, 6 of 6)

- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013)
- [Fast matrix completion without the condition number](https://mlsanity.com/paper/1407.4070/) (2014)
- [Fast Exact Matrix Completion with Finite Samples](https://mlsanity.com/paper/1411.1087/) (2014)

## Built on by (most cited first, 3 of 3)

- [Gradient-Based Spectral Embeddings of Random Dot Product Graphs](https://mlsanity.com/paper/2307.13818/) (2023)
- [On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squares](https://mlsanity.com/paper/2112.11760/) (2021)
- [LASE: Learned Adjacency Spectral Embeddings](https://mlsanity.com/paper/2412.17734/) (2024)

## Abstract (arXiv)

Factorization-based gradient descent is a scalable and efficient algorithm for solving low-rank matrix completion. Recent progress in structured non-convex optimization has offered global convergence guarantees for gradient descent under certain statistical assumptions on the low-rank matrix and the sampling set. However, while the theory suggests gradient descent enjoys fast linear convergence to a global solution of the problem, the universal nature of the bounding technique prevents it from obtaining an accurate estimate of the rate of convergence. In this paper, we perform a local analysis of the exact linear convergence rate of gradient descent for factorization-based matrix completion for symmetric matrices. Without any additional assumptions on the underlying model, we identify the deterministic condition for local convergence of gradient descent, which only depends on the solution matrix and the sampling set. More crucially, our analysis provides a closed-form expression of the asymptotic rate of convergence that matches exactly with the linear convergence observed in practice. To the best of our knowledge, our result is the first one that offers the exact rate of convergence of gradient descent for matrix factorization in Euclidean space for matrix completion.