Linear Convergence of Iterative Soft-Thresholding

By Kristian Bredies, Dirk A. Lorenz. 2007

294 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/0dd58bd61d4d82f566db8edcc18999d53fe6bfc1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Mathematical Physics

Citations in the corpus

High-resolution prestack seismic inversion using a hybrid FISTA least-squares strategy (2013, background): “ISTA is known to have linear convergence (Bredies and Lorenz, 2008), but FISTA is shown to be faster by several orders of magnitude.”
An introduction to continuous optimization for imaging (2016, background): “…smoother than during the first iterations, and some authors have succeeded in exploiting this ‘partial smoothness’ to show better (linear) convergence of the FB descent (Bredies and Lorenz 2008, Grasmair, Haltmeier and Scherzer 2011, Liang, Fadili and Peyré 2014, Tao, Boley and Zhang 2015).”
Fast global convergence rates of gradient methods for high-dimensional statistical recovery (2010, methodology): “For the special case of sparse linear regression with random isotropic designs (also referred to as compressed sensing), some authors have established local linear convergence, meaning guarantees that apply once the iterates are close enough to the optimum [9, 17].”
Necessary and sufficient conditions for linear convergence of ℓ1‐regularization (2011, methodology): “In contrast, in [23, 24, 34], we have derived linear convergence rates on the whole space X , assuming an additional injectivity condition originally introduced in [5, 28].”
Inverse problems in spaces of measures (2013, methodology): “It will turn out that this method is an instance of a combination between a generalized conditional gradient method (see [5, 7]) and the well-known iterative soft-thresholding method (or, more generally, a generalized gradient projection method [6]).”
A Generalized Forward-Backward Splitting (2011, unknown): “on convergence rate analysis (on the objective in general) and accelerated versions of the forward-backward algorithm [8, 9, 61] might inspire one to study those of our GFB (for the case where β > 0).”
Proximal Splitting Methods in Signal Processing (2009, background): “the problem [8, 35, 58, 89, 96, 97, 108, 112, 136]. Another type of convergence rate is that pertaining to the objective values (f 1(xn)+f 2(xn))n≥0. This rate has been investigated in several places [13, 21, 80] and variants of (14) have been developed to improve it [13, 14, 81, 100, 123, 128] (not”
Fast global convergence of gradient methods for high-dimensional statistical recovery (2011, background): “, [3, 7, 6, 5, 12, 18]) focuses on polynomial-time algorithms for solving these types of convex programs.”
A non-adapted sparse approximation of PDEs with stochastic inputs (2010, methodology): “Numerous solvers based on the active set [54,36], interior-point continuation [21,42] and projected gradient [25,23,39,13,9,62,3,4] methods have been developed for solving the above formulations of the ‘1-minimization problem.”
Sparse regularization with lq penalty term (2008, background): “In this case, if the differential of the operator satisfies a certain injectivity condition, we can show that the actual convergence rate improves up to O(δ).”