Source-linked AI summary
Accelerated Projected Gradient Method for Linear Inverse Problems with Sparsity Constraints
I. Daubechies, M. Fornasier, I. Loris
TL;DR
Ill-posed and noisy linear inverse problems motivate ℓ1 regularization when solutions are sparse. The paper replaces direct ℓ1-penalized iteration with projected gradient methods on ℓ1-balls, including accelerated variants, and proves norm convergence for a projected method with and without acceleration. Numerical examples show these methods can outperform thresholded Landweber and even LARS in CPU time, while the paper notes that no method is universally best.
Problem
Ill-conditioned or non-invertible operators and noisy data require regularization, particularly when the unknown has a sparse expansion.
Method
The paper develops projected gradient methods for ℓ1-constrained inverse problems, using variable-step projected iterations and accelerated steepest-descent ingredients.
Results
Strong norm convergence is proved for the full sequence under a suitable descent-parameter condition, and numerical examples show CPU-time advantages over thresholded Landweber and LARS.
Takeaways & Limitations
Projected steepest-descent-style iterations provide a convergence-guaranteed alternative that can be faster in practice, although performance depends on the operator, data, and penalization parameter.
Takeaways & Limitations
The paper’s toy-model comparison notes that LARS can lose its advantage on much larger problems whose solutions are not sparse in absolute numbers.
Abstract
from arXiv · showhide
Regularization of ill-posed linear inverse problems via $\ell_1$ penalization has been proposed for cases where the solution is known to be (almost) sparse. One way to obtain the minimizer of such an $\ell_1$ penalized functional is via an iterative soft-thresholding algorithm. We propose an alternative implementation to $\ell_1$-constraints, using a gradient method, with projection on $\ell_1$-balls. The corresponding algorithm uses again iterative soft-thresholding, now with a variable thresholding parameter. We also propose accelerated versions of this iterative method, using ingredients of the (linear) steepest descent method. We prove convergence in norm for one of these projected gradient methods, without and with acceleration.
1 Introduction
The paper addresses ill-posed, noisy linear inverse problems by using ℓ1 regularization when the unknown admits a sparse or compressible representation. Its central aim is to construct faster iterative algorithms while exploiting sparsity as prior knowledge.
- Objective: The main objective is to develop iterative algorithms for ℓ1-penalized or ℓ1-constrained inverse problems that converge faster than an earlier iterative method.The paper situates this goal within the broader use of sparsity for data recovery and computational simplification.
- Problem: Ill-conditioned or non-invertible forward operators and noisy observations make reconstruction require regularization.The data model relates observable y to an unknown f through a linear operator, with noise added in realistic settings.
- Sparsity assumption: The approach targets unknowns that have sparse expansions in an orthonormal basis or frame, meaning only a few coefficients are large.Sparse frame expansions are identified as realistic for signals such as natural images.
- Regularization: Adding an ℓ1 term to the minimized functional models the sparsity constraint and acts as a regularization scheme.The paper follows earlier work showing that this ℓ1 assumption corresponds to regularization.
2 Framework and Notations
The paper formulates sparse inverse problems in sequence spaces using frame coefficients and an ℓ1-regularized functional. It reviews iterative soft-thresholding, whose thresholding operation produces the minimizer of a combined ℓ2–ℓ1 objective.
- Sequence-space framework: The framework uses ℓp spaces of real coefficient sequences indexed by a countable set Λ, with ℓ2 serving as the default norm.The index set has a natural enumeration used in convergence arguments.
- Frames: A frame provides stable series expansions f = F x, where x belongs to ℓ2(Λ), although coefficients need not be unique when the frame is redundant.The synthesis map F is bounded, and orthonormal bases are a special case of frames.
- Sparsity model: Sparsity or compressibility is modeled by placing the coefficient sequence in a weighted ℓ1 space, because ℓ1 minimization promotes sparse expansions.This representation is applied to the frame coefficients of the unknown.
- Penalized inverse problem: The transformed operator K := A ◦ F maps coefficient sequences to data, and the paper seeks approximations to the minimizer x̄(τ) of the penalized functional.The recovered object is obtained as f̄(τ) = F x̄(τ).
- Baseline algorithm: Iterative soft-thresholding approximates x̄(τ) through recursively defined iterates and converges to the minimizer of a functional combining ℓ2 and ℓ1 norms.The paper also calls this scheme the thresholded Landweber iteration.
- Illustration: Figure 1 compares three algorithms in the ∥x∥1 versus ∥Kx − y∥2 plane, including thresholded Landweber, projected Landweber, and projected steepest descent.The figure uses boxes, crosses, and triangles for the respective paths, with the vertical axis logarithmically scaled.
3 Discussion of the Thresholded Landweber Iteration
The thresholded Landweber iteration can overshoot the target ℓ1-ball and converge slowly, while projected gradient iterations keep iterates within the ball and support larger adaptive steps. The paper studies conditions ensuring norm convergence, including parameters beyond prior results.
- Motivation: The sparsest solution of an under-determined linear system is computationally hard, motivating ℓ1-minimization as a tractable convex alternative for some operators.The algorithm is considered fast relative to exhaustive search for sparsity.
- Thresholded Landweber dynamics: Thresholded Landweber initially approaches the target quickly, overshoots its ℓ1 norm, and then slowly returns toward the limit.The iterates start inside the relevant ℓ1-ball, leave it, and correct the external detour only asymptotically.
- Projected methods: Replacing thresholding with projection onto an ℓ1-ball prevents ℓ1-norm overshoot, although the projected Landweber iteration remains very slow.The resulting method is called the projected Landweber iteration.
- Projected methods: Adaptive descent parameters produce promising convergence numerically for projected Landweber, unlike the soft-thresholded iteration, where larger steps failed to converge in some experiments.The modified projected method shows larger steps and faster convergence than projected Landweber in the illustrated comparison.
- Convergence question: Earlier projected-gradient results generally established only weak convergence in infinite-dimensional spaces and imposed restrictions on descent parameters.The paper targets norm convergence for whole sequences with adaptive parameters that may grow and exceed 2/∥K∥.
- Convergence question: A main result proves norm convergence to a unique accumulation point for descent parameters β(n) ≥ 2 under an appropriate choice of parameters.The authors identify strong convergence as non-automatic and note a prior counterexample where it fails.
4 Projections onto ℓ1-Balls via Thresholding Operators
The paper characterizes ℓ2-projection onto ℓ1-balls through soft-thresholding and gives a finite-dimensional computation based on sorting and searching thresholded coefficients. It also records geometric properties of the projection.
- Thresholding characterization: Soft-thresholding produces a continuous, piecewise linear, decreasing ℓ1 norm as its threshold increases.For ℓ1 sequences, the norm equals the original norm at threshold zero and vanishes once the threshold reaches the largest coefficient magnitude.
- Thresholding characterization: When ∥a∥1 exceeds R, the ℓ2 projection onto the ℓ1-ball is Sµ(a), with µ chosen so ∥Sµ(a)∥1 = R.If a already lies in the ball, the projection leaves it unchanged.
- Explicit computation: Computing the finite-dimensional projection begins by sorting the absolute component values, an O(m log m) operation.A subsequent search identifies the thresholding index needed to determine the projection threshold.
- Projection properties: Projection onto the ℓ1-ball is non-expansive, so it does not increase ℓ2 distances between inputs.The paper derives this through standard convex-projection inequalities.
5 The Projected Gradient Method
The projected gradient method replaces fixed-step thresholded Landweber updates with projected, adaptively scaled gradient steps and establishes convergence under conditions on the descent parameters.
- Algorithmic formulation: The method replaces straightforward fixed-threshold soft-thresholding with adapted soft-thresholding operations corresponding to projection onto an ℓ1-ball.The ball radius R remains fixed throughout the iterations, while the threshold is adjusted to realize the projection.
- Algorithmic formulation: The projected gradient iteration scales the residual gradient r(n) by β(n) before projecting the result onto the constraint ball.The step is introduced in the spirit of classical steepest descent, with arbitrary initialization such as x(0) = 0.
- Convergence analysis: Norm convergence is proved for the algorithm when descent parameters satisfy Condition (B), under assumptions including β(n) ≥ 1 and boundedness conditions.Condition (B) requires bounded parameters with inf β(n) ≥ 1 and imposes an inequality involving successive iterates and K.
- Characterization of minimizers: Minimizers of D on BR can be nonunique, but all share the same image under K and differ only by elements of ker K.Nonzero coordinates of minimizers are restricted to a finite set of indices attaining the maximal magnitude of K*(y − u).
- Convergence analysis: Every weak accumulation point minimizes the discrepancy D on BR, and each such point has a subsequence converging to it in norm.The proof also establishes convergence of the corresponding K-images along weakly convergent subsequences.
- Convergence analysis: The full iterate sequence converges in norm to a minimizer of D on BR when Condition (B) holds, although different initial points may lead to different limits.The uniqueness argument concerns the accumulation point for a fixed recursion and initialization.
6 Numerical Experiments and Additional Algorithms
The numerical experiments compare projected and thresholded iterative methods across increasingly complex inverse problems, while additional algorithms connect projected iterations to trade-off curves and POCS. Projected steepest descent often converges faster, but its performance and guarantees depend on the problem and parameter choice.
- Numerical experiments: The experiments evaluate convergence as a function of CPU time, using the exact minimizer and relative reconstruction error as references.The authors note that the exact minimizer is needed in advance to measure relative error over time.
- Numerical experiments: For partial Fourier matrices, the adaptive steepest-descent parameter equals 1, so projected steepest descent performs identically to projected Landweber.In this setting, the dynamical step size offers no advantage.
- Numerical experiments: 2 seconds, 39 seconds, and 151 seconds are required by projected steepest descent, thresholded Landweber, and LARS, respectively, to reach 5% relative error in the second example.The second example uses a 1536 × 2049 rank-1536 matrix, and LARS is slower because the limiting vector has 429 nonzero entries.
- Numerical experiments: Projected steepest descent reaches 3% relative error in about 5.5 hours, compared with more than 21 hours for thresholded Landweber in the seismic tomography example.Each projected steepest descent step takes approximately twice as long because it uses an additional matrix-vector multiplication and computes an ℓ1-ball projection.
- Numerical experiments: Projected Landweber is initially faster in the third example but later becomes slower than iterative soft-thresholding because of the additional projection time.The comparison uses time in hours on the horizontal axis and relative error on the vertical axis.
- Additional algorithms: The increasing-radius interior algorithm has no convergence proof, although its iterates were observed to follow the trade-off curve closely.Its radius increases as R(n) = (n + 1)R/N over a prescribed maximum of N iterations, starting from the origin.
7 Conclusions
The paper reports convergence results for accelerated projected gradient methods and numerical evidence that they can outperform thresholded Landweber and LARS in CPU time. Algorithm choice depends on the operator’s structure and the minimizer’s absolute sparsity, while the discussed cases do not cover all operators and data.
- 7 Conclusions: The proposed accelerated projected gradient methods have convergence results for minimizing an ℓ1-penalized functional and can outperform thresholded Landweber and LARS in CPU time.The convergence innovation is Condition (B), which guarantees strong convergence for the full sequence.
- 7 Conclusions: The thresholded Landweber algorithm works best when the operator is close to the identity, independently of the minimizer’s sparsity.
- 7 Conclusions: The projected steepest descent algorithm works best for operators with relatively nice spectra and not too many zeroes, independently of the minimizer’s sparsity.
- 7 Conclusions: The exact LARS method works best when the minimizer is sparse in absolute terms.
- 7 Conclusions: The three recommended regimes overlap partially and do not cover the whole range of possible operators and data.Future work targets large ill-conditioned matrices with minimizers relatively sparse relative to the underlying space’s dimension.