Iterative Thresholding Algorithms

The iterative thresholding algorithm for image restorations was first introduced in [10].  The key idea of [10] is to perform a thresholding operation to wavelet frame coefficients of images at each step to get a sparse approximate solution in the wavelet frame transform domain. The convergence analysis led to the sparsity-based balanced model for image restoration using wavelet frames in [8]. (see also e.g. survey papers.)

Both hard and soft thresholding operators were tested in [10]. The efficiency of an iterative thresholding algorithm depends on which thresholding operator is used. Hard-thresholding is a favorite choice since it is unbiased for large observations and easy to implement.  A complete analysis of the convergence of iterative hard thresholding algorithms for the wavelet frame models was given in [2]. However, it is unstable due to discontinuity. Many efforts have been made to smoothen and stabilize the hard thresholding. Soft-thresholding is one of the popular choices.  For example, it was used in wavelet frame-based image restorations for the balanced model in [3, 8 ], the synthesis model in [7],  and the analysis model in [4]. Soft thresholding is stable but has a large bias for large observations. Many thresholding operators were constructed in literature by interpolating between the hard and soft thresholding to balance the “sparsity”, “continuity/stability”, and “unbiasedness”.  The thresholding operators generated by proximal operators of the p-norm variational model with p being smaller than one were used in [9]. Furthermore, various PDE-based models may be understood as different ways to design thresholding\shrinkage operators for wavelet frame-based iterative thresholding algorithms, since wavelet frame transforms are discretizations of PDE models.  However, it is unclear in which sense an optimal balanced point between the sparsity and unbiasedness can be reached for given continuity of the thresholding.

In [1], we gave an optimal thresholding operator by minimizing the summation of variance and squared bias. This is the best one in balancing the “sparsity”, “continuity/stability”, and “unbiasedness”. The corresponding iterative thresholding algorithm converges to the limiting point that attains the minimum of the mean square error along each coordinate when the other coordinates are fixed.  This optimal property of the limit point is not available for algorithms using any other thresholding except for those algorithms using soft thresholding since the convex optimization theory can be applied in this case as shown in  [3, 4, 5, 6, 7, 8].

The ideas, algorithms, and models developed here for the wavelet frame-based image denoising,  deblurring, and inpainting were modified and adapted to applications such as blind deblurring, the iterative singular value thresholding algorithm for low rank matrix completion, and many other applications. (see also e.g. survey papers.)

    1. Tongyao Pang, Zuowei Shen, Sparse Estimation: An MMSE Approach, Constructive Approximation, (202x) to appear.PDF
    2. Chenglong Bao, Bin Dong, Likun Hou, Zuowei Shen, Xiaoqun Zhang, Xue Zhang, Image5, restoration by minimizing zero norm of wavelet frame coefficients, Inverse Problems, 32(1), (2016). PDF
    3. Zuowei Shen, Kim-Chuan Toh, Sangwoon Yun, An accelerated proximal gradient algorithm for frame-based image restoration via the balanced approach, SIAM Journal on Imaging Sciences, 4 (2) (2011), 573-596. PDF
    4. Jianfeng Cai, Stanley Osher, Zuowei Shen, Split Bregman methods and frame based image restoration, Multiscale Modeling and Simulation: A SIAM Interdisciplinary Journal 8(2), (2009), 337-369. PDF
    5. Jianfeng Cai, Stanley Osher, Zuowei Shen, Linearized Bregman iterations for compressed sensing, Mathematics of Computation, 78 (2009), 1515-1536. PDF
    6. Jianfeng Cai, Stanley Osher, Zuowei Shen, Convergence of the linearized Bregman iteration for l_1-norm minimization, Mathematics of Computation, 78 (2009), 2127-2136. PDF
    7. Jianfeng Cai, Stanley Osher, Zuowei Shen, Linearized Bregman iteration for frame based image deblurring, SIAM Journal on Imaging Sciences, 2(1) (2009), 226-252.PDF
    8. Jianfeng Cai, Raymond Chan, Zuowei Shen, A framelet-based image inpainting algorithm, Applied and Computational Harmonic Analysis, 24 (2008), 131-149. PDF
    9. Anwei Chai, Zuowei Shen, Deconvolution: A wavelet frame approach, Numerische Mathematik, 106 (2007), 529-587. deconvolution.pdf
    10. Raymond Chan, Tony Chan, Lixin Shen, Zuowei Shen, Wavelet algorithms for high-resolution image reconstruction, SIAM Journal on Scientific Computing, 24 (2003) 1408-1432. cs1.pdf