Acceleration of RED via vector extrapolation

Tao Hong, Yaniv Romano, Michael Elad

This paper introduces an accelerated solver for the REgularization by Denoising (RED) framework by incorporating Vector Extrapolation (VE) techniques. By treating the iterative restoration process as a sequence of vectors and "extrapolating" toward its limit, the authors achieve a computational speedup of over 50% without sacrificing image quality.

TL;DR

RED is a powerful framework for image restoration that is often bottlenecked by slow convergence. This paper uses Vector Extrapolation to "jump" toward the solution, cutting computation time by more than half while maintaining state-of-the-art reconstruction quality.

What Problem Does This Paper Address?

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 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. It typically requires 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 tackles this bottleneck, seeking a way to reach the solution in far fewer steps.

Methods

The authors propose using Vector Extrapolation (VE) 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. Instead of just taking the next step in an iterative process, VE looks at a small window of previous iterates and uses them to "predict" where the sequence is heading. The paper explores three main variants:

  1. Minimal Polynomial Extrapolation (MPE)
  2. Reduced Rank Extrapolation (RRE)
  3. Singular Value Decomposition MPE (SVD-MPE)

The core strategy is a "cycling" approach:

  • Run the standard RED FP algorithm for a few steps ($m$).
  • Collect a small set of consecutive iterates ($\kappa$).
  • Apply a VE method to compute a "jump" to a new, more advanced initial point.
  • Repeat until convergence.

While VE is traditionally used for linear systems, the authors demonstrate that it is highly effective for the non-linear iterations found in RED because these systems behave linearly as they approach their fixed point.

Datasets

The authors evaluated their method on standard image restoration benchmarks:

  • Image Deblurring: Tested on ten classic images (e.g., Starfish, Butterfly, Leaves, Boats) using both uniform and Gaussian blur kernels.
  • Super-Resolution: Tested on nine images (e.g., Plants, Raccoon, Bike) with a scaling factor of 3.
  • Denoising Engine: They used the Trainable Nonlinear Reaction Diffusion (TNRD) method as the "black-box" denoiser within the RED framework.

Key Insights and Ideas

  • Linearity in Non-Linearity: A key insight is that non-linear iterative systems (like RED) can be locally approximated as linear systems near their solution. This allows VE techniques, originally built for linear algebra, to provide massive speedups in complex image processing tasks.
  • Error Elimination: VE works by effectively canceling out the largest error components of the iteration matrix, allowing the algorithm to "leapfrog" over dozens of standard iterations.
  • Parameter Robustness: The method is robust to its internal parameters (the window size $\kappa$ and the number of initial steps $m$). Even small windows (e.g., $\kappa=5$) provide significant gains.

Key Results

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.

  • Computational Savings: 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 Quality: The accelerated method achieves high-quality reconstruction much faster than other techniques.
Visual comparison of deblurring algorithms. The bottom row (f) shows the proposed FP-MPE reaching high quality significantly faster than the baseline FP in row (e).
  • Stability: The authors showed that the conditions required for VE to achieve fast convergence are naturally met by the RED framework due to the differentiability and passivity of the denoisers used.

Limitations and Future Work

  • Memory Overhead: VE requires storing $\kappa+2$ image vectors in memory to perform the extrapolation. While manageable for standard images, this could be a constraint for very high-resolution 3D data (like medical CT/MRI).
  • Denoiser Choice: The study primarily focused on the TNRD denoiser. Future work could explore how VE performs with even more complex, non-differentiable, or deep-learning-based "black-box" denoisers.
  • Parameter Tuning: While robust, finding the optimal $m$ and $\kappa$ for a specific task still requires some manual experimentation. Automated ways to adapt these parameters during runtime could be a promising research direction.

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 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},
}

Loading related content...

Figure