Two-point step-size iterative soft-thresholding method for sparse reconstruction

Abstract

Many problems in signal processing involve minimizing a quadratic error term combined with an ℓ₁ norm term. Iterative soft-thresholding (IST) algorithm is a basic method for these problems. Despite previous explanations of IST, this study presents it as a method of constructing a local model to approximate the objective function. It only uses the approximation of the quadratic term while keeping the ℓ₁ norm term unchanged. Based on this, we propose a modified IST (MIST), using a general strictly convex quadratic function to approximate the quadratic part. IST uses the identity matrix to approximate the Hessian matrix of the quadratic term, while we adopt an adaptive matrix by using the information of current and former iterates. This strategy results in the two-point step-size IST, including MIST_BB1 and MIST_BB2. Various experiments on compressed sensing show that MIST_BB1 is much faster than competing codes and insensitive to the regularization parameter.

Keywords:

• two-point step size
• iterative soft-thresholding
• ℓ₁ regularization
• image deconvolution
• compressed sensing

2000 AMS Subject Classifications :

• 47N10
• 80M50
• 65K10

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant No. 60970104) and the Fundamental Research Funds for the Central Universities. The third author was supported by National Natural Science Foundation of China (Grant No. 11001006), and by fundamental research funds for the central universities (Grant No. YWF-10-02-021).