On a generalization of the iterative soft-thresholding algorithm for the case of non-separable penalty

By Ignace Loris, Caroline Verhoeven. 2011

152 citations recorded by the source corpus.

An explicit algorithm for the minimization of an ℓ1-penalized least-squares functional, with non-separable ℓ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 ℓ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 ℓ1-norm can be handled as well.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Distributed Fixed Point Methods with Compressed Iterates (2019, neutral): “The PAPC algorithm [10,17,32] is an algorithm for minimizing F + H ◦ L , where F is smooth and convex, H is nonsmooth and convex and L is a linear operator.”
A primal-dual algorithm with optimal stepsizes and its application in decentralized consensus optimization (2017, methodology): “:3) l degenerates to h , and the problem (1) becomes It is equivalent to the following saddle-point problem In order to solve (2) (or (3)), a primal-dual algorithm was proposed in diﬀerent ﬁelds under diﬀerent names [5,9,16].”
Distributed Proximal Splitting Algorithms with Rates and Acceleration (2020, methodology): “So, when R 0, both the PD3O and PPDY revert to an algorithm which, for ck ≡ c, is the Loris–Verhoeven algorithm (Loris and Verhoeven, 2011; Combettes et al., 2014; Condat et al., 2019a).”
Dualize, Split, Randomize: Fast Nonsmooth Optimization Algorithms (2020, methodology): “In the deterministic case gk+1 = ∇F (xk), LiCoSGD reverts to an instance of the algorithm first proposed by Loris and Verhoeven in [52], and rediscovered independently as the PDFP2O algorithm [15] and the Proximal Alternating Predictor-Corrector (PAPC) algorithm [30].”
Proximal Splitting Algorithms: A Tour of Recent Advances, with New Twists. (2020, methodology): “This analysis is subsequently applied in Section 3 to the Loris–Verhoeven algorithm, which is a primal–dual forward–backward algorithm.”
A New Primal–Dual Algorithm for Minimizing the Sum of Three Functions with a Linear Operator (2016, methodology): “In particular, we show that our proposed algorithm recovers Chambolle–Pock [4], PAPC [7,17, 27], and Davis–Yin [15].”