# On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squares

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 89 references that are in the map.
- First posted on arXiv 22 Dec 2021.

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

- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [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)
- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Fast Exact Matrix Completion with Finite Samples](https://mlsanity.com/paper/1411.1087/) (2014)
- [IHT dies hard: Provable accelerated Iterative Hard Thresholding](https://mlsanity.com/paper/1712.09379/) (2017)
- [Spectral Compressed Sensing via Projected Gradient Descent](https://mlsanity.com/paper/1707.09726/) (2017)
- [Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent](https://mlsanity.com/paper/2102.02396/) (2021)
- [A Closed-Form Bound on the Asymptotic Linear Convergence of Iterative Methods via Fixed Point Analysis](https://mlsanity.com/paper/2112.10598/) (2021)

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

- [RedCore: Relative Advantage Aware Cross-modal Representation Learning for Missing Modalities with Imbalanced Missing Rates](https://mlsanity.com/paper/2312.10386/) (2023)
- [GC-Fed: Gradient Centralized Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2503.13180/) (2025)

## Abstract (arXiv)

Many recent problems in signal processing and machine learning such as compressed sensing, image restoration, matrix/tensor recovery, and non-negative matrix factorization can be cast as constrained optimization. Projected gradient descent is a simple yet efficient method for solving such constrained optimization problems. Local convergence analysis furthers our understanding of its asymptotic behavior near the solution, offering sharper bounds on the convergence rate compared to global convergence analysis. However, local guarantees often appear scattered in problem-specific areas of machine learning and signal processing. This manuscript presents a unified framework for the local convergence analysis of projected gradient descent in the context of constrained least squares. The proposed analysis offers insights into pivotal local convergence properties such as the conditions for linear convergence, the region of convergence, the exact asymptotic rate of convergence, and the bound on the number of iterations needed to reach a certain level of accuracy. To demonstrate the applicability of the proposed approach, we present a recipe for the convergence analysis of projected gradient descent and demonstrate it via a beginning-to-end application of the recipe on four fundamental problems, namely, linear equality-constrained least squares, sparse recovery, least squares with the unit norm constraint, and matrix completion.