Two-Step Algorithms for Linear Inverse Problems with Non-Quadratic Regularization

Iterative shrinkage/thresholding (IST) algorithms have been recently proposed to handle high-dimensional convex optimization problems arising in image inverse problems (namely deconvolution) under non-quadratic regularization (e.g., total variation or sparsity inducing regularizers on wavelet representations). The convergence speed of IST algorithms depends heavily on the nature of the direct operator, being very slow when this operator is severely ill-conditioned. In this paper, we introduce a two-step version of IST (termed 2IST, pronounced "twist") showing much faster convergence for strongly ill-conditioned operators. We give theoretical results concerning the convergence behavior of 2IST and show its effectiveness for wavelet-based and total variation image deconvolution.