A New TwIST: Two-Step Iterative Shrinkage/Thresholding Algorithms for Image Restoration
By José M. Bioucas-Dias, Mário A. T. Figueiredo. IEEE Transactions on Image Processing, 2007
2,025 citations recorded by the source corpus.
Iterative shrinkage/thresholding (1ST) algorithms have been recently proposed to handle a class of convex unconstrained optimization problems arising in image restoration and other linear inverse problems. This class of problems results from combining a linear observation model with a nonquadratic regularizer (e.g., total variation or wavelet-based regularization). It happens that the convergence rate of these 1ST algorithms depends heavily on the linear observation operator, becoming very slow when this operator is ill-conditioned or ill-posed. In this paper, we introduce two-step 1ST (TwIST) algorithms, exhibiting much faster convergence rate than 1ST for ill-conditioned problems. For a vast class of nonquadratic convex regularizers (lscrP norms, some Besov norms, and total variation), we show that TwIST converges to a minimizer of the objective function, for a given range of values of its parameters. For noninvertible observation operators, we introduce a monotonic version of TwIST (MTwIST); although the convergence proof does not apply to this scenario, we give experimental evidence that MTwIST exhibits similar speed gains over IST. The effectiveness of the new methods are experimentally confirmed on problems of image deconvolution and of restoration with missing samples.
Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Physics
View Paper: https://www.semanticscholar.org/paper/0acd253741fede941cf323e577d4f9dfabb4636b
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
- Lei Zhang
- Wangmeng Zuo
- Francis R. Bach
- Thomas Pock
- Stephen P. Boyd
- Julien Mairal
- Wotao Yin
- José M. Bioucas-Dias
In Computer Vision and Pattern Recognition
- Lei Zhang
- Luc Van Gool
- Wangmeng Zuo
- Ming-Hsuan Yang
- Dacheng Tao
- Chen Change Loy
- Radu Timofte
- Xiaogang Wang
In Mathematical Physics
- Stephen P. Boyd
- Lei Zhang
- Thomas Pock
- Antonin Chambolle
- Laurent Condat
- Wotao Yin
- José M. Bioucas-Dias
- Jean-Christophe Pesquet
Citations in the corpus
- Solving Inverse Problems With Piecewise Linear Estimators: From Gaussian Mixture Models to Structured Sparsity (2010, neutral): “The PLE deblurring is compared with a number of deconvolution algorithms: “ForWaRD” (Fourier-wavelet regularized deconvolution) [ 61], “TVB” (total variation based) [7], “TwIST” (two-step itera tive shrinkage/thresholding) [6], “SP” (sparse prior) [44], “S A-DCT” (shape adaptive DCT) [30], “BM3D” (3”
- An introduction to Total Variation for Image Analysis (2009, background): “See also [15] for similar accelerations for a smaller class of problems.”
- A Survey of Sparse Representation: Algorithms and Applications (2015, methodology): “For example, Bioucas-Dias and Figueirdo [174] introduced a two-step iterative shrinkage/thresholding (TwIST) algorithm for image restoration, which is more efficient and can be viewed as an extension of the IST method.”
- A Miniature Electrical Impedance Tomography Sensor and 3-D Image Reconstruction for Cell Imaging (2017, background): “(8) with nonquadratic convex regularizer is solved by a Two-step Iterative Shrinkage/Thresholding Algorithm (TwIST) [30], which exhibits fast convergence rate for ill-conditioned problems.”
- Plug-and-Play Priors for Bright Field Electron Tomography and Sparse Interpolation (2015, methodology): “The solution to equation (1) may be computed using a variety of optimization methods, such as the alternating direction method of multipliers (ADMM), the fast iterative shrinkage thresholding algorithm (FISTA) [52], the two-step iterative shrinkage thresholding (TwIST) [53], or sparse reconstruction”
- Image denoising with nonlocal spectral graph wavelets (2010, neutral): “This is a BPDN/Lasso problem in Lagrangian form with a synthesis sparsity prior and thus admits a global minimum which can be found by well established minimization techniques like the iterative soft thresholding (IST) [41], the forward-backward (FB) splitting [42], or related approaches [43, 44].”
- Generalized alternating projection based total variation minimization for compressive sensing (2015, methodology): “On the other hand, the total variation (TV) based algorithms have demonstrated high performance on variously CS problems [20–25].”
- Multiplicative Noise Removal Using Variable Splitting and Constrained Optimization (2009, neutral): “Even when the log-likelihood is convex (as in [27], [34], [37], [38]), it does not have a Lipschitz-contin uous gradient, which is a necessary condition for the applicabil ity (with guaranteed convergence) of algorithms of the forward backward splitting (FBS) class [3], [6], [13], [41].”
- Half-Quadratic-Based Iterative Minimization for Robust Sparse Representation (2014, methodology): “Based on conjugate function, a loss function in image restoration and signal recovery can be defined as [33], [39], [40],”
- Mask-guided Spectral-wise Transformer for Efficient Hyperspectral Image Reconstruction (2021, methodology): “We compare our MST with several SOTA HSI reconstruction algorithms, including three model-based methods (TwIST [4], GAP-TV [57], and DeSCI [27]) and six CNNbased methods (λ-net [36], HSSP [49], DNU [50], PnPDIP-HSI [35], TSA-Net [33], and DGSMP [18]).”
- A Field Guide to Forward-Backward Splitting with a FASTA Implementation (2014, background): “While several predictor-corrector variants of FBS have been proposed (see for example [41]), the algorithm FISTA has become quite popular because of its lack of tuning parameters and good worst-case performance.”