# Linear Convergence of ISTA and FISTA

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 24 references that are in the map.
- First posted on arXiv 13 Dec 2022.

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

- [A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights](https://mlsanity.com/paper/1503.01243/) (2015)
- [Understanding the Acceleration Phenomenon via High-Resolution Differential Equations](https://mlsanity.com/paper/1810.08907/) (2018)
- [False Discoveries Occur Early on the Lasso Path](https://mlsanity.com/paper/1511.01957/) (2015)
- [Acceleration via Symplectic Discretization of High-Resolution Differential Equations](https://mlsanity.com/paper/1902.03694/) (2019)
- [First-order optimization algorithms via inertial systems with Hessian driven damping](https://mlsanity.com/paper/1907.10536/) (2019)
- [Sparse Recovery via Differential Inclusions](https://mlsanity.com/paper/1406.7728/) (2014)
- [Gradient Norm Minimization of Nesterov Acceleration: o(1/k3)](https://mlsanity.com/paper/2209.08862/) (2022)
- [Proximal Subgradient Norm Minimization of ISTA and FISTA](https://mlsanity.com/paper/2211.01610/) (2022)

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

- [Linear convergence of forward-backward accelerated algorithms without knowledge of the modulus of strong convexity](https://mlsanity.com/paper/2306.09694/) (2023)
- [Lyapunov Analysis For Monotonically Forward-Backward Accelerated Algorithms](https://mlsanity.com/paper/2412.13527/) (2024)

## Abstract (arXiv)

In this paper, we revisit the class of iterative shrinkage-thresholding algorithms (ISTA) for solving the linear inverse problem with sparse representation, which arises in signal and image processing. It is shown in the numerical experiment to deblur an image that the convergence behavior in the logarithmic-scale ordinate tends to be linear instead of logarithmic, approximating to be flat. Making meticulous observations, we find that the previous assumption for the smooth part to be convex weakens the least-square model. Specifically, assuming the smooth part to be strongly convex is more reasonable for the least-square model, even though the image matrix is probably ill-conditioned. Furthermore, we improve the pivotal inequality tighter for composite optimization with the smooth part to be strongly convex instead of general convex, which is first found in [Li et al., 2022]. Based on this pivotal inequality, we generalize the linear convergence to composite optimization in both the objective value and the squared proximal subgradient norm. Meanwhile, we set a simple ill-conditioned matrix which is easy to compute the singular values instead of the original blur matrix. The new numerical experiment shows the proximal generalization of Nesterov's accelerated gradient descent (NAG) for the strongly convex function has a faster linear convergence rate than ISTA. Based on the tighter pivotal inequality, we also generalize the faster linear convergence rate to composite optimization, in both the objective value and the squared proximal subgradient norm, by taking advantage of the well-constructed Lyapunov function with a slight modification and the phase-space representation based on the high-resolution differential equation framework from the implicit-velocity scheme.