Abstract
This paper investigates the $\ell^1$ regularized least squares optimization problem within separable Hilbert spaces. We demonstrate that the Iterative Soft-Thresholding Algorithm (ISTA) achieves linear convergence without requiring restrictive assumptions on the linear operator or the specific problem instance. This result stems from two fundamental concepts: the "extended support"—a finite set encompassing the solution's support—and the property of conditioning over finite-dimensional sets. We prove that ISTA identifies the solution's extended support in a finite number of iterations. Once identified, the problem effectively reduces to a finite-dimensional one where conditioning ensures linear convergence. Our analysis generalizes to a broad class of thresholding gradient algorithms, offering a novel proof of strong convergence and explicit convergence rates.
Introduction
In signal processing and machine learning, $\ell^1$ regularization (e.g., LASSO) is a standard technique for promoting sparsity. The Iterative Soft-Thresholding Algorithm (ISTA) is the primary tool for solving these problems, especially in high-dimensional or infinite-dimensional settings. While ISTA's convergence is well-established, its rate of convergence often appears faster in practice than theoretical bounds suggest. Traditionally, linear convergence guarantees required strict conditions like the Restricted Isometry Property (RIP) or injectivity of the linear operator. This work bridges the gap by showing that linear convergence is an inherent structural property of $\ell^1$ regularized least squares in Hilbert spaces.
Theoretical Framework: Forward-Backward Splitting
The authors frame thresholding gradient methods as instances of Forward-Backward splitting. The objective function is decomposed into a smooth data-fidelity term (least squares) and a non-smooth sparsity-promoting regularizer.
The core innovation lies in two theoretical pillars:
- Extended Support Identification: The "extended support" is defined as a finite set of indices containing the solution's support and indices where dual constraints are active. The paper proves that ISTA iterates eventually reside within this finite-dimensional subspace after a finite number of steps.
- Finite Uniform Conditioning: For $\ell^1$ regularized problems, the objective function exhibits "2-conditioning" on finite-dimensional subspaces. This ensures that once the algorithm identifies the extended support, it behaves like a gradient method on a well-conditioned finite-dimensional problem, leading to linear convergence.
Key Insights
- Emergent Finite-Dimensionality: Even in infinite-dimensional Hilbert spaces, the algorithm naturally "shrinks" the problem into a finite-dimensional subspace.
- Structural Linear Convergence: Linear convergence for $\ell^1$ least squares is a structural property—it does not depend on specific properties of the linear operator $A$, but rather on the interplay between the $\ell^1$ norm and the least squares loss.
- Generalization: The framework extends beyond $\ell^1$ to elastic-net penalties ($\ell^1 + \ell^p$), providing a unified convergence analysis for various thresholding schemes.
Convergence Results
- Finite Identification (Theorem 3.9): The number of iterations to identify the extended support is finite and depends on the initial error and dual stability.
- Linear Convergence (Theorem 4.8): For $\ell^1$ regularized least squares, iterates $x^n$ converge to $\bar{x}$ at a linear rate: $\|x^{n+1} - \bar{x}\| \leq C\sqrt{\epsilon^n}$.
- Rates for $\ell^1 + \ell^p$ (Theorem 4.11):
- For $1 < p < 2$, convergence remains linear.
- For $p > 2$, convergence is sublinear ($O(n^{-\frac{1}{p-2}})$), outperforming the general $O(1/n)$ rate.
Conclusion and Future Directions
This work provides a robust theoretical foundation for the observed efficiency of ISTA. Future research may explore extending these results to non-separable penalties like the Group LASSO or "gridless" problems involving measures in Banach spaces. While linear convergence is guaranteed, precisely estimating the convergence constant remains a challenge as it depends on the local geometry of the operator restricted to the extended support.
Summary updated