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

Abstract

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.

17 pages; 1 figure; results formulated for a more general penalty than previous version; numerical example added

References in corpus (1)

• Fast Image Recovery Using Variable Splitting and Constrained Optimization

Cited by in corpus (18)

• Fixed Point Strategies in Data Science
• Smoothing and Decomposition for Analysis Sparse Recovery
• Variable metric inexact line-search based methods for nonsmooth optimization
• Iterative algorithms for total variation-like reconstructions in seismic tomography
• Controlled Wavelet Domain Sparsity in X-ray Tomography
• Linearly-involved Moreau-Enhanced-over-Subspace Model: Debiased Sparse Modeling and Stable Outlier-Robust Regression
• Testing and non-linear preconditioning of the proximal point method
• Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms
• A very fast iterative algorithm for TV-regularized image reconstruction with applications to low-dose and few-view CT
• Bregman three-operator splitting methods
• Distributed Proximal Splitting Algorithms with Rates and Acceleration
• First-order primal-dual methods for nonsmooth nonconvex optimisation
• New convergence analysis of a primal-dual algorithm with large stepsizes
• A projected gradient method for $\alpha {\ell }_1-\beta {\ell }_2$ sparsity regularization
• Easily parallelizable and distributable class of algorithms for structured sparsity, with optimal acceleration
• Uniqueness of DRS as the 2 Operator Resolvent-Splitting and Impossibility of 3 Operator Resolvent-Splitting
• Joint demosaicing and fusion of multiresolution coded acquisitions: A unified image formation and reconstruction method
• Convergence analysis of a primal-dual optimization-by-continuation algorithm