ℓ₀-minimization methods for image restoration problems based on wavelet frames

In this paper we consider a class of ℓ0-minimization and wavelet frame-based models for image deblurring and denoising. Mathematically, they can be formulated as minimizing the sum of a data fidelity term and the ℓ0-'norm' of the framelet coefficients of the underlying image, and we are particularly interested in three different types of data fidelity forms for image restoration problems. We first study the first-order optimality conditions for these models. We then propose a penalty decomposition (PD) method for solving these problems in which a sequence of penalty subproblems are solved by a block coordinate descent (BCD) method. Under some suitable assumptions, we establish that any accumulation point of the sequence generated by the PD method satisfies the first-order optimality conditions of these problems. Moreover, for the problems in which the data fidelity term is convex, we show that such an accumulation point is a local minimizer of the problems. In addition, we show that any accumulation point of the sequence generated by the BCD method is a block coordinate minimizer of the penalty subproblem. Furthermore, under some convexity assumptions on the data fidelity term, we prove that such an accumulation point is a local minimizer of the penalty subproblem. Numerical simulations show that the proposed ℓ0-minimization methods enjoy great potential for image deblurring and denoising in terms of solution quality and/or speed.