l0-minimization methods for image restoration problems based on wavelet frames

In this paper we consider a class of l(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 l(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 l(0)-minimization methods enjoy great potential for image deblurring and denoising in terms of solution quality and/or speed.