Source-linked AI summary
On a generalization of the iterative soft-thresholding algorithm for the case of non-separable penalty
Ignace Loris, Caroline Verhoeven
TL;DR
The paper addresses ℓ1-penalized least squares with a non-separable penalty induced by a linear operator A. It proposes an explicit proximity-based iterative algorithm with proven convergence, connecting the general problem to soft-thresholding and gradient projection special cases. The averaged iterates achieve a 1/N convergence rate for the functional.
Problem
The paper studies minimization of a quadratic data-misfit term plus a non-smooth, non-separable penalty ∥Ax∥1 in inverse problems and imaging.
Method
The method uses four matrix-vector multiplications and a simple projection or proximity operator per iteration, without requiring proxH(A·).
Results
The averaged iterates have a 1/N convergence rate for the functional, and the method reduces to iterative soft-thresholding when A=1.
Takeaways & Limitations
The framework handles general convex non-separable penalties while retaining an explicit iteration that avoids non-trivial minimizations, linear systems, and projections.
Takeaways & Limitations
The convergence proof is restricted to finite dimensions, and the functional need not decrease monotonically at every iteration.
Abstract
from arXiv · showhide
An explicit algorithm for the minimization of an $\ell_1$ penalized least squares functional, with non-separable $\ell_1$ term, is proposed. Each step in the iterative algorithm requires four matrix vector multiplications and a single simple projection on a convex set (or equivalently thresholding). Convergence is proven and a 1/N convergence rate is derived for the functional. In the special case where the matrix in the $\ell_1$ term is the identity (or orthogonal), the algorithm reduces to the traditional iterative soft-thresholding algorithm. In the special case where the matrix in the quadratic term is the identity (or orthogonal), the algorithm reduces to a gradient projection algorithm for the dual problem. By replacing the projection with a simple proximity operator, other convex non-separable penalties than those based on an $\ell_1$-norm can be handled as well.
1 Introduction
The paper develops an explicit, convergent algorithm for ℓ1-penalized least squares when the penalty is non-separable through a linear operator A. It connects this general case to iterative soft-thresholding and avoids non-trivial subproblems in each iteration.
- 1 Introduction: The method targets ℓ1-penalized least squares with a non-separable penalty ∥Ax∥1, where K mixes variables in the data term and A mixes variables in the penalty.The quadratic term is smooth and convex, while the penalty is convex and non-smooth.
- 1 Introduction: The proposed iteration uses four matrix-vector multiplications and one simple projection onto an ℓ∞ ball, or equivalently a thresholding operation.The multiplications are by K, K^T, A, and A^T.
- 1 Introduction: The framework extends beyond the ℓ1 penalty by replacing projection and soft-thresholding with proximity operators for a general convex function H.The method requires proxH* rather than proxH(A·).
- 1 Introduction: The paper proves convergence and a 1/N functional rate for averages of the generalized soft-thresholding iterates.This bridges the general A ≠ 1 setting with the established A = 1 iterative soft-thresholding case.
- 1 Introduction: The algorithm is designed for cases where existing methods require a non-trivial minimization, linear-system solution, or projection onto a non-trivial convex set.The authors emphasize settings where K and A lack special structure that makes those subproblems easy.
- 1 Introduction: The analysis does not introduce a smoothing parameter, and it is not an iteratively reweighted least-squares algorithm.The paper notes that an O(1/N^2) algorithm and speed gains from solving a linear system at every iteration remain open questions.
2 Mathematical tools
The paper formulates the method using convex conjugates, subdifferentials, and proximity operators. For the ℓ1 penalty, these operators reduce to explicit projection and soft-thresholding maps that are simple to implement.
- 2 Mathematical tools: The framework assumes that H and its convex conjugate H* are proper, lower semi-continuous, convex functions on a finite-dimensional real vector space.The finite-dimensional setting is part of the paper’s stated assumptions.
- 2 Mathematical tools: For H(u)=λ∥u∥1, proxH* is the projection Pλ onto the ℓ∞ ball, while proxH is the componentwise soft-thresholding operator Sλ.These explicit operators provide the computational primitives for the algorithm.
- 2 Mathematical tools: The same componentwise notation for Pλ and Sλ applies when variables are scalar, vector-valued, or arranged as lists of such elements.This includes (Ax)i∈R2 when A is the gradient of a two-dimensional image.
- 2 Mathematical tools: Proximity operators characterize subdifferential membership: u∈∂H(u+) exactly when u+=proxH(u++u).This identity connects the nonsmooth optimality condition to a computable proximity operation.
- 2 Mathematical tools: The projection and soft-thresholding operators are linked through the proximity-operator identity for a function and its convex conjugate.The paper uses this dual relationship to move between H and H*.
3 Variational equations and special cases
The variational formulation expresses optimality through coupled primal-dual equations and a saddle-point problem. Known special cases recover forward-backward soft-thresholding or gradient projection methods.
- 3 Variational equations and special cases: The optimality conditions are KT(y−Kx)−ATw=0 and w=proxH*(w+Ax), and the algorithm is designed to converge to a solution of these equations.The paper assumes that at least one solution (x̂,ŵ) exists.
- 3 Variational equations and special cases: Using H(Ax)=supw⟨Ax,w⟩−H*(w), the minimization problem becomes a saddle-point problem whose solutions correspond to the variational equations.The associated gap is non-negative for all primal and dual variables.
- 3 Variational equations and special cases: When A=1 and H(x)=λ∥x∥1, the problem is solved by the traditional iterative soft-thresholding algorithm.Soft-thresholding makes every iterate contain many exact zeros.
- 3 Variational equations and special cases: When K=1, the problem can be solved by a gradient projection algorithm for a quadratic minimization over a convex set.In this case Ax need not be sparse at every iteration; sparsity appears only in the limit.
4 Algorithm
The paper develops a fixed-point iteration for the saddle-point equations, interpretable as a predict-correct method, with special cases recovering iterative soft-thresholding and gradient projection.
- Algorithm: The proposed iteration is designed to converge to the fixed-point equations and thereby solve the minimization problem.
- Algorithm: The iteration alternates gradient steps in x with a proximal ascent step in w, forming a predict-correct method for the saddle-point problem.An equivalent pseudo-implicit form is useful for proving convergence.
- Algorithm: The algorithm can also be viewed as gradient descent on the quadratic term followed by one dual-variable update from the previous dual iterate.
- Special cases: When A is orthogonal and H = λ||·||1, the method reduces to iterative soft-thresholding.
- Special cases: When K is orthogonal and H = λ||·||1, the method reduces to the gradient projection algorithm for data g = K^T y.
5 Convergence
The convergence analysis establishes that the iterates approach a solution of the variational equations and provides convergence guarantees for averaged iterates under stated assumptions.
- Proof structure: The proof uses saddle-point inequalities and a gap function, but the gap is not itself a measure of distance because zero gap need not imply a saddle point.
- Convergence theorem: Under the stated assumptions, the sequence converges to a solution of the variational equations, yielding a minimizer and a saddle point.
- Convergence theorem: The averaged first N iterates converge to the saddle point, with a functional convergence estimate bounded by a constant divided by N.
- Proof structure: The analysis establishes boundedness and convergence through norm inequalities, subsequence convergence, and continuity of the proximity operator.
- Rate conditions: The rate proof allows a constant C1 independent of N, with C1 equal to zero when ||K||≤1, and separately requires bounded dual variables for another estimate.
6 Discussion
The discussion presents a scaled explicit algorithm for the general convex-penalty problem, establishes convergence under step-size conditions, and situates its novelty and scope relative to existing methods.
- Algorithm and convergence: The scaled algorithm uses four matrix-vector operations and proximal updates, with step sizes constrained by τ < 2/∥K^TK∥ and σ < 1/∥AA^T∥.For the ℓ1 case, the dual update uses projection onto the ℓ∞ ball, while the primal update uses K, K^T, A, and A^T.
- Algorithm and convergence: The convergence proof covers A = 1 by adaptation, despite the main proof condition ∥A∥ < 1 excluding that case directly.The paper explicitly notes that the theorem’s proof can be slightly modified to include A = 1.
- General penalties: The method needs only proxH* rather than proxH(A·), allowing simple dual proximal operators when the composed primal operator is difficult.This is especially useful for non-separable penalties whose composition with A lacks a simple proximity operator.
- Relation to prior work: The authors identify the explicit one-dual-step construction as distinct from related methods requiring non-explicit iterations, linear-system solves, or additional dual variables.The discussion also connects the method to gradient steps, dual algorithms, and saddle-point schemes while distinguishing their computational requirements.
- Algorithm and convergence: The algorithm converges to a saddle point and a minimizer, with a 1/N functional bound for averaged iterates under an additional boundedness condition.The paper contrasts this with prior results requiring both primal and dual variables to be bounded; here only the dual variable must be bounded for the stated bound.
- Limitations: The convergence analysis is finite-dimensional, and the total-variation operator A = grad is unbounded in the infinite-dimensional setting.The paper therefore does not extend its convergence proof to infinite-dimensional spaces.
7 Numerical example of total variation minimization
A synthetic seismic tomography experiment applies the algorithm with a total variation penalty to reconstruct a piecewise-constant spherical model from sparse noisy ray data. After 1000 iterations, sharp edges are reasonably resolved and the functional is close to its limiting value.
- Numerical example: The experiment reconstructs a 98304-dimensional synthetic spherical model from 8490 seismic surface-ray measurements using total variation regularization.The input contains zones with both sharp and smooth edges, and the rays correspond to actual earthquake-station geometries.
- Numerical example: After 1000 iterations, the reconstruction has a 10% residual error relative to a reference minimizer and about 3 correct decimals of the minimal functional value.The reported reconstruction is xout = x1000, obtained in about 20 seconds with λ chosen so the residual matches the noise level.
- Numerical example: The total variation penalty produces a piecewise-constant output, with sharp edges reasonably well resolved despite the small amount of available data.The reported example specifically notes successful resolution of sharp features near North America.