Local Linear Convergence of ISTA and FISTA on the LASSO Problem

2015/01/13 by Shaozhe Tao, Tao, Shaozhe, Daniel Boley +3 · 4 citations
Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Numerical methods in inverse problems #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1501.02888

openalex publication_date 2015/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We establish local linear convergence bounds for the ISTA and FISTA iterations on the model LASSO problem. We show that FISTA can be viewed as an accelerated ISTA process. Using a spectral analysis, we show that, when close enough to the solution, both iterations converge linearly, but FISTA slows down compared to ISTA, making it advantageous to switch to ISTA toward the end of the iteration processs. We illustrate the results with some synthetic numerical examples.

Citations

• Atomic Decomposition by Basis Pursuit
• Least angle regression

Cited by

• Diffusion Generative Models Meet Compressed Sensing, with Applications to Imaging and Finance
• Adaptive Iterative Soft-Thresholding Algorithm with the Median Absolute Deviation
• Real-time ℓ¹ -- ℓ² deblurring using wavelet expansions of operators
• Activity Identification and Local Linear Convergence of Forward--Backward-type methods

Related

• Convergence of LCA Flows to (C)LASSO Solutions
• Accelerate the Warm-up Stage in the Lasso Computation via a Homotopic Approach
• Local Convergence of an AMP Variant to the LASSO Solution in Finite Dimensions
• Activity Identification and Local Linear Convergence of Forward--Backward-type methods
• The iterates of FISTA convergence even under inexact computations and stochastic gradients