PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear convergence of iterative soft-thresholding

Kristian Bredies, Dirk A. Lorenz

arXiv:0709.1598v4math.FAmath.NA

TL;DR

The paper addresses the lack of general convergence-rate estimates for iterative soft-thresholding in infinite-dimensional sparse inverse problems. It places the algorithm in a generalized gradient framework and shows linear convergence under finite basis injectivity or strict sparsity, while noting scope boundaries in the generalized theory.

  • Problem

    Infinite-dimensional iterative soft-thresholding is strongly convergent, but earlier analyses do not inherently provide a-priori estimates or convergence rates.

  • Method

    The paper formulates iterative soft-thresholding as a generalized gradient projection method and derives convergence results using descent and Bregman-Taylor estimates.

  • Results

    The algorithm converges linearly when the operator has finite basis injectivity or the minimizer has a strict sparsity pattern.

  • Takeaways & Limitations

    The framework also supports linear-convergence analyses for related methods and for systems based on frames or dictionaries satisfying the injectivity condition.

  • Takeaways & Limitations

    The generalized convergence-rate discussion is restricted to the special case of the generalized gradient projection method, and the Bregman distance alone is insufficient when Φ is not sufficiently convex.

Abstract

from arXiv · show

In this article a unified approach to iterative soft-thresholding algorithms for the solution of linear operator equations in infinite dimensional Hilbert spaces is presented. We formulate the algorithm in the framework of generalized gradient methods and present a new convergence analysis. As main result we show that the algorithm converges with linear rate as soon as the underlying operator satisfies the so-called finite basis injectivity property or the minimizer possesses a so-called strict sparsity pattern. Moreover it is shown that the constants can be calculated explicitly in special cases (i.e. for compact operators). Furthermore, the techniques also can be used to establish linear convergence for related methods such as the iterative thresholding algorithm for joint sparsity and the accelerated gradient projection method.

1. Introduction

The paper studies convergence rates for iterative soft-thresholding in infinite-dimensional sparse inverse problems, where noise and non-smooth regularization complicate numerical solution. It develops a unified generalized-gradient framework and proves linear convergence under finite basis injectivity or strict sparsity.

  • Motivation: Sparse inverse problems model quantities represented by finitely many nonzero coefficients in a countable basis.The operator equation Ku = f connects the quantity of interest to measurements, while noise motivates stable regularization.
  • Motivation: Iterative soft-thresholding is simple and strongly convergent in infinite dimensions, but prior analyses generally provide no a-priori distance estimates or convergence rate.The method requires an initial value and an operator with ∥K∥ < 1.
  • Contribution: The paper formulates iterative soft-thresholding as a generalized gradient projection method and develops a unified convergence analysis for related algorithms.The framework supplies a new proof of strong convergence independent of earlier proofs.
  • Main result: Linear convergence holds when K has the finite basis injectivity property or the minimizer has a strict sparsity pattern.Finite basis injectivity concerns the operator, whereas strict sparsity is a property of the minimizer.
  • Extensions: The convergence result extends to frames and dictionaries when the finite basis injectivity property is satisfied.Examples include systems combining trigonometric and Haar wavelet bases under the stated injectivity condition.
  • Main result: For strict sparsity, once the active sign pattern is fixed, the problem is quadratic and the iteration becomes linear from some index onward.The theorem applies to all bounded linear operators in this strict-sparsity case.

2. Iterative soft-thresholding and a generalized gradient projection method

The paper embeds iterative soft-thresholding in a generalized gradient projection framework for minimizing a sum of smooth and non-smooth functionals. In this formulation, proximity steps produce soft-thresholding, while convergence-rate results apply to the specialized algorithm.

  • Generalized framework: The generalized method extends gradient projection to minimization problems combining smooth and non-smooth functionals.It replaces a constraint with a proper, convex, lower semi-continuous functional Φ and applies its proximity operator.
  • Generalized framework: The algorithm initializes a feasible u0, computes successive iterates using a step-size rule and proximity operator, then repeats.The supplied passage describes the three-step iteration procedure.
  • Generalized framework: Solutions of the minimization problem are exactly the fixed points of the generalized algorithm.Choosing Φ as the indicator of a closed convex constraint recovers the classical gradient projection method.
  • Scope: The discussion restricts general convergence-rate statements to the special generalized gradient projection case.Earlier related methods are described as strongly convergent under appropriate conditions but without general rate statements.
  • Iterative soft-thresholding: Iterative soft-thresholding is a special case obtained by choosing F and Φ appropriately, with each proximal subproblem solved by soft-thresholding.Here F′(u) = K∗(Ku − f), and the derivative has Lipschitz constant at most ∥K∥^2.
  • Iterative soft-thresholding: Under the stated operator, data, parameter, and step-size conditions, generalized gradient projection coincides with iterative soft-thresholding.The equivalence is stated in Proposition 1.

3. Convergence of the generalized gradient projection method

The generalized gradient projection framework derives descent and convergence properties for F + Φ, including sublinear functional-gap decay and linear convergence under a distance-to-gap estimate. Bregman-like and Taylor distances provide the key error controls, while step-size conditions ensure descent.

  • Framework and descent: The method interprets iterative soft-thresholding as a generalized gradient projection method and analyzes each iteration through descent of F + Φ.The framework also uses the resolvent/subdifferential formulation underlying one iteration.
  • Framework and descent: Step sizes below 2/L provide a sufficient decrease condition, while a weaker condition can require checking the next iterate a-posteriori.The weaker rule may lose one iteration and increase computation time because unsuccessful step sizes must be replaced.
  • Convergence rates: O(n^-1) functional-gap decay follows when F + Φ is coercive; an additional quadratic distance-to-gap bound upgrades this to exponential gap decay and linear iterate convergence.The latter condition requires a minimizer u* and a constant c > 0 controlling ∥u_n − u*∥^2 by the gap r_n.
  • Error measures: The Bregman-like distance measures the Φ contribution, while the Taylor distance measures the F contribution and both are nonnegative under the stated convexity assumptions.Both distances vanish at minimizers, and their combined control yields the estimate needed for linear convergence.
  • Convergence rates: If R and T jointly control the distance to a minimizer on every bounded sublevel set, the generalized gradient projection iterates converge linearly to a unique minimizer.The theorem applies to convex differentiable F with Lipschitz-continuous derivative and proper, convex, lower-semicontinuous Φ.

4. Convergence rates for the iterative soft-thresholding method

The analysis establishes strong convergence of iterative soft-thresholding and identifies two conditions—FBI or strict sparsity—that yield linear convergence. For compact operators, the convergence constants can be made explicit, while weaker FBI assumptions remain possible.

  • Proof framework: The generalized gradient projection framework converts descent and Bregman-Taylor estimates into the linear convergence result.The Bregman-like and Taylor distances control the relevant error components; both are needed when the penalty is not sufficiently convex.
  • Strong convergence: The iterative soft-thresholding sequence converges strongly to a minimizer under the stated step-size rule.The proof uses descent, an O(n^-1) bound on the associated functional distances, finite-dimensional compactness, and non-expansiveness of proximal mappings.
  • Linear convergence: Linear convergence follows when K has the FBI property or the minimizer has a strict sparsity pattern.These are the two alternative cases used in Theorem 1.
  • Relaxations: The FBI property can be relaxed to injectivity on finite subsets of bounded size, while the remaining proof and linear-rate conclusion remain valid.The relaxation uses FBI of order S=|I| for the finite coefficient set arising in the proof.
  • Explicit constants: For compact operators satisfying FBI, the method admits an explicit geometric estimate ∥u_n−u∗∥≤Cλ^n for some C≥0.The estimate uses u_0=0 and s=∥K∥^-2.

5. Convergence of related methods

The generalized gradient projection analysis extends beyond ordinary iterative soft-thresholding to joint-sparsity thresholding and weighted ℓ1-ball gradient projection. These methods converge strongly under suitable step sizes and linearly under FBI-based conditions.

  • Unified framework: The related methods are analyzable because both can be written as generalized gradient projection methods.This common formulation allows the convergence analysis developed earlier to be reused.
  • Joint sparsity constraints: The joint-sparsity iterative soft-thresholding procedure converges strongly in (ℓ2)^N under the stated step-size rule.The vector-valued coefficients are grouped by index, and proximal mappings reduce to projections associated with the dual norm.
  • Joint sparsity constraints: Under FBI and the additional step-size conditions, joint-sparsity thresholding converges at a linear rate.The proof transfers the Bregman-distance and Bregman-Taylor estimates to vector-valued coefficients using norm equivalence in R^N.
  • Weighted ℓ1-ball projection: For weighted ℓ1-ball constrained minimization, the gradient projection method converges linearly when K satisfies FBI and the prescribed step-size conditions hold.The formulation uses Φ=I_Ω, and the generalized and classical gradient projection methods coincide in this setting.
  • Accelerated methods: The linear result also remains valid for accelerated step-size choices satisfying the referenced condition.The same conclusion is stated for both the weighted ℓ1-ball gradient projection method and the related accelerated procedure.

6. Conclusions

The paper concludes that linear convergence is widespread for iterative soft-thresholding and related generalized gradient projection methods under FBI or strict sparsity conditions. Its speed and scope remain constrained by solution-dependent constants and the assumptions needed for the error estimates.

  • Conclusions: Linear convergence is obtained in many cases, with explicitly calculable constants in some compact-operator settings.The convergence factor generally depends on K, the initial value u_0, and a solution u∗.
  • Limitations: The convergence factor λ can be arbitrarily close to 1 because it depends on a solution, so convergence may be arbitrarily slow.The paper notes that this behavior is also often observed in practice.
  • Conclusions: A strict sparsity pattern connects convergence to eventual linear iteration because the problem becomes quadratic on a fixed sign pattern.The paper relates this observation to other algorithms based on the same structure.
  • Conclusions: The generalized theorem applies broadly because linear convergence follows from descent properties together with Bregman or Bregman-Taylor estimates.This supports a unified treatment of the related algorithms and other penalty terms discussed in the paper.

A. Proof of Theorem 1 (continued)

Under a strict sparsity pattern, thresholding eventually fixes the zero and nonzero coordinate structure, allowing the iteration to reduce to a finite-dimensional contracting subspace. This yields a linear convergence bound for the iterates.

  • Strict sparsity pattern: A strict sparsity pattern is analyzed by separating zero, positive, and negative coordinates and showing that thresholding eventually preserves the minimizer’s pattern.The proof selects indices after which zero coordinates remain zero and nonzero coordinates retain their signs.
  • Subspace decomposition: After a finite index n0, the iteration lies in the orthogonal complement of the kernel component and can be decomposed into complementary subspaces V and V⊥.The kernel component agrees with the minimizer, while the remaining error is represented in V⊥.
  • Subspace decomposition: The restriction to finite-dimensional V⊥ is a strict contraction because K is bounded below there and the induced mappings have contraction factor λ.This is the key mechanism converting eventual pattern identification into linear convergence.
  • Linear convergence: ∥u_n+1 −u∗∥^2 ≤ λ^2∥u_n −u∗∥^2 after n0, establishing geometric decay of the iterate error.The proof then obtains ∥u_n −u∗∥≤Cλ^n for all n.

B. Proof of Theorem 3

The proof establishes an explicit convergence constant by lower-bounding a residual on a suitable bounded set, while using compactness and the FBI property to control the relevant parameters. A constant step-size choice then yields an a-priori linear estimate.

  • Parameter control: The FBI property ensures σ_k > 0, while compactness of K implies μ_k →0 as k →∞.These properties provide the parameter control used in the proof.
  • Explicit constant: The proof seeks c1 > 0 satisfying c1∥P_k(v −u∗)∥^2 ≤ R(v) on a suitable bounded set and for a suitable k.P_k is the orthogonal projection onto sequences whose first k−1 coordinates vanish.
  • A-priori estimate: The resulting a-priori estimate bounds the iterate error geometrically in terms of λ^n, using the initial functional-value bound from u0 = 0.The proof estimates r0 by (F + Φ)(0) = ∥f∥^2/2.
  • Parameter control: With constant step-size s = ∥K∥−2 and δ = 1/2, the proof obtains the desired convergence constant.The selected step size is tied directly to the operator norm.
Loading 0709.1598v4…