Acceleration of RED via Vector Extrapolation

Tao Hong, Yaniv Romano, Michael Elad

Abstract: Models play an important role in inverse problems, serving as the prior for representing the original signal to be recovered. REgularization by Denoising (RED) is a recently introduced general framework for constructing such priors using state-of-the-art denoising algorithms. Using RED, solving inverse problems is shown to amount to an iterated denoising process. However, as the complexity of denoising algorithms is generally high, this might lead to an overall slow algorithm. In this paper, we suggest an accelerated technique based on vector extrapolation (VE) to speed-up existing RED solvers. Numerical experiments validate the obtained gain by VE, leading to a substantial savings in computations compared with the original fixed-point method.

Introduction

Inverse problems in imaging—such as deblurring, super-resolution, and inpainting—aim to recover a clean image from a corrupted version. A critical component in solving these is the "prior," which describes what a clean image should look like. The REgularization by Denoising (RED) framework is a popular approach that allows researchers to use state-of-the-art image denoisers (like TNRD or BM3D) as priors. While RED produces excellent results, it is notoriously slow, typically requiring hundreds of iterations of a "Fixed-Point" (FP) algorithm. Since each iteration involves running a complex, computationally expensive denoising algorithm, the total time cost is massive. This paper introduces an accelerated solver for the RED framework by incorporating Vector Extrapolation (VE) techniques to reach the solution in far fewer steps.

Methodology

The proposed method uses Vector Extrapolation to accelerate the standard Fixed-Point (FP) solver used in RED. VE is a family of numerical techniques designed to speed up the convergence of sequences by using a small window of previous iterates to "predict" where the sequence is heading. The paper explores three main variants: Minimal Polynomial Extrapolation (MPE), Reduced Rank Extrapolation (RRE), and Singular Value Decomposition MPE (SVD-MPE).

The core strategy is a "cycling" approach: run the standard RED FP algorithm for a few steps, collect a small set of consecutive iterates, and apply a VE method to compute a "jump" to a new, more advanced initial point. While VE is traditionally used for linear systems, it is highly effective for the non-linear iterations found in RED because these systems behave linearly as they approach their fixed point.

Experimental Setup

The method was evaluated on standard image restoration benchmarks, including image deblurring (on ten classic images like Starfish and Butterfly) and super-resolution (on nine images with a scaling factor of 3). The Trainable Nonlinear Reaction Diffusion (TNRD) method was used as the "black-box" denoiser within the RED framework.

Key Results and Discussion

The proposed FP-MPE (Fixed-Point with Minimal Polynomial Extrapolation) consistently outperformed standard FP, Steepest Descent, Nesterov’s acceleration, and L-BFGS in convergence speed. In deblurring tasks, FP-MPE reached the same objective value as the standard FP method in 50% to 75% fewer iterations. For example, on the "Starfish" image with uniform blur, standard RED took 200 iterations, while FP-MPE reached the same result in just 50–60 iterations.

Visual comparisons demonstrate that the accelerated method achieves high-quality reconstruction much faster than other techniques.

Standard Fixed-Point (FP) iteration progress for image deblurring.
Proposed FP-MPE iteration progress, showing significantly faster convergence to high-quality results.

A key insight is that non-linear iterative systems like RED can be locally approximated as linear systems near their solution, allowing VE to effectively cancel out the largest error components and "leapfrog" over standard iterations. The method is robust to internal parameters like window size, with even small windows providing significant gains.

Conclusion and Future Work

Vector Extrapolation provides a computational speedup of over 50% without sacrificing image quality in the RED framework. While VE requires additional memory to store image vectors, it is manageable for standard restoration tasks. Future work could explore performance with even more complex, non-differentiable, or deep-learning-based denoisers, as well as automated ways to adapt parameters during runtime.

Summary updated

Abstract

Models play an important role in inverse problems, serving as the prior for representing the original signal to be recovered. REgularization by Denoising (RED) is a recently introduced general framework for constructing such priors using state-of-the-art denoising algorithms. Using RED, solving inverse problems is shown to amount to an iterated denoising process. However, as the complexity of denoising algorithms is generally high, this might lead to an overall slow algorithm. In this paper, we suggest an accelerated technique based on vector extrapolation (VE) to speed-up existing RED solvers. Numerical experiments validate the obtained gain by VE, leading to a substantial savings in computations compared with the original fixed-point method.
BibTeX
@article{hong2019acceleration,
  author = {Tao Hong and Yaniv Romano and Michael Elad},
  title = {{Acceleration of RED via Vector Extrapolation}},
  journal = {J. Vis. Commun. Image Represent.},
  year = {2019},
  doi = {10.1016/j.jvcir.2019.102575},
}
Figure