SUBMITTED FOR PUBLICATION; 2007. 1 Majorization-Minimization Algorithms for Wavelet-Based Image Restoration

Abstract — Standard formulations of image/signal deconvolution under wavelet-based priors/regularizers lead to very high dimensional optimization problems involving the following difficulties: the non-Gaussian (heavy-tailed) wavelet priors lead to objective functions which are non-quadratic, usually nondifferentiable and sometimes even non-convex; the presence of the convolution operator destroys the separability which underlies the simplicity of wavelet-based denoising. This paper presents a unified view of several recently proposed algorithms for handling this class of optimization problems, placing them in a common majorization-minimization (MM) framework. One of the classes of algorithms considered (when using quadratic bounds on nondifferentiable log-priors) shares the infamous “singularity issue” (SI) of “iteratively reweighted least squares ” (IRLS) algorithms: the possibility of having to handle infinite weights, which may cause both numerical and convergence issues. In this paper, we prove several new results which strongly support the claim that the SI does not compromise the usefulness of this class of algorithms. Exploiting the unified MM perspective, we introduce a new algorithm, resulting from using ℓ1 bounds for non-convex regularizers; the experiments confirm the superior performance of this method, when compared to the one based on quadratic majorization. Finally, an experimental comparison of the several algorithms, reveals their relative merits for different standard types of scenarios