# Local and Global Linear Convergence of General Low-rank Matrix Recovery Problems

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2021.

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

- [Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate](https://mlsanity.com/paper/2203.03899/) (2022)
- [Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods](https://mlsanity.com/paper/2110.10279/) (2021)
- [From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent](https://mlsanity.com/paper/2210.06705/) (2022)
- [Inductive Matrix Completion: No Bad Local Minima and a Fast Algorithm](https://mlsanity.com/paper/2201.13052/) (2022)
- [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022)
- [Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks](https://mlsanity.com/paper/2410.09640/) (2024)
- [On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2402.02569/) (2024)
- [Absence of spurious solutions far from ground truth: A low-rank analysis with high-order losses](https://mlsanity.com/paper/2403.06056/) (2024)

## Abstract (arXiv)

We study the convergence rate of gradient-based local search methods for solving low-rank matrix recovery problems with general objectives in both symmetric and asymmetric cases, under the assumption of the restricted isometry property. First, we develop a new technique to verify the Polyak-Lojasiewicz inequality in a neighborhood of the global minimizers, which leads to a local linear convergence region for the gradient descent method. Second, based on the local convergence result and a sharp strict saddle property proven in this paper, we present two new conditions that guarantee the global linear convergence of the perturbed gradient descent method. The developed local and global convergence results provide much stronger theoretical guarantees than the existing results. As a by-product, this work significantly improves the existing bounds on the RIP constant required to guarantee the non-existence of spurious solutions.