1 Introduction

Image deblurring under Poisson noise is an important task in various applications such as astronomical images [26, 39], positron emission tomography (PET) [4, 29], and single particle emission computed tomography (SPECT) [18, 31]. In this paper, we focus on the following image reconstruction model:

$$\begin{aligned} g=\text{ Poisson }(Af+c\mathbf {e}), \end{aligned}$$
(1.1)

where \(g\in \mathbb {R}^n\) is the observed image, \(\mathbf {e}:=(1,\ldots ,1)^T\in \mathbb {R}^n\) is a vector of all ones, \(c\ge 0\) is a fixed background, \(A\in \mathbb {R}^{n\times n}\) is a spatial-invariant blur matrix, \(f\in \mathbb {R}^n\) is a column vector concatenated from the original image with size \(m_1\times m_2\) (\(n=m_1m_2\)), and \(\text{ Poisson }(\cdot )\) denotes the degradation by Poisson noise. We remark that A is a matrix of block Toeplitz with Toeplitz blocks when zero boundary conditions are applied, and block Toeplitz-plus-Hankel with Toeplitz-plus-Hankel blocks when Neumann boundary conditions are used [27, 28].

An approach to deal with the images corrupted by Poisson noise is the maximum a posterior (MAP) estimate [5, 7, 16, 20, 49]. Assume that the observed data \(g_i\) are independent random variables, then the probability distribution of g is the product of the probability distributions of all pixels [37], which can be described as follows:

$$\begin{aligned} P(g|f)=\prod _{i=1}^n\frac{[(Af+c\mathbf {e})_i]^{g_i}e^{-(Af+c\mathbf {e})_i}}{g_i!}, \end{aligned}$$

where \((Af+c\mathbf {e})_i\) and \(g_i\) denote the ith components of \(Af+c\mathbf {e}\) and g, respectively. By taking the negative logarithm of the probability distribution, the Kullback-Leibler (KL) divergence \(D_{KL}(Af+c\mathbf {e},g)\) of \(Af+c\mathbf {e}\) from g is given by [13]

$$\begin{aligned} \begin{aligned} D_{KL}(Af+c\mathbf {e},g):=\sum _{i=1}^n(Af+c\mathbf {e})_i-g_i\log ((Af+c\mathbf {e})_i)+\log (g_i!), \end{aligned} \end{aligned}$$

which is convex, nonnegative, and coercive on the nonnegative orthant. When the constants are omitted, we obtain the following data fidelity term

$$\begin{aligned} \Phi (f):=\mathbf {e}^T(Af+c\mathbf {e})-g^T\log (Af+c\mathbf {e}), \end{aligned}$$

where the notation \(^T\) denotes the transpose operator and \(\log (\cdot )\) means componentwise. The maximum likelihood estimator of the original image is the minimizer of \(\Phi (f)\). It is known that the Richardson-Lucy (RL) algorithm can be applied to solve this problem [24, 32]. There are also a number of important works on RL algorithm, including [9, 14, 37, 41], to name only a few. However, the RL algorithm converges slowly and yields high noise estimate [43].

To deal with the ill-posed problem, a regularization term should be added to control the noise. Traditional regularization methods include the Tikhonov-like regularization [42] and the total variation (TV) regularization [35]. Although the Tikhonov-like regularization method has the advantage of simple calculations [17], it tends to make images unduly smooth and often fails to adequately save important image attributes such as sharp edges. By contrast, the TV regularization, first proposed by Rudin, Osher, and Fatemi for image denoising in [35] and then extended to image deconvolution in [34], has become very popular to represent the prior of images due to its ability to preserve sharp edges. In addition, Acar et al. [1] analyzed the advantages of the TV regularization over the Tikhonov-like regularization for recovering images including piecewise smooth objects.

Based on the prior information of an image, we use the TV as the regularization term. Then, a discrete version of the TV deblurring problem under Poisson noise is given by [23]

$$\begin{aligned} \min _{f\ge 0} \ \alpha \left( \mathbf {e}^T(Af+c\mathbf {e})-g^T\log (Af+c\mathbf {e})\right) + \sum _{i=1}^n \Vert D_if\Vert , \end{aligned}$$
(1.2)

where \(\alpha \) is a regularization parameter to balance the regularization term and the KL divergence term, the nonnegative constraint \(f\ge 0\) guarantees that no negative intensities occur in the restored images, \(\Vert \cdot \Vert \) denotes the Euclidean norm of a vector, and \(D_if\in \mathbb {R}^2\) denotes the first-order finite difference of f at pixel i in both horizontal and vertical directions. More specifically, let f be extended by periodic boundary conditions, where \(f:=(f_1,f_2,\ldots , f_n)^T\). Then, for \(i=1,\ldots , n\), \(D_if\) is defined as

$$\begin{aligned} D_if:=((D_xf)_i,(D_yf)_i)^T, \end{aligned}$$

where

$$\begin{aligned} (D_xf)_i= \left\{ \begin{array}{lll} f_{i+m_2}-f_i, &{} \text{ if } \ 1\le i\le m_2(m_1-1),\\ f_{mod (i,m_2)}-f_i, &{} \text{ otherwise },\\ \end{array}\right. \end{aligned}$$

and

$$\begin{aligned} (D_yf)_i= \left\{ \begin{array}{lll} f_{i+1}-f_i, &{} \text{ if } \ mod (i,m_2)\ne 0,\\ f_{i-m_2+1}-f_i, &{} \text{ otherwise }.\\ \end{array}\right. \end{aligned}$$

Here \(mod (i,m_2)\) denotes the remainder of i divided by \(m_2\).

The computational challenges of this model are that the KL divergence is non-quadratic and contains a logarithm function. The algorithms of image restoration based on the quadratic data fitting term cannot be applied to this model directly. Moreover, since the TV term is non-differentiable, it is difficult to solve the Euler-Lagrange equation associated with the minimization model (1.2). Recently, some efficient algorithms are proposed to solve the Poisson noise removal problem. Le et al. [23] proposed a gradient descent method to solve a variational image restoration model under Poisson noise. It is well known that the convergence speed of the gradient descent method is very slow. Moreover, Figueiredo et al. [15] proposed an augmented Lagrangian (PIDAL) method for deconvolving Poissonian images. But it needs to solve a TV denoising subproblem under their splitting strategy, which cannot be solved exactly. Furthermore, Setzer et al. [36] proposed an alternating split Bregman algorithm (called PIDSplit+) for the restoration of blurred images corrupted with Poissonian noise. Although the resulting subproblems have closed-form solutions, this algorithm converges slowly after reaching a low accuracy.

In this paper, we focus on developing a fast algorithm to solve the constrained minimization model (1.2). By putting the constrained set into the objective function, we obtain the following unconstrained optimization problem

$$\begin{aligned} \min _f \ \alpha \left( \mathbf {e}^T(Af+c\mathbf {e})-g^T\log (Af+c\mathbf {e})\right) +\sum _{i=1}^n \Vert D_if\Vert + \delta _{\mathbb {R}_+^{n}}(f), \end{aligned}$$
(1.3)

where \(\delta _{\mathbb {R}_+^{n}}(\cdot )\) is the indicator function over \(\mathbb {R}_+^{n}\). Let \(u\in \mathbb {R}^n\) be an auxiliary variable that approximates \(Af+c\mathbf {e}\) in (1.3). Similarly, we introduce \(w_i\in \mathbb {R}^2\) to approximate \(D_if\) and z to approximate f. By adding the quadratic terms to penalize the differences between every pair of original and auxiliary variables, we obtain the following problem

$$\begin{aligned} \min _{u,z,w,f} \ \mathcal {Q}(u,z,w,f):= & {} \ \alpha \left( \mathbf {e}^Tu-g^T\log (u)\right) +\delta _{\mathbb {R}_+^n}(z)+\beta _1\Vert u-(Af+c\mathbf {e})\Vert ^2 \nonumber \\&+\,\sum _{i=1}^n\Vert w_i\Vert +\beta _2 \sum _{i=1}^n\Vert D_if-w_i\Vert ^2 + \beta _3\Vert z-f\Vert ^2, \end{aligned}$$
(1.4)

where \(\beta _1, \beta _2, \beta _3\) are positive penalty parameters, respectively. It is clear that when \(\beta _1,\beta _2,\beta _3\) are sufficiently large, the objective function in (1.4) is close to that in (1.3).

An alternating minimization algorithm is proposed to solve the model (1.4). Alternating minimization algorithms have been applied to the cases of recovering blurred images corrupted by impulse, Gaussian, and multiplicative noises successfully [19, 21, 22, 44, 46,47,48]. For more details about multiplicative noise removal, the interested readers are referred to the papers [2, 38, 40]. Since u, z, w are decoupled, we can minimize f and (u, z, w), alternately. When \(\beta _1,\beta _2,\beta _3\) are sufficiently large, the minimizer of (1.4) is close to that of (1.3). The main advantages of the proposed algorithm are that the resulting subproblems have closed-form solutions or can be solved by fast Fourier transforms [27, 28]. Moreover, based on the fixed point iteration [8, 30], we show that, for any fixed \(\beta _1,\beta _2,\beta _3\), the sequence generated by the alternating minimization algorithm converges to a solution of (1.4). Our numerical results show that the proposed algorithm is faster than PIDAL [15], PIDSplit+ [36], and the primal dual (PD) algorithm [45].

The remaining parts of this paper are organized as follows. In Sect. 2, we give some notation that will be used throughout this paper. The alternating minimization algorithm is presented in Sect. 3. We establish the convergence of the proposed algorithm in Sect. 4. In Sect. 5, some numerical experiments are presented to demonstrate the efficiency of our proposed algorithm. Finally, we give some concluding remarks in Sect. 6.

2 Preliminaries

In this section, we briefly introduce some notation that will be used throughout this paper. \(\mathbb {R}^n\) denotes the n-dimensional Euclidean space. \(\mathbb {R}_+^{n}\) denotes the nonnegative orthant of \(\mathbb {R}^n\), i.e., \(\mathbb {R}_+^{n}:=\{x=(x_1,\ldots ,x_n)^T\in \mathbb {R}^n|x_i\ge 0, i=1, \ldots , n\}\). \(\mathbb {R}_{++}^{n}\) denotes the positive orthant of \(\mathbb {R}^{n}\), i.e., \(\mathbb {R}_{++}^{n}:=\{x=(x_1,\ldots ,x_n)^T\in \mathbb {R}^n|x_i>0, i=1,\ldots ,n\}\). The set of all \(m\times n\) matrices with real entries is denoted by \(\mathbb {R}^{m\times n}\). For any matrix \(A\in \mathbb {R}^{m\times n}\), \(\Vert A\Vert \) denotes the spectral norm of A.

Let \(D^{(1)}\) and \(D^{(2)}\) be the first-order finite difference matrices in the horizontal and vertical directions, respectively. \(D_i\in \mathbb {R}^{2\times n}\) is a matrix formed by stacking the ith rows of \(D^{(1)}\) and \(D^{(2)}\). Let \(D:=(D_1^T,\ldots ,D_n^T)^T\). \(A\succeq B\) denotes that \(A-B\) is positive semidefinite. The identity matrix is denoted by I, whose dimension should be clear from the context. The relative interior of a set G is denoted by \(\text{ int }(G)\). The indicator function of a set G is defined as

$$\begin{aligned} \delta _G(x):= \left\{ \begin{array}{lll} 0, &{} \text{ if } \ x\in G,\\ +\infty , &{} \text{ otherwise }.\\ \end{array}\right. \end{aligned}$$

Next, we give the definition of a convex function [33, Definition 2.1].

Definition 2.1

  1. (a)

    A subset C of \(\mathbb {R}^n\) is convex if it includes for every pair of points the line segment that joins them, or in other words, if for every choice of \(x_0\in C\) and \(x_1\in C\) one has \([x_0,x_1]\in C\):

    $$\begin{aligned} (1-\tau )x_0+\tau x_1\in C \ \ for \ \ all \ \ \tau \in (0,1). \end{aligned}$$
  2. (b)

    A function \(\psi \) on a convex set C is convex relative to C if for every choice of \(x_0\in C\) and \(x_1\in C\) one has

    $$\begin{aligned} \psi ((1-\tau )x_0+\tau x_1)\le (1-\tau )\psi (x_0)+\tau \psi (x_1)\ \ for \ \ all \ \ \tau \in (0,1). \end{aligned}$$

The effective domain of a function \(\psi : \mathbb {R}^n\rightarrow \mathbb {R}\cup \{+\infty \}\) is defined as

$$\begin{aligned} \text{ dom }(\psi ):=\{x: \psi (x)<+\infty \}. \end{aligned}$$

We say that \(\psi \) is proper if it never equals \(-\infty \) and \(\text{ dom }(\psi )\ne \varnothing \). For any proper convex function \(\psi : \mathbb {R}^n\rightarrow \mathbb {R}\cup \{+\infty \}\) and any point \(x\in \text{ dom }(\psi )\), the subgradient of \(\psi \) at x is defined as

$$\begin{aligned} \partial \psi (x):=\{v: \psi (y)\ge \psi (x)+ \langle v, y-x \rangle , \forall y \}. \end{aligned}$$

Let \(\psi :\mathcal {X}\rightarrow \mathbb {R}\cup \{+\infty \}\) be a closed, proper, convex function, where \(\mathcal {X}\) is a real finite dimensional Euclidean space equipped with an inner product \(\langle \cdot ,\cdot \rangle \) and its induced norm \(\Vert \cdot \Vert \). The operator

$$\begin{aligned} \text{ Prox }_\psi : \mathcal {X}\rightarrow \mathcal {X}:x\mapsto \arg \min _{y\in \mathcal {X}} \Big \{\psi (y)+\frac{1}{2}\Vert x-y\Vert ^2\Big \} \end{aligned}$$

is called the proximal mapping of \(\psi \) [12].

Other notation will be defined in appropriate sections if necessary.

3 An Alternating Minimization Algorithm

In this section, we present an alternating minimization algorithm to solve (1.4). Alternating minimization algorithms have been applied to the cases of recovering blurred images corrupted by impulse, Gaussian, and multiplicative noises successfully [19, 21, 22, 44, 46,47,48]. The alternating minimization algorithm for solving (1.4) can be described in Algorithm 1.

figure a

Since the objective function in (3.1) is differentiable, \(f^{k+1}\) can be computed by solving the following equation:

$$\begin{aligned} \begin{aligned} (\beta _1A^TA+\beta _2D^TD +\beta _3 I)f^{k+1}= \beta _1A^T(u^k-c\mathbf {e}) +\beta _2D^Tw^k + \beta _3z^k, \end{aligned} \end{aligned}$$
(3.5)

where \(w^k:=((w_1^k)^T,\ldots ,(w_n^k)^T)^T\). Let \(M:=\beta _1A^TA+\beta _2D^TD +\beta _3 I\), then M is positive definite. Thus, we have

$$\begin{aligned} f^{k+1}=M^{-1}\left( \beta _1A^T(u^k-c\mathbf {e}) +\beta _2D^Tw^k + \beta _3z^k\right) . \end{aligned}$$
(3.6)

Remark 3.1

In image restoration problems, A is usually a blurring matrix and D is a difference matrix under period boundary conditions that can be diagonalized by fast Fourier transforms. The computational cost of the method is dominated by three fast discrete transforms for solving the linear system in (3.5) [27, 28]. The interested readers are refered to [27, 28] for a detailed discussion on how to handle blurring matrices with other boundary conditions.

Since A is a blurring matrix, the entries of A are nonnegative, and \(c\ge 0\). Notice that, for any \(u^0>0\), we have \(u^k>0\). Therefore, the closed-form solution for (3.2) is given by

$$\begin{aligned} \begin{aligned} u^{k+1}=\frac{Af^{k+1}+c\mathbf {e}}{2}-\frac{\alpha \mathbf {e}}{4\beta _1} +\frac{\sqrt{(\alpha \mathbf {e}-2\beta _1({Af^{k+1}+c\mathbf {e}}))^2+8\alpha \beta _1 g}}{4\beta _1}. \end{aligned} \end{aligned}$$
(3.7)

Here, the root square of a vector means componentwise.

As for the subproblem about z in (3.3), we have

$$\begin{aligned} z^{k+1}=\mathcal {P}_{\mathbb {R}_+^n}(f^{k+1}), \end{aligned}$$

where \(\mathcal {P}\) is the projection onto \(\mathbb {R}_+^n\), i.e.,

$$\begin{aligned} (\mathcal {P}_{\mathbb {R}_+^n}(f))_i:= \left\{ \begin{array}{lll} f_i, &{} \text{ if } \ f_i\ge 0,\\ 0, &{} \text{ otherwise }.\\ \end{array}\right. \end{aligned}$$

As for the subproblem about \(w_i\) in (3.4), by the well-known two-dimensional shrinkage [3], \(w_i^{k+1}\) is given by

$$\begin{aligned} w_i^{k+1}=\max \left\{ \Vert D_if^{k+1}\Vert -\frac{1}{2\beta _2},0\right\} \frac{D_if^{k+1}}{\Vert D_if^{k+1}\Vert }, \ i=1,\ldots ,n, \end{aligned}$$
(3.8)

where \(0\cdot (0/0)=0\) is assumed.

Remark 3.2

Algorithm 1 could be applied to both the isotropic and anisotropic TV. For simplicity, we will only discuss the isotropic case in detail since it is similar to deal with the anisotropic case.

Remark 3.3

Compared with PIDAL [15], the subproblems of the alternating minimization algorithm can be solved exactly in each iteration.

4 Convergence Analysis

In this section, we establish the convergence of Algorithm 1. The following results in [8, 30] are utilized to show that the iteration sequence \(\{(f^k,u^k,z^k,w^k)\}\) generated by Algorithm 1 converges to a minimizer \((f^*,u^*,z^*,w^*)\) of \(\mathcal {Q}\).

Theorem 4.1

Let \(\mathcal {X}\) be a Hilbert space, and let \(\mathcal {T}\) be a nonexpansive self-mapping of \(\mathcal {X}\) such that T is asymptotically regular, i.e., for any x in \(\mathcal {X}\), \(\Vert \mathcal {T}^{n+1}x-\mathcal {T}^nx\Vert \) tends to 0 as n tends to \(+\infty \). Assume that \(\mathcal {T}\) has at least one fixed point. Then, for any x in \(\mathcal {X}\), a weak limit of a weakly convergent subsequence of the sequence of successive approximations \(\{\mathcal {T}^nx\}\) is a fixed point of \(\mathcal {T}\).

Although Theorem 4.1 shows the general case of the fixed point iteration in Hilbert spaces, we only use the finite dimension case for the sequence generated by Algorithm 1. Thus the weak and strong convergence coincide for Algorithm 1, i.e., the limit point of \(\{\mathcal {T}^nx\}\) is a fixed point of \(\mathcal {T}\). For the finite dimensional case about this theorem, a simplified proof can be found in [10, Theorem 5]. When \(\mathcal {X}\) is \(\mathbb {R}^n\), the sequence of successive approximations can converge to a fixed point. Therefore, we only need to prove that the operator \(\mathcal {T}\) about the iteration sequence is nonexpansive, asymptotically regular, and has a fixed point.

For the proximal operator of a function, we have the following proposition [12, Lemma 2.4].

Proposition 4.1

Let \(\phi :\mathcal {X}\rightarrow \mathbb {R}\cup \{+\infty \}\) be a closed, proper and convex function. Then, for any \(x,y\in \mathcal {X}\),

$$\begin{aligned} \Vert Prox _\phi (x)-Prox _\phi (y)\Vert ^2\le \left\langle Prox _\phi (x)-Prox _\phi (y), x-y \right\rangle . \end{aligned}$$

In the following, we define the nonexpansive operator [6], which is important for the analysis of the convergence.

Definition 4.1

An operator \(\mathcal {T}\) is called nonexpansive in \(\mathcal {X}\) if for any \(x_1,x_2\in \mathcal {X}\), we have

$$\begin{aligned} \Vert \mathcal {T}(x_1)-\mathcal {T}(x_2)\Vert \le \Vert x_1-x_2\Vert . \end{aligned}$$

By Proposition 4.1, we obtain that \(\text{ Prox }_\phi \) is nonexpansive, i.e.,

$$\begin{aligned} \Vert \text{ Prox }_\phi (x)-\text{ Prox }_\phi (y)\Vert \le \Vert x-y\Vert , \ \forall x,y\in \mathcal {X}. \end{aligned}$$

Actually, the proximal operator is a special kind of an averaged operator, which is nonexpansive [10, Lemma 3]. Next, we construct the iteration sequence of Algorithm 1. Let

$$\begin{aligned} H:=\begin{pmatrix} \sqrt{\beta _1}A \\ \sqrt{\beta _3}I \\ \sqrt{\beta _2}D \end{pmatrix} \ \text{ and } \ \ v:=\begin{pmatrix} u \\ z \\ w \end{pmatrix}, \end{aligned}$$

then \(M=H^TH\) by the definition of M. Thus, (3.5) is equivalent to

$$\begin{aligned} \begin{aligned} Mf^{k+1}&=\beta _1A^T(u^k-c\mathbf {e}) +\beta _2D^Tw^k + \beta _3z^k\\&=(BH)^Tv^k-\beta _1cA^T\mathbf {e}, \end{aligned} \end{aligned}$$

where

$$\begin{aligned} B:=\begin{pmatrix} \sqrt{\beta _1}I &{} 0 &{} 0 \\ 0 &{} \sqrt{\beta _3}I &{} 0 \\ 0 &{} 0 &{} \sqrt{\beta _2}I \end{pmatrix}. \end{aligned}$$

Since M is positive definite, we obtain

$$\begin{aligned} f^{k+1}=M^{-1}((BH)^Tv^k-\beta _1cA^T\mathbf {e}):=\mathcal {T}_f(v^k). \end{aligned}$$
(4.1)

Let \(\varphi (u):=\mathbf {e}^Tu-g^T\log (u)\). Since \(u>0\) and \(Af+c\mathbf {e}>0\), by (3.2), we get

$$\begin{aligned} u^{k+1}=\text{ Prox }_{\frac{\alpha }{2\beta _1}\varphi }(Af^{k+1}+c\mathbf {e}):=\mathcal {T}_1(f^{k+1})=\mathcal {T}_1(\mathcal {T}_f(v^k)). \end{aligned}$$
(4.2)

Moreover, by (3.3), we have

$$\begin{aligned} z^{k+1}=\mathcal {P}_{\mathbb {R}_+^n}(f^{k+1}):=\mathcal {T}_2(f^{k+1})=\mathcal {T}_2(\mathcal {T}_f(v^k)). \end{aligned}$$
(4.3)

Note that, for \(w_i\), the minimizer is the two-dimensional shrinkage operator [3]. Let \(g(x)=\Vert x\Vert \), by (3.8), we obtain that

$$\begin{aligned} \begin{aligned} w^{k+1} :=\begin{pmatrix} w_1^{k+1} \\ \vdots \\ w_n^{k+1} \end{pmatrix}= \begin{pmatrix} \text{ Prox }_{\frac{1}{2\beta _2}g}(D_1f^{k+1}) \\ \vdots \\ \text{ Prox }_{\frac{1}{2\beta _2}g}(D_nf^{k+1}) \end{pmatrix}:=\mathcal {T}_3(f^{k+1})=\mathcal {T}_3(\mathcal {T}_1(v^k)). \end{aligned} \end{aligned}$$
(4.4)

Thus, combining (4.2), (4.3), and (4.4), we get

$$\begin{aligned} v^{k+1}=\begin{pmatrix} \mathcal {T}_1(\mathcal {T}_f(v^k)) \\ \mathcal {T}_2(\mathcal {T}_f(v^k)) \\ \mathcal {T}_3(\mathcal {T}_f(v^k)) \end{pmatrix}. \end{aligned}$$

Let

$$\begin{aligned} \mathcal {T}:=\begin{pmatrix} \mathcal {T}_1(\mathcal {T}_f) \\ \mathcal {T}_2(\mathcal {T}_f) \\ \mathcal {T}_3(\mathcal {T}_f) \end{pmatrix}, \end{aligned}$$
(4.5)

we have \(v^{k+1}=\mathcal {T}(v^k)\), which is the iteration of Algorithm 1. In the following, we show that \(\mathcal {T}\) is nonexpansive.

Lemma 4.1

The operator \(\mathcal {T}\) in (4.5) is nonexpansive.

Proof

For any \(v_1,v_2\), by the definition of \(\mathcal {T}\), we have

$$\begin{aligned} \ \Vert \mathcal {T}(v_1)-\mathcal {T}(v_2)\Vert ^2= & {} \left\| \begin{pmatrix} \mathcal {T}_1(\mathcal {T}_f(v_1))-\mathcal {T}_1(\mathcal {T}_f(v_2)) \\ \mathcal {T}_2(\mathcal {T}_f(v_1))-\mathcal {T}_2(\mathcal {T}_f(v_2)) \\ \mathcal {T}_3(\mathcal {T}_f(v_1))-\mathcal {T}_3(\mathcal {T}_f(v_2)) \end{pmatrix}\right\| ^2 \nonumber \\= & {} \Vert \mathcal {T}_1(\mathcal {T}_f(v_1))-\mathcal {T}_1(\mathcal {T}_f(v_2))\Vert ^2 +\Vert \mathcal {T}_2(\mathcal {T}_f(v_1))-\mathcal {T}_2(\mathcal {T}_f(v_2))\Vert ^2 \nonumber \\&+\, \Vert \mathcal {T}_3(\mathcal {T}_f(v_1))-\mathcal {T}_3(\mathcal {T}_f(v_2))\Vert ^2. \end{aligned}$$
(4.6)

Let \(f_1:=\mathcal {T}_f(v_1)\) and \(f_2:=\mathcal {T}_f(v_2)\), then, by the definition of \(\mathcal {T}_f\), we obtain that

$$\begin{aligned} f_1-f_2=\mathcal {T}_f(v_1)-\mathcal {T}_f(v_2)=M^{-1}(BH)^T(v_1-v_2). \end{aligned}$$
(4.7)

Thus, we have

$$\begin{aligned} \begin{aligned}&\ \Vert \mathcal {T}_1(\mathcal {T}_f(v_1))-\mathcal {T}_1(\mathcal {T}_f(v_2))\Vert \\&\quad =\ \Vert \mathcal {T}_1(f_1)-\mathcal {T}_1(f_2)\Vert \\&\quad =\ \Big \Vert \text{ Prox }_{\frac{\alpha }{2\beta _1}\varphi } (Af_1+c\mathbf {e})-\text{ Prox }_{\frac{\alpha }{2\beta _1}\varphi }(Af_2+c\mathbf {e})\Big \Vert \\&\quad \le \ \Vert A(f_1-f_2)\Vert =\Vert AM^{-1}(BH)^T(v_1-v_2)\Vert , \end{aligned} \end{aligned}$$
(4.8)

where the inequality follows from Proposition 4.1 and the last equality follows from (4.7). For the operator \(\mathcal {T}_2(\mathcal {T}_f)\), we get

$$\begin{aligned} \begin{aligned}&\ \Vert \mathcal {T}_2(\mathcal {T}_f(v_1))-\mathcal {T}_2(\mathcal {T}_f(v_2))\Vert \\&\quad =\ \Vert \mathcal {T}_2(f_1)-\mathcal {T}_2(f_2)\Vert \\&\quad \le \ \Vert f_1-f_2\Vert =\Vert M^{-1}(BH)^T(v_1-v_2)\Vert , \end{aligned} \end{aligned}$$
(4.9)

where the inequality holds since \(\mathcal {T}_2\) is nonexpansive. For the operator \(\mathcal {T}_3(\mathcal {T}_f)\), we have

$$\begin{aligned} \begin{aligned}&\Vert \mathcal {T}_3(\mathcal {T}_f(v_1))-\mathcal {T}_3(\mathcal {T}_f(v_2))\Vert ^2\\&\quad =\ \Vert \mathcal {T}_3(f_1)-\mathcal {T}_3(f_2)\Vert ^2\\&\quad \le \sum _{i=1}^n\Vert D_i(f_1-f_2)\Vert ^2 \\&\quad =\ \Vert D(f_1-f_2)\Vert ^2=\Vert DM^{-1}(BH)^T(v_1-v_2)\Vert ^2, \end{aligned} \end{aligned}$$
(4.10)

where the inequality holds by Proposition 4.1. Therefore, combining (4.8), (4.9), (4.10) and (4.6), we obtain that

$$\begin{aligned} \begin{aligned}&\ \Vert \mathcal {T}(v_1)-\mathcal {T}(v_2)\Vert ^2\\&\quad \le \ \Vert AM^{-1}(BH)^T(v_1-v_2)\Vert ^2+\Vert M^{-1}(BH)^T(v_1-v_2)\Vert ^2 +\Vert DM^{-1}(BH)^T(v_1-v_2)\Vert ^2\\&\quad =\ \Biggl \Vert \begin{pmatrix} A \\ I \\ D \end{pmatrix}M^{-1}(BH)^T(v_1-v_2)\Biggl \Vert ^2 =\Vert B^{-1}HM^{-1}(BH)^T(v_1-v_2)\Vert ^2=\Vert v_1-v_2\Vert ^2, \end{aligned} \end{aligned}$$

where the last equality follows from the definition of M. This implies that \(\Vert \mathcal {T}(v_1)-\mathcal {T}(v_2)\Vert \le \Vert v_1-v_2\Vert \). Thus, \(\mathcal {T}\) is nonexpansive. \(\square \)

The following lemma shows that \(\mathcal {T}\) is asymptotically regular.

Lemma 4.2

Let \(v^k:=((u^k)^T,(z^k)^T,(w^k)^T)^T\) be generated by Algorithm 1, then \(\sum _{k=1}^{+\infty }\Vert v^k-v^{k-1}\Vert ^2\) converges and \(\mathcal {T}\) is asymptotically regular.

Proof

The proof follows the lines of the proof of Lemma 3.6 in [19]. For the sake of completeness, we give it here. We consider the Taylor expansion of \(\mathcal {Q}(f,u^k,z^k,w^k)\) at \(f^{k+1}\) and let \(f=f^k\). Since \(\mathcal {Q}(f,u^k,z^k,w^k)\) about f is a quadratic function, we have

$$\begin{aligned} \begin{aligned} \mathcal {Q}(f^k,u^k,z^k,w^k)=&\ \mathcal {Q}(f^{k+1},u^k,z^k,w^k)+(\nabla _f\mathcal {Q}(f^{k+1},u^k,z^k,w^k))^T(f^k-f^{k+1})\\&+ \frac{1}{2}(f^k-f^{k+1})^T\nabla _f^2\mathcal {Q}(f^{k+1},u^k,z^k,w^k)(f^k-f^{k+1}), \end{aligned} \end{aligned}$$
(4.11)

where \(\nabla _f\mathcal {Q}(f^{k+1},u^k,z^k,w^k)\) and \(\nabla _f^2\mathcal {Q}(f^{k+1},u^k,z^k,w^k)\) denote the gradient and Hessian matrix of \(\mathcal {Q}(f,u^k,z^k,w^k)\) at \(f^{k+1}\), respectively. Since \(f^{k+1}\) is a minimizer of \(\mathcal {Q}(f,u^k,z^k,w^k)\), we have

$$\begin{aligned} \nabla _f\mathcal {Q}(f^{k+1},u^k,z^k,w^k)=0. \end{aligned}$$
(4.12)

Moreover,

$$\begin{aligned} \begin{aligned} \nabla _f^2\mathcal {Q}(f^{k+1},u^k,z^k,w^k) =2\beta _1A^TA+2\beta _2D^TD+2\beta _3I\succeq 2\beta _3I. \end{aligned} \end{aligned}$$
(4.13)

Thus, by substituting (4.12) and (4.13) into (4.11), we get

$$\begin{aligned} \mathcal {Q}(f^k,u^k,z^k,w^k) - \mathcal {Q}(f^{k+1},u^k,z^k,w^k) \ge \beta _3\Vert f^k-f^{k+1}\Vert ^2. \end{aligned}$$

Since \(\mathcal {Q}(f^{k+1},u^{k+1},z^{k+1},w^{k+1})\le \mathcal {Q}(f^{k+1},u^k,z^k,w^k)\), we obtain

$$\begin{aligned} \begin{aligned} \mathcal {Q}(f^k,u^k,z^k,w^k) - \mathcal {Q}(f^{k+1},u^{k+1},z^{k+1},w^{k+1}) \ge \beta _3\Vert f^k-f^{k+1}\Vert ^2. \end{aligned} \end{aligned}$$
(4.14)

Combining (4.2), (4.3) and (4.4), we have

$$\begin{aligned} \begin{aligned}&\ \Vert v^k-v^{k+1}\Vert ^2\\&\quad =\ \Vert \mathcal {T}_1(f^k)-\mathcal {T}_1(f^{k+1})\Vert ^2 +\Vert \mathcal {T}_2(f^k)-\mathcal {T}_2(f^{k+1})\Vert ^2+\Vert \mathcal {T}_3(f^k)-\mathcal {T}_3(f^{k+1})\Vert ^2 \\&\quad \le \ \Vert A(f^k-f^{k+1})\Vert ^2 + \Vert f^k-f^{k+1}\Vert ^2 + \Vert D(f^k-f^{k+1})\Vert ^2 \\&\quad \le \ (\Vert A\Vert ^2+\Vert D\Vert ^2+1)\Vert f^k-f^{k+1}\Vert ^2, \end{aligned} \end{aligned}$$

where the first inequality holds by Proposition 4.1. From [11], we know that \(\Vert D\Vert ^2\le 8\) and from [25], we have \(\Vert A\Vert \le 1\). Thus,

$$\begin{aligned} \Vert v^k-v^{k+1}\Vert ^2\le 10\Vert f^{k}-f^{k+1}\Vert ^2. \end{aligned}$$
(4.15)

Substituting (4.15) into (4.14), we have

$$\begin{aligned} \begin{aligned} \frac{\beta _3}{10}\Vert v^{k}-v^{k+1}\Vert ^2 \le \mathcal {Q}(f^k,u^k,z^k,w^k) - \mathcal {Q}(f^{k+1},u^{k+1},z^{k+1},w^{k+1}). \end{aligned} \end{aligned}$$

Since \(\mathcal {Q}\) is bounded below, it follows that \(\sum _{k=0}^{+\infty }\Vert v^{k}-v^{k+1}\Vert ^2\) converges. Moreover,

$$\begin{aligned} \lim _{k\rightarrow +\infty }\Vert v^{k}-v^{k+1}\Vert =0. \end{aligned}$$

Note that \(v^{k}=\mathcal {T}(v^{k-1})=\mathcal {T}^2(v^{k-2})=\cdots =\mathcal {T}^{k-1}(v^{1})=\mathcal {T}^k(v^0),\) we obtain that

$$\begin{aligned} \lim _{k\rightarrow +\infty }\Vert \mathcal {T}^k(v^0)-\mathcal {T}^{k+1}(v^0)\Vert =0. \end{aligned}$$

This implies that \(\mathcal {T}\) is asymptotically regular. Thus, we complete the proof. \(\square \)

By [45], we know that \(\mathbf {e}^Tu-g^T\log (u)\) is proper, which implies that \(\mathcal {Q}(f,u,z,w)\) is proper. Notice that \(\mathcal {Q}(f,u,z,w): \mathbb {R}^n\times \mathbb {R}^n_{++}\times \mathbb {R}^n\times \mathbb {R}^{2n}\rightarrow \mathbb {R}\cup \{+\infty \}\) is continuous, we obtain that \(\mathcal {Q}(f,u,z,w)\) is closed [33, Thoerem 1.6]. In order to show the existence of minimizers of \(\mathcal {Q}(f,u,z,w)\), by [33, Theorem 1.9], we only need to prove that \(\mathcal {Q}(f,u,z,w)\) is coercive, i.e., \(\mathcal {Q}(f,u,z,w)\) tends to infinity as \(\Vert (f^T,u^T,z^T,w^T)^T\Vert \) tends to infinity.

Lemma 4.3

If \(Ker (A)\cap Ker (D)=\{0\}\), where \(Ker (\cdot )\) denotes the null space of a matrix, then \(\mathcal {Q}(u,z,w,f)\) is coercive.

Proof

When

$$\begin{aligned} \left\| \begin{pmatrix} f \\ u \\ z \\ w \end{pmatrix}\right\| \rightarrow +\infty , \end{aligned}$$

we have \(\Vert u\Vert \rightarrow +\infty \), or \(\Vert w\Vert \rightarrow +\infty \), or

$$\begin{aligned} \left\| \begin{pmatrix} f \\ z \end{pmatrix}\right\| \rightarrow +\infty . \end{aligned}$$

Thus, we proceed the discussions by three cases.

Case 1. Suppose that \(\Vert u\Vert \rightarrow +\infty \). We note that \(u-\log (u)\) tends to infinity when u tends to infinity. Thus, we have \(\mathcal {Q}(f,u,z,w)\) tends to infinity.

Case 2. Suppose that \(\Vert w\Vert \rightarrow +\infty \). Then, \(\sum _{i=1}^n\Vert w_i\Vert \) tends to infinity. Since \(u-\log (u)\) is bounded below, we obtain that \(\mathcal {Q}(f,u,z,w)\) tends to infinity.

Case 3. Suppose that

$$\begin{aligned} \left\| \begin{pmatrix} f \\ z \end{pmatrix}\right\| \rightarrow +\infty . \end{aligned}$$

We assume that \(\Vert u\Vert , \Vert w\Vert \) are bounded, otherwise the result holds by Cases 1 and 2. If \(\Vert f\Vert \) tends to infinity and \(\Vert z\Vert \) is bounded, we have \(\Vert z-f\Vert ^2\) tends to infinity. Thus, \(\mathcal {Q}(f,u,z,w)\) tends to infinity. If \(\Vert z\Vert \) tends to infinity and \(\Vert f\Vert \) is bounded, we have \(\Vert z-f\Vert ^2\) tends to infinity. Then, \(\mathcal {Q}(f,u,z,w)\) tends to infinity. If \(\Vert f\Vert \) tends to infinity, \(\Vert z\Vert \) tends to infinity, since \(\text{ Ker }(A)\cap \text{ Ker }(D)=\{0\}\), we have \(\Vert Af\Vert \) tends to infinity or \(\Vert Df\Vert \) tends to infinity as \(\Vert f\Vert \) tends to infinity. Since \(\Vert u\Vert , \Vert w\Vert \) are bounded, we obtain that \(\mathcal {Q}(f,u,z,w)\) tends to infinity. Together with Cases 1 and 2, we complete the proof. \(\square \)

Remark 4.1

The condition \(\text {Ker}(A)\cap \text {Ker}(D)=\{0\}\) in Lemma 4.3 is easy to satisfy. If A is a blurring matrix, then their rows sum up to one, while the differences matrix D (under appropriate boundary conditions) has kernel consisting of constant vectors so that their joint kernel must be the zero vector.

We now show that the set of fixed points of \(\mathcal {T}\) is nonempty.

Lemma 4.4

Suppose that \(Ker (A)\cap Ker (D)=\{0\}\). Then the set of fixed points of \(\mathcal {T}\) is nonempty.

Proof

Since \(\mathcal {Q}\) is coercive, by [33, Theorem 1.9], we obtain that the minimizer \((f^*,u^*,z^*,w^*)\) of \(\mathcal {Q}\) exists. Then, by [33, Thoerem 6.12], we get

$$\begin{aligned} \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}\in \begin{pmatrix} \partial _f\mathcal {Q}(f^*,u^*,z^*,w^*) \\ \partial _u\mathcal {Q}(f^*,u^*,z^*,w^*) + N_{\mathbb {R}_{++}^n}(u^*) \\ \partial _z\mathcal {Q}(f^*,u^*,z^*,w^*) \\ \partial _w\mathcal {Q}(f^*,u^*,z^*,w^*) \end{pmatrix}, \end{aligned}$$

where \( N_{\mathbb {R}_{++}^n}(u^*)\) denotes the normal cone of \(\mathbb {R}_{++}^n\) at \(u^*\). Since \(u^*>0\), i.e., \(u^*\in \text{ int }(\mathbb {R}_{++}^n)\), by [33, Proposition 6.5], we have \(N_{\mathbb {R}_{++}^n}(u^*)=\{0\}\). This implies that

$$\begin{aligned} \left\{ \begin{array}{lll} f^*=\mathcal {T}_f(v^*)=\arg \min _f\{\mathcal {Q}(\cdot ,u^*,z^*,w^*)\}, \\ u^*=\mathcal {T}_1(f^*)=\arg \min _u\{\mathcal {Q}(f^*,\cdot ,z^*,w^*)\}, \\ z^*=\mathcal {T}_2(f^*)=\arg \min _z\{\mathcal {Q}(f^*,u^*,\cdot ,w^*)\}, \\ w^*=\mathcal {T}_3(f^*)=\arg \min _w\{\mathcal {Q}(f^*,u^*,z^*,\cdot )\}, \end{array}\right. \end{aligned}$$

where \(v^*:=((u^*)^T,(z^*)^T,(w^*)^T)^T\). Thus, by the definition of \(\mathcal {T}\), we obtain that \(v^*=\mathcal {T}(v^*)\), and \(v^*\) is a fixed point of \(\mathcal {T}\). \(\square \)

Combining Lemmas 4.1, 4.2, 4.4 and Theorem 4.1, we can get the following convergence result.

Theorem 4.2

Suppose that \(Ker (A)\cap Ker (D)=\{0\}\). For any initial point \(u^0>0,z^0,w^0\), the sequence \(\{(f^k,u^k,z^k,w^k)\}\) generated by Algorithm 1 converges to a minimizer \((f^*,u^*,z^*,w^*)\) of \(\mathcal {Q}\).

Remark 4.2

Compared with the alternating minimization algorithms in [19, 21, 22], we consider some constraints in Algorithm 1.

5 Experimental Results

In this section, we present numerical results to show the efficiency of the proposed algorithm for the images corrupted by blurs and Poisson noise. The testing images include Cameraman (\(256\times 256\)), House (\(256\times 256\)), Barbara (\(512\times 512\)), and Livingroom (\(512\times 512\)), which are shown in Fig. 1. In our numerical examples, we consider two blurring functions from MATLAB: Average blur and Gaussian blur. For Average blur, the testing kernel is \(9\times 9\), and for Gaussian blur, the testing kernel is \(9\times 9\) (standard deviation \(= 3\)). All the experiments are performed under Windows 7 and MATLAB R2015b running on a laptop (AMD A10-5750M, @ 2.50GHz, 8G RAM).

Fig. 1
figure 1

Original images. From left to right: Cameraman, House, Barbara, Livingroom

Full size image
Table 1 SNR(dB) values and CPU time(s) of different algorithms for the Cameraman, House, Barbara, and Livingroom images corrupted by Average blur and Poisson noise
Full size table

Since Poisson noise is data-dependent, the noise levels of the observed images depend on the pixel intensity M. To test different noise levels, we consider different peak intensities of the images. The noisy and blurry images in our test are simulated as follows. The original image f is first scaled with the peak intensities. Then the scaled image is convolved with the blur kernel A and the background is added. Finally, the Poisson noise is added in Matlab using the function poissrnd.

Fig. 2
figure 2

Recovered images (with SNR(dB) and CPU time(s)) of different algorithms on the Cameraman, House, Barbara and Livingroom images corrupted by Average blur and Poisson noise with peak intensity \(M=80\) and \(c=10\). First row: Noisy and blurry images. Second row: Images recovered by PIDAL. Third row: Images recovered by PIDSplit+. Fourth row: Images recovered by PD. Fifth row: Images recovered by Algorithm 1

Full size image
Fig. 3
figure 3

Difference images of House image among different algorithms in Fig. 2. a Difference image between PIDAL and PIDSplit+. b Difference image between PD and PIDAL. c Difference image between PD and PIDSplit+. d Difference image between Algorithm 1 and PIDAL. e Difference image between Algorithm 1 and PIDSplit+. f Difference image between Algorithm 1 and PD

Full size image

To evaluate the performance of different algorithms, the signal-to-noise ratio (SNR) is used to measure the quality of the restored image:

$$\begin{aligned} \text{ SNR }=10\log _{10}\left( \frac{\Vert f\Vert ^2}{\Vert f-\hat{f}\Vert ^2}\right) , \end{aligned}$$

where f is the original image and \(\hat{f}\) is the restored image. We terminate Algorithm 1 by checking whether the relative error of the successive iterates satisfies

$$\begin{aligned} \frac{\Vert f^{k+1}-f^k\Vert }{\Vert f^k\Vert }\le \text{ tol }, \end{aligned}$$
(5.1)

where \(\text{ tol }\) is set to be \(10^{-3}\) in our experiments. The maximum iteration number of Algorithm 1 is set to be 500. For the penalty parameters \(\beta _1, \beta _2, \beta _3\) in Algorithm 1, the initial values of \(\beta _1, \beta _2, \beta _3\) are set to 0.4, 0.4 and 0.001, respectively, and then \(\beta _1, \beta _2, \beta _3\) are increased by \(\tau \beta _1, \tau \beta _2, \tau \beta _3\) every twenty iterations, where \(\tau =1.01\) in our experiments. The regularization parameter \(\alpha \) will be selected from \(\{1,10, 20, 50, 100, 150, 200, 250, 300\}\) for the fast convergence and satisfactory accuracy. We remark that \(\beta _1,\beta _2,\beta _3\) should make the minimizer of (1.4) close to the minimizer of (1.3) in the quadratic penalty (1.4). Unfortunately, large \(\beta _i,i=1,\ldots ,3\), usually cause numerical difficulties, since (1.4) becomes very ill-conditioned. Hence, it is more practical to minimize (1.4) with moderate values of \(\beta _i,i=1,\ldots ,3\).

5.1 Comparisons to the Existing Methods

In this subsection, we compare our algorithm with PIDAL [15], PIDSplit+ [36], and PD [45]. The stopping criterion of PIDAL, PIDSplit+, and PD is the same as (5.1) and the maximum iteration number of the three algorithms is set to be 1000. For the PIDAL algorithm [15], the Chambolle’s projection algorithm [11] is used to solve the TV denoising subproblem. The number of iterations of Chambolle’s algorithm is set to 20 and the corresponding step size is set to 0.248, which were suggested in [15]. We use the final values of an inner iteration loop as the initial values for the next loop. Moreover, as suggested in [15, 36], we set \(\gamma =50/\alpha \) for the PIDAL and PIDSplit+ algorithms, where \(\alpha \) is the regularization parameter and \(\gamma \) is the penalty parameter. In the PIDAL, PIDSplit+, and PD algorithms, the parameter \(\alpha \) is also tested from \(\{1, 10, 20, 50, 100, 150, 200, 250, 300\}\) to get the best recovery performance in terms of SNR values and CPU time.

In Table 1, we show the SNR values and CPU time (in seconds) for the Cameraman, House, Barbara, and Livingroom images corrupted by Average blur and Poisson noise with different peak intensities M and c, respectively. We can see that our proposed algorithm outperforms PIDAL, PIDSplit+, and PD for these images in terms of CPU time, and the SNR values of the proposed algorithm are almost the same as those of the other algorithms. Therefore, under almost the same accuracies, our proposed algorithm is much faster than the other three algorithms. Moreover, the PIDAL and PIDSplit+ algorithms need more CPU time than PD for these images.

Table 2 SNR(dB) values and CPU time(s) of different algorithms for the Cameraman, House, Barbara, and Livingroom images corrupted by Gaussian blur and Poisson noise
Full size table
Fig. 4
figure 4

Recovered images (with SNR(dB) and CPU time(s)) of different algorithms on the Cameraman, House, Barbara, and Livingroom images corrupted by Gaussian blur and Poisson noise with peak intensity \(M=40\) and \(c=1\). First row: Noisy and blurry images. Second row: Images recovered by PIDAL. Third row: Images recovered by PIDSplit+. Fourth row: Images recovered by PD. Fifth row: Images recovered by Algorithm 1

Full size image
Fig. 5
figure 5

SNR(dB) values versus CPU time(s) for the images corrupted by Gaussian blur and Poisson noise with \(M=20, c=1\). a Cameraman. b House. c Barbara. d Livingroom

Full size image

The visual comparison of the Cameraman, House, Barbara, and Livingroom images corrupted by Average blur and Poisson noise with peak intensity \(M=80\) and \(c=10\) is shown in Fig. 2. We can observe that these images restored by Algorithm 1 are almost the same as those restored by the PIDAL, PIDSplit+, and PD algorithms. However, the CPU time of the proposed algorithm is much less than those of the other three algorithms. Moreover, one can hardly see the differences among these images restored by the four algorithms. In Fig. 3, we show the difference images of the House image of Fig. 2 for different algorithms. It is shown that there are still some differences in these images restored by PIDAL, PIDSplit+, PD, and Algorithm 1.

Table 2 shows the SNR values and CPU time for the Cameraman, House, Barbara, and Livingroom images corrupted by Gaussian blur and Poisson noise with different peak intensities M and c, respectively. It can be seen that the CPU time of the proposed algorithm is less than the other three algorithms. The accuracies of the proposed algorithm are almost the same as those of PIDAL, PIDSplit+, and PD in terms of SNR values. Moreover, the PD algorithm performs better than PIDAL and PIDSplit+ in terms of CPU time.

Figure 4 shows the comparison on the Cameraman, House, Barbara, and Livingroom images corrupted by Gaussian blur and Poisson noise with peak intensity \(M=40\) and \(c=1\). We can observe that the SNR values of the restored images by the four algorithms are almost the same, and the computational time required by the proposed algorithm is much less than those required by PIDAL, PIDSplit+, and PD.

In Fig. 5, we plot the SNR values versus CPU time for the Cameraman, House, Barbara, and Livingroom images corrupted by Gaussian blur and Poisson noise with \(M=20, c=1\). We can observe that the PIDAL and PIDSplit+ algorithms are fast at the initial iterations. But the convergence speed of the two algorithms is slow after reaching a low accuracy. Algorithm 1 needs less CPU time than PIDAL, PIDSplit+, and PD for reaching high accurate solutions. Moreover, the PD algorithm is slower than the proposed algorithm for all the stages. It needs more iterations to reach the same accuracy than the proposed algorithm. The proposed algorithm is fast in all the iterations for low and high accurate solutions. Thus, Algorithm 1 outperforms PIDAL, PIDSplit+ in terms of CPU time.

6 Concluding Remarks

In this paper, we have proposed an alternating minimization algorithm for the restoration of blurred images corrupted by Poisson noise, which minimizes the KL divergence plus TV regularization regularization model with nonnegative constraint. By introducing new variables, the objective function is separable. The approximation model (1.4) is derived from the classical penalty method. Then, we can minimize each variables, alternatingly. Furthermore, based on the fixed point theory, we establish the convergence of the proposed algorithm under very mild assumptions. Our preliminary numerical experiments show that the proposed algorithm is much faster than PIDAL [15], PIDSplit+ [36] and PD [45].