An iterative linear expansion of thresholds for ℓ₁-based image restoration

This paper proposes a novel algorithmic framework to solve image restoration problems under sparsity assumptions. As usual, the reconstructed image is the minimum of an objective functional that consists of a data fidelity term and an ℓ₁ regularization. However, instead of estimating the reconstructed image that minimizes the objective functional directly, we focus on the restoration process that maps the degraded measurements to the reconstruction. Our idea amounts to parameterize the process as a linear combination of few elementary thresholding functions (LET) and to solve the linear weighting coefficients by minimizing the objective functional. It is then possible to update the thresholding functions and to iterate this process ( i-LET). The key advantage of such a linear parametrization is that the problem size reduces dramatically--each time we only need to solve an optimization problem over the dimension of the linear coefficients (typically less than 10) instead of the whole image dimension. With the elementary thresholding functions satisfying certain constraints, a global convergence of the iterated LET algorithm is guaranteed. Experiments on several test images over a wide range of noise levels and different types of convolution kernels clearly indicate that the proposed framework usually outperforms state-of-the-art algorithms in terms of both the CPU time and the number of iterations.