Acceleration of RED via Vector Extrapolation

I Introduction

Inverse problems in imaging address the reconstruction of clean images from their corrupted versions. The corruption can be a blur, loss of samples, downscale or a more complicated operator (e.g., CT and MRI), accompanied by a noise contamination. Roughly speaking, inverse problems are characterized by two main parts: the first is called the forward model, which formulates the relation between the noisy measurement and the desired signal, and the second is the prior, describing the log-probability of the destination signal.

In recent years, we have witnessed a massive advancement in a basic inverse problem referred to as image denoising . Indeed, recent work goes as far as speculating that the performance obtained by leading image denoising algorithms is getting very close to the possible ceiling . This motivated researchers to seek ways to exploit this progress in order to address general inverse problems. Successful attempts, as in , suggested an exhaustive manual adaptation of existing denoising algorithms, or the priors used in them, treating specific alternative missions. This line of work has a clear limitation, as it does not offer a flexible and general scheme for incorporating various image denoising achievements for tackling other advanced image processing tasks. This led to the following natural question: is it possible to suggest a general framework that utilizes the abundance of high-performance image denoising algorithms for addressing general inverse problems? Venkatakrishnan et al. gave a positive answer to this question, proposing a framework called Plug-and-Play Priors ($P^{3}$) method . Formulating the inverse problem as an optimization task and handling it via the Alternating Direction Method of Multipliers (ADMM) scheme , $P^{3}$ shows that the whole problem is decomposed into a sequence of image denoising sub-problems, coupled with simpler computational steps. The $P^{3}$ scheme provides a constructive answer to the desire to use denoisers within inverse problems, but it suffers from several key disadvantages: $P^{3}$ does not define a clear objective function, since the regularization used is implicit; Tuning the parameters in $P^{3}$ is extremely delicate; and since $P^{3}$ is tightly coupled with the ADMM, it has no flexibility with respect to the numerical scheme.

A novel framework named REgularization by Denoising (RED) proposes an appealing alternative while overcoming all these flaws. The core idea in RED is the use of the given denoiser within an expression of regularization that generalizes a Laplacian smoothness term. The work in carefully shows that the gradient of this regularization is in fact the denoising residual. This, in turn, leads to several iterative algorithms, all guaranteed to converge to the global minimum of the inverse problem’s penalty function, while using a denoising step in each iteration.

The idea of using a state-of-the-art denoising algorithm for constructing an advanced prior for general inverse problems is very appealing.Firstly, it enables utilizing the vast progress in image denoising for solving challenging inverse problems as explained above. Secondly, RED enables utilizing the denoiser as a black-box. However, a fundamental problem still exists due to the high complexity of typical denoising algorithms, which are required to be activated many times in such a recovery process. Indeed, the evidence from the numerical experiments posed in clearly exposes this problem, in all the three methods proposed, namely the steepest descent, the fixed-point (FP) strategy and the ADMM scheme. Note that the FP method is a parameter free and the most efficient among the three, and yet this approach too requires the activation of the denoising algorithms dozens of times for a completion of the recovery algorithm.

Our main contribution in this paper is to address these difficulties by applying vector extrapolation (VE) to accelerate the FP algorithm shown in . Our simulations illustrate the effectiveness of VE for this acceleration, saving more than $50\%$ of the overall computations involved compared with the native FP method.

The rest of this paper is organized as follows. We review RED and its FP method in Section II. Section III recalls the Vector Extrapolation acceleration idea. Several experiments on image deblurring and super-resolution, which follows the ones given in , show the effectiveness of VE, and these are brought in Section IV. We conclude our paper in Section V.

II REgularization by Denoising (RED)

This section reviews the framework of RED, which utilizes denoising algorithms as image priors . We also describe its original solver based on the Fixed Point (FP) method.

From an estimation point of view, the signal $\bm{x}$ is to be recovered from its measurements $\bm{y}$ using the posterior conditional probability $P(\bm{x}|\bm{y})$. Using maximum a posterior probability (MAP) and the Bayes’ rule, the estimation task is formulated as:

II-B RED and the Fixed-Point Method

Define $f(\bm{x})$ as an abstract and differentiable denoiser.This denoising function admits a noisy image $\bm{x}$, and removes additive Gaussian noise form it, assuming a prespecified noise energy. RED suggests applying the following form as the prior:

where $\mathcal{T}$ denotes the transpose operator. The term $\bm{x}^{\mathcal{T}}\left(\bm{x}-f(\bm{x})\right)$ is an image-adaptive Laplacian regularizer, which favors either a small residual $\bm{x}-f(\bm{x})$, or a small inner product between $\bm{x}$ and the residual . Plugged into Equation (2), this leads the following minimization task:

The prior $R(\bm{x})$ of RED is a convex function and easily differentiated if the following two conditions are met:

Local Homogeneity: For any scalar $c$ arbitrarily close to $1$, we have $f(c\bm{x})=cf(\bm{x})$.

Strong Passivity: The Jacobian $\nabla_{\bm{x}}f(\bm{x})$ is stable in the sense that its spectral radius is upper bounded by one, $\rho(\nabla_{\bm{x}}f(\bm{x}))\leq 1$.

Surprisingly, the gradient of $E(\bm{x})$ is given by

where $\bm{I}$ represents the identity matrix. This matrix inversion is calculated in the Fourier domain for block-circulant $\bm{H}$, or using iterative methods for the more general cases. The convergence of the FP method is guaranteed since

Although the FP method is more efficient than the steepest descent and the ADMM, it still needs hundreds of iterations, which means hundreds of denoising activations, to reach the desired minimum. This results in a high complexity algorithm which we aim to address in this work. In the next section, we introduce an accelerated technique called Vector Extrapolation (VE) to substantially reduce the amount of iterations in the FP method.

III Proposed Method via Vector Extrapolation

We begin this section by introducing the philosophy of VE in linear and nonlinear systems and then discuss three variants of VE We refer the interesting readers to and the references therein to explore further the VE technique., i.e., Minimal Polynomial Extrapolation (MPE), Reduced Rank Extrapolation (RRE) and Singular Value Decomposition Minimal Polynomial Extrapolation (SVD-MPE) . Efficient implementation of these three variants is also discussed. We end this section by embedding VE in the FP method for RED, offering an acceleration of this scheme. Finally, we discuss the convergence and stability properties of VE.

Consider a vector set $\{\bm{x}_{i}\in\Re^{N}\}$ generated via a linear process,

where $\bm{A}\in\Re^{N\times N}$, $\bm{b}\in\Re^{N}$ and $\bm{x}_{0}$ is the initial vector. If $\rho(\bm{A})<1$, a limit point $\bm{x}^{*}$ exists, being the FP of (8), $\bm{x}^{*}=\bm{A}\bm{x}^{*}+\bm{b}$. We turn to describe how VE works on such linear systems . Denote $\bm{u}_{i}=\bm{x}_{i+1}-\bm{x}_{i},~{}~{}i=0,1,\cdots,$ and define the defective vector $\bm{e}_{i}$ as

Subtracting $\bm{x}^{*}$ from both sides of (8) and utilizing the fact that $\bm{x}^{*}$ is the FP, we have $\bm{e}_{i+1}=\bm{A}\bm{e}_{i}$ resulting in

We define a new extrapolated vector $\bm{x}_{(m,\kappa)}$ as a weighted average of the form

where $\sum\limits_{i=0}^{\kappa}\gamma_{i}=1$. Substituting (9) in (11) and using (10) and $\sum_{i=0}^{\kappa}\gamma_{i}=1$, we have

Note that the optimal $\{\gamma_{i}\}$ and $\kappa$ should be chosen so as to force $\sum\limits_{i=0}^{\kappa}\gamma_{i}\bm{A}^{i}\bm{e}_{m}=0$. This way, we attain the FP through only one extrapolation step.

More broadly speaking, given a nonzero matrix $\bm{B}\in\Re^{N\times N}$ and an arbitrary nonzero vector $\bm{u}\in\Re^{N}$, we can find a unique polynomial $P(z)$ with smallest degree to yield $P(\bm{B})\bm{u}=\bm{0}$. Such a $P(z)$ is called the minimal polynomial of $\bm{B}$ with respect to the vector $\bm{u}$. Notice that the zeros of $P(z)$ are the eigenvalues of $\bm{B}$. Thus, assume that the minimal polynomial of $\bm{A}$ with respect to $\bm{e}_{m}$ can be represented as

resulting in $P(\bm{A})\bm{e}_{m}=\bm{0}$. So, we have

Multiplying both sides of (14) by $\bm{A}$ results in $\sum_{i=0}^{\kappa}c_{i}\bm{A}\bm{e}_{m+i}=\sum_{i=0}^{\kappa}c_{i}\bm{e}_{m+i+1}=\bm{0}$, and thus we receive

This suggests that $\{c_{i}\}$ could be determined by solving the linear equations posed in (16). Once obtaining $\{c_{i}\}$, $\{\gamma_{i}\}$ are calculated through $\gamma_{i}=\frac{c_{i}}{\sum_{j=0}^{\kappa}c_{j}}$. Note that $\sum_{j=0}^{\kappa}c_{j}\neq 0$ if $\bm{I}-\bm{A}$ is not singular yielding $\sum_{j=0}^{\kappa}c_{j}=P(1)\neq 0$. Assuming $\kappa$ is the degree of the minimal polynomial of $\bm{A}$ with respect to $\bm{e}_{m}$, we can find a set of $\{\gamma_{i}\}$ to satisfy $\sum_{i=0}^{\kappa}\gamma_{i}=1$ resulting in $\sum_{i=0}^{\kappa}\gamma_{i}\bm{x}_{m+i}=\bm{x}^{*}$. However, the degree of the minimal polynomial of $\bm{A}$ can be as large as $N$, which in our case is very high. Moreover, we also do not have a way to obtain this degree with an easy algorithm. Because of these two difficulties, some approximate methods are developed to extrapolate the next vector via the previous ones and we will discuss them in Subsection III-B.

Turning to the nonlinear case, denote $\bm{F}$ as the FP function to evaluate the next vector,

where $\bm{F}$ is an $N$-dimensional vector-valued function, $\bm{F}:\Re^{N}\rightarrow\Re^{N}$. We say $\bm{x}^{*}$ is a FP of $\bm{F}$ if $\bm{x}^{*}=\bm{F}(\bm{x}^{*})$. Expanding $\bm{F}(\bm{x})$ in its Taylor series yields

where $\bm{F}^{\prime}(\cdot)$ is the Jacobian matrix of $\bm{F}(\cdot)$. Recalling $\bm{F}(\bm{x}^{*})=\bm{x}^{*}$, we have

Assuming the sequence $\bm{x}_{0},\bm{x}_{1},\dots$ converges to $\bm{x}^{*}$ (if $\rho(\bm{F}^{\prime}(\bm{x}))<1$), it follows that $\bm{x}_{i}$ will be close enough to $\bm{x}^{*}$ for all large $i$, and hence

For large $i$, the vectors $\{\bm{x}_{i}\}$ behave as in the linear system of the form $(\bm{I}-\bm{A})\bm{x}=\bm{b}$ through

where $\bm{A}=\bm{F}^{\prime}(\bm{x}^{*})$, $\bm{b}=[\bm{I}-\bm{F}^{\prime}(\bm{x}^{*})]\bm{x}^{*}$. This implies that the nonlinear system yields the same formula as the linear one and motivates us to extrapolate the next vector by the previous ones as in linear systems. Indeed, such an extension has been shown to be successful in various areas of science and engineering, e.g., computational fluid dynamics, semiconductor research, tomography and geometrical image processing .

III-B Derivations of MPE, RRE and SVD-MPE

We turn to discuss how to utilize an approximate way to obtain the next vector by extrapolating the previous ones. Due to the fact that the degree of the minimal polynomial can be as large as $N$ and we cannot obtain it, an arbitrary positive number is set as the degree, being much smaller than the true one. With such a replacement, the linear equations in (16) become inconsistent and there does not exist a solution for $\{c_{i}\},c_{\kappa}=1$ in the ordinary sense. Alternatively, we solve instead

where $\bm{c}=\begin{bmatrix}c_{0}&\cdots&c_{\kappa}\end{bmatrix}^{\mathcal{T}}$ and $\bm{U}_{\kappa}^{m}=\begin{bmatrix}\bm{u}_{m}&\cdots&\bm{u}_{m+\kappa}\end{bmatrix}$. Then evaluating $\gamma_{i}$ through ${c_{i}}/\left(\sum_{i=0}^{i=\kappa}c_{i}\right)$ results in the next vector $\bm{x}_{(m,\kappa)}=\sum_{i=0}^{\kappa}\gamma_{i}\bm{x}_{m+i}$ as a new approximation. This method is known as Minimal Polynomial Extrapolation (MPE) .

The detailed steps for obtaining the next vector through MPE are shown in Algorithm 1. To solve the constrained problem in (18), we suggest utilizing QR decomposition with the modified Gram-Schmidt (MGS) . The MGS procedure for the matrix $\bm{U}_{\kappa}^{m}$ is shown in Algorithm 2.

Now, let us discuss the other two variants of VE, i.e., Reduced Rank Extrapolation (RRE) and SVD-MPE . The main difference among RRE, MPE and SVD-MPE is at Step 2 in Algorithm 1 regarding the evaluation of $\{\gamma_{i}\}$. In RRE and SVD-MPE, we utilize the following methods to obtain $\{\gamma_{i}\}$:

Solving $\bm{R}_{\kappa}^{\mathcal{T}}\bm{R}_{\kappa}\bm{d}=\bm{1}$ through forward and backward substitution, we obtain $\bm{\gamma}$ through $\frac{\bm{d}}{\sum_{i}d_{i}}$. Actually, such a formulation of $\bm{\gamma}$ is the solution of:

Computing the SVD decomposition of $\bm{R}_{\kappa}=\bm{U}\bm{\Sigma}\bm{V}^{\mathcal{T}}$, we have $\bm{\gamma}=\frac{\bm{v}_{\kappa+1}}{\sum_{i}\bm{v}_{i,\kappa+1}}$ where $\bm{v}_{\kappa+1}$ and $\bm{v}_{i,\kappa+1}$ represent the last column and the $(i,\kappa+1)$th element of matrix $\bm{V}$, respectively.

Here are two remarks regarding RRE, MPE and SVD-MPE:

Observing the derivations of MPE, SVD-MPE and RRE, we notice that RRE’s solution must exist unconditionally, while MPE and SVD-MPE may not exist because the sum of $\{c_{i}\}$ and $\{v_{i,\kappa+1}\}$ in MPE and SVD-MPE may become zero. Thus RRE may be more robust in practice . However, MPE and RRE are related, as revealed in . Specifically, if MPE does not exist, we have $\bm{x}_{(m,\kappa)}^{RRE}=\bm{x}_{(m,\kappa-1)}^{RRE}$. Otherwise, the following holds

where $\mu_{\kappa}$, $\mu_{\kappa-1}$ and $v_{\kappa}$ are positive scalars depending only on $\bm{x}_{(m,\kappa)}^{RRE}$, $\bm{x}_{(m,\kappa-1)}^{RRE}$ and $\bm{x}_{(m,\kappa)}^{MPE}$, respectively. Furthermore, the performance of MPE and RRE is similar – both of the methods either perform well or work poorly .

Observe that we only need to store ${\kappa}+2$ vectors in memory at all steps in Algorithm 2. Formulating the matrix $\bm{U}_{m}^{\kappa}$, we overwrite the vector $\bm{x}_{m+i}$ with $\bm{u}_{m+i}=\bm{x}_{m+i}-\bm{x}_{m+i-1}$ when the latter is computed and only $\bm{x}_{m}$ is always in the memory. Next, $\bm{u}_{m+i}$ is overwritten by $\bm{q}_{i}$, $i=1,\cdots,{\kappa}+1$ in computing the matrix $\bm{Q}_{\kappa}$. Thus, we do not need to save the vectors $\bm{x}_{m+1},\cdots,\bm{x}_{m+{\kappa}+1}$, which implies that no additional memory is required in running Algorithm 2.

III-C Embedding VE in the Baseline Algorithm

We introduce VE in its cycling formulation for practical usage. One cycling means we activate the baseline algorithm to produce $\{\bm{x}_{i}\}$ and then utilize VE once to evaluate the new vector as a novel initial point. Naturally, we repeat such a cycling many times. The steps of utilizing VE in its cycling mode are shown in Algorithm 3. Few comments are in order:

In practice, we utilize VE in its cycling formulation. Specially, the iterative form shown in Algorithm 3 is named as full cycling . To save the complexity of computing $\{\gamma_{i}\}$, one may reuse the previous $\{\gamma_{i}\}$, a method known as cycling with frozen $\gamma_{i}$. Parallel VE can be also developed if more machines are available. Explaining details of the last two strategies is out of the scope of this paper. We refer the reader to for more information.

Numerical experience also indicates that cycling with even moderately large $m>0$ will avoid stalling from happening . Moreover, we also recommend setting $m>0$ when the problem becomes challenging to solve.

In our case, the termination criterion in Algorithm 3 can be the number of total iterations (the number of calling of the baseline algorithm) or the difference between consecutive two vectors. Furthermore, we also recommend giving additional iterations to activate the baseline algorithm after terminating the VE, which can stabilize the accelerated algorithm in practice.

III-D Convergence and Stability Properties

We mention existing results regarding the convergence and stability properties of VE for understanding this technique better. A rich literature has examined the convergence and stability properties of RRE, MPE and SVD-MPE in linear systems . Assuming the matrix $\bm{A}$ is diagonalizable, then in the $k$th iteration $\bm{x}_{k}$ should have the form $\bm{x}_{k}=\bm{x}^{*}+\sum_{i=1}^{\kappa}\bm{v}_{i}\lambda_{i}^{k}$ where $(\lambda_{i},\bm{v}_{i})$ are some or all of the eigenvalues and corresponding eigenvectors of $\bm{A}$, with distinct nonzero eigenvalues. By ordering $\lambda_{i}$ as $|\lambda_{1}|\geq|\lambda_{2}|\geq\cdots$, the following asymptotic performance holds for all of the three variants of VE when $|\lambda_{k}|>|\lambda_{k+1}|$:

This implies that the sequence $\{\bm{x}_{(m,\kappa)}\}_{m=0}^{\infty}$ converges to $\bm{x}^{*}$ faster than the original sequence $\{\bm{x}_{k}\}$.

As shown in (20), for a large $m$, (8) reduces the contributions of the smaller $\lambda_{i}$ to the error $\bm{x}_{(m,\kappa)}-\bm{x}^{*}$, while VE eliminates the contributions of the $\kappa$ largest $\lambda_{i}$. This indicates that $\bm{x}_{(m,\kappa)}-\bm{x}^{*}$ is smaller than each of the errors $\bm{x}_{m+i}-\bm{x}^{*},~{}i=0,1,\cdots,\kappa$, when $m$ is large enough. We mention another observation that an increasing $\kappa$ generally results in a faster convergence of VE. However, a large $\kappa$ has to increase the storage requirements and also requires a much higher computational cost. Numerical experiments indicate that a moderate $\kappa$ can already works well in practice.

If the following condition is held, we say VE is stable:

Here, we denote $\{\gamma_{i}\}$ by $\{\gamma_{i}^{(m,\kappa)}\}$ to show their dependence on $m$ and $\kappa$. If (21) holds true, the error in $\bm{x}_{i}$ will not magnify severely. As shown in , MPE and RRE obey such a stability property.

For nonlinear systems, the analysis of convergence and stability becomes extremely challenging. One of the main results is the quadratic convergence theorem . This theorem is built on one special assumption that $\kappa$ is set to be the degree of the minimal polynomial of $\bm{F}^{\prime}(\bm{x}^{*})$. The proof of the quadratic convergence was shown in . In a following work, Smith, Ford and Sidi noticed that there exists a gap in the previous proof . Jbilou et al. suggested two more conditions in order to close the gap :

The matrix $\bm{F}^{\prime}(\bm{x}^{*})-\bm{I}$ is nonsingular

$\bm{F}^{\prime}(\cdot)$ satisfies the following Lipschitz condition:

Surprisingly, these two conditions are met by the RED scheme. The first condition is satisfied by the fact

The second one is also true, due to the assumption in RED that the denoiser $f(\bm{x})$ is differentiable. So we claim that it is possible for VE to solve RED with quadratic convergence rate.

Although VE can lead to a quadratic convergence rate, trying to achieve such a rate may not be realistic because $\kappa$ can be as large as $N$. However, we may obtain a linear but fast convergence in practice with even moderate values of $m$ and $\kappa$, which is also demonstrated in the following numerical experiments.

IV Experimental Results

We follow the same experiments of image deblurring and super-resolution as presented in to investigate the performance of VE in acceleration. The trainable nonlinear reaction diffusion (TNRD) method is chosen as the denoising engine. Mainly, we choose the FP method as our baseline algorithm. For a fair comparison, the same parameters suggested in for different image processing tasks are set in our experiments. In , the authors compared RED with other popular algorithms in image deblurring and super-resolution tasks, showing its superiority. As the main purpose in this paper is to present the acceleration of our method for solving RED, we omit the comparisons with other popular algorithms. In the following, we mainly show the acceleration of applying MPE with FP for solving RED first and then discuss the choice of parameters in VE, i.e., $m$ and $\kappa$. In addition, we compare our method with three other methods, steepest descent (SD), Nesterov’s acceleration and Limited-memory BFGS (L-BFGS) . Note that we need to determine a proper step-size for the above methods . However, evaluating the objective value or gradient in RED is expensive implying that any line-search method becomes prohibitive. Note that, in contrast, in our framework as described in Algorithm 3 does not suffer from such a problem. In the following, we manually choose a fixed step-size for getting a good convergence behavior. Finally, we compare the difference among RRE, MPE and SVD-MPE. All of the experiments are conducted on a workstation with Intel(R) Xeon(R) CPU E5-2699 @2.20GHz.

In this experiment, we degrade the test images by convolving with two different point spread functions (PSFs), i.e., $9\times 9$ uniform blur and a Gaussian blur with a standard derivation of $1.6$. In both of these cases, we add an additive Gaussian noise with $\sigma=\sqrt{2}$ to the blurred images. The parameters $m$ and $\kappa$ in Algorithm 3 are set to and $5$ for the image deblurring task. Additionally, we apply VE to the case where the baseline algorithm is SD, called SD-MPE, with the parameters $m$ and $\kappa$ are chosen as and $8$. The value of the cost function and peak signal to noise ratio (PSNR) versus iteration or CPU time are given in Fig.s 2 and 3 The goal of this paper is to investigate the performance of solving RED with VE rather than the restoration results. Therefore, we present the recovered PSNR versus iteration or running time. One can utilize some no-reference quality metrics like NFERM and ARISMc to further examine the restoration results.. These correspond to both a uniform and a Gaussian blur kernels, all tested on the “starfish” image. Clearly, we observe that SD is the slowest algorithm. Surprisingly, SD-MPE and Nesterov’s method yield almost the same convergence speed, despite their totally different scheme. Moreover, We note that FP is faster than L-BFGS, Nesterov’s method and SD-MPE. Undoubtedly, FP-MPE is the fastest one, both in terms of iterations and CPU time, which indicates the effectiveness of MPE’s acceleration. To provide a visual effect, we show the change in reconstructed quality of different algorithms in Fig. 1. Clearly, the third column of FP-MPE achieves the best reconstruction faster, while other methods need more iterations to obtain a comparable result.

Additional nine test images suggested in are also included in our experiments, in order to investigate the performance of VE further. In this experiment we focus on the comparison between FP-MPE and FP for the additional images. We run the native FP method $200$ iterations first and denote the final image by $\bm{x}^{*}$. Clearly, the corresponding cost-value is $E(\bm{x}^{*})$. We activate Algorithm 3 with the same initial value as used in the FP method to examine how many iterations are needed to attain the same or lower objective value than $E(\bm{x}^{*})$. The final number of iterations with different images are given in Table I. Clearly, an acceleration is observed in all the test images in the image deblurring task.

IV-B Image super-resolution

We generate a low resolution image by blurring the ground truth one with a $7\times 7$ Gaussian kernel with standard derivation $1.6$ and then downsample by a factor of $3$. Afterwards, an additive Gaussian noise with $\sigma=5$ is added to the resulting image. The same parameters $m$ and $\kappa$ used in the deblurring task for FP-MPE are adopted here. For SD-MPE, the parameters $m$ and $\kappa$ are set to $1$ and $10$, respectively. We choose “Plants” as our test image because it needs more iterations for FP-MPE to converge. As observed from Fig. 4, while L-BFGS and the Nesterov’s method are faster than the FP method, our acceleration method (FP-MPE) is quite competitive with both. Furthermore, we investigate all of the test images as shown in to see how many iterations are needed for MPE to achieve the same or lower cost compared with the FP method. The results are shown in Table II. As can be seen, MPE works better than the FP method indicating an effective acceleration for solving RED.

IV-C The Choice of the Parameters and the Difference Among RRE, MPE and SVD-MPE

Conclude by discussing the robustness to the choice of parameters $m$ and $\kappa$ for the MPE algorithm. To this end, the single image super-resolution task is chosen as our study. Furthermore, we choose to demonstrate this robustness on the “Plants” image since it required the largest number of iterations in the MPE recovery process. As seen from Fig.s 5(a) - 5(c), MPE always converges faster than the regular FP method with different $m$ and $\kappa$. Moreover, we also observe that a lower objective value is attained through MPE. Notice that MPE has some oscillations because it is not a monotonically accelerated technique. However, we still see a lower cost is achieved if additional iterations are given.

In part (d) of Fig. 5, an optimal pair of $m$ and $\kappa$ is chosen for MPE, RRE and SVD-MPE for the single image super-resolution task with the “Plants” image.The optimal $m$ and $\kappa$ are obtained by searching in the range $$with$\kappa\geq 2$, seeking the fastest convergence for these three methods. We see that all three methods yield an acceleration and a lower cost, demonstrating the effectiveness of the various variants of VE. Moreover, we see that SVD-MPE converges faster at the beginning, but MPE yields a lowest eventual cost.

V Conclusion

The work reported in introduced RED – a flexible framework for using arbitrary image denoising algorithms as priors for general inverse problems. This scheme amounts to iterative algorithms in which the denoiser is called repeatedly. While appealing and quite practical, there is one major weakness to the RED scheme – the complexity of denoising algorithms is typically high which implies that the use of RED is likely to be costly in run-time. This work aims at deploying RED efficiently, alleviating the above described shortcoming. An accelerated technique is proposed in this paper, based on the Vector Extrapolation (VE) methodology. The proposed algorithms are demonstrated to substantially reduce the number of overall iterations required for the overall recovery process. We also observe that the choice of the parameters in the VE scheme is robust.

References