PaperlayerView exact revision on arXiv

Source-linked AI summary

Regularization by Denoising: Clarifications and New Interpretations

Edward T. Reehorst, Philip Schniter

arXiv:1806.02296v4cs.CV

TL;DR

The paper addresses why RED’s explicit regularization interpretation fails for practical non-symmetric denoisers. It proposes SMD and develops algorithmic and consensus-equilibrium interpretations, while concluding that explicit regularization cannot explain RED for non-JS denoisers.

  • Problem

    RED’s explicit regularization interpretation is unsupported for many practical denoisers because the required Jacobian symmetry does not hold.

  • Method

    The paper introduces SMD to match a score rather than construct an explicit regularizer, and analyzes RED through denoising, accelerated algorithms, and consensus equilibrium.

  • Results

    The paper establishes that non-JS denoisers admit no regularizer with gradient x − f(x), while connecting SMD to kernel density estimation and constrained MMSE denoising.

  • Takeaways & Limitations

    RED is interpreted through score matching and consensus equilibrium rather than explicit regularization when practical denoisers lack Jacobian symmetry.

  • Takeaways & Limitations

    The explicit-regularization explanation is ruled out for non-JS denoisers, including practical methods such as non-local means, BM3D, TNRD, and DnCNN.

Abstract

from arXiv · show

Regularization by Denoising (RED), as recently proposed by Romano, Elad, and Milanfar, is powerful image-recovery framework that aims to minimize an explicit regularization objective constructed from a plug-in image-denoising function. Experimental evidence suggests that the RED algorithms are state-of-the-art. We claim, however, that explicit regularization does not explain the RED algorithms. In particular, we show that many of the expressions in the paper by Romano et al. hold only when the denoiser has a symmetric Jacobian, and we demonstrate that such symmetry does not occur with practical denoisers such as non-local means, BM3D, TNRD, and DnCNN. To explain the RED algorithms, we propose a new framework called Score-Matching by Denoising (SMD), which aims to match a "score" (i.e., the gradient of a log-prior). We then show tight connections between SMD, kernel density estimation, and constrained minimum mean-squared error denoising. Furthermore, we interpret the RED algorithms from Romano et al. and propose new algorithms with acceleration and convergence guarantees. Finally, we show that the RED algorithms seek a consensus equilibrium solution, which facilitates a comparison to plug-and-play ADMM.

I. INTRODUCTION

The paper examines RED image recovery and argues that its explicit regularization interpretation fails for many practical denoisers. It introduces SMD and related algorithmic and equilibrium interpretations to explain RED more broadly.

  • Accurate image priors are difficult to obtain, motivating denoiser-based approaches to image recovery.
  • RED constructs an explicit regularizer from a plug-in denoiser and uses it within a variational image-recovery framework.
  • RED recovery algorithms based on steepest descent, ADMM, and fixed-point methods achieve state-of-the-art performance in deblurring and super-resolution.
  • For many practical denoisers, RED algorithms do not minimize the stated variational objective because the required Jacobian symmetry is absent.
  • SMD matches the gradient of a log-prior and connects RED analysis to kernel density estimation, constrained MMSE denoising, accelerated algorithms, and consensus equilibrium.

C. Plug-and-Play ADMM

This section places RED alongside plug-and-play denoising methods and explains how denoising enters ADMM-style recovery algorithms. It also frames the uncertainty about the objective minimized when no explicit regularizer exists.

  • The denoising update can be viewed as variational denoising of an internal iterate plus a dual variable.
  • PnP-ADMM replaces the ADMM proximal update with a sophisticated image denoiser such as BM3D.
  • When the denoiser has no explicit regularizer, the objective minimized by PnP-ADMM is unclear, although numerical experiments show strong performance.
  • RED similarly constructs an explicit regularizer from an arbitrary denoiser to enable variational optimization and convergence analysis.
  • The RED gradient rule and fixed-point condition motivate iterative RED algorithms, but the paper shows their regularization explanation requires local homogeneity and Jacobian symmetry.

B. The RED Gradient

The RED gradient expression is valid only under local homogeneity and Jacobian symmetry. When symmetry fails, no explicit regularizer can generally produce the RED fixed-point gradient, although some denoiser classes do satisfy symmetry.

  • Local homogeneity implies that the denoiser Jacobian applied to the image equals the denoiser output.
  • Under local homogeneity, the RED gradient expression holds if and only if the denoiser Jacobian is symmetric.
  • C. Impossibility of Explicit Regularization: For a non-symmetric denoiser Jacobian, no regularization function has gradient x − f(x), making explicit regularization impossible for the RED algorithms.
  • C. Impossibility of Explicit Regularization: The obstruction concerns explicit regularization generally, not merely the particular RED regularizer.
  • D. Analysis of Jacobian Symmetry: Transform-domain thresholding denoisers can have perfectly symmetric Jacobians.
  • D. Analysis of Jacobian Symmetry: MAP and MMSE-optimal denoisers under assumed priors also have symmetric Jacobians, but symmetry is difficult to establish for approximate MAP or MMSE denoisers.

E. Jacobian Symmetry Experiments

Experiments show that practical denoisers generally violate Jacobian symmetry, while gradient accuracy depends on both symmetry and local homogeneity. Small local-homogeneity imperfections can substantially disrupt RED gradient expressions.

  • Jacobian symmetry measurement: Numerical Jacobians are evaluated by finite differences, and symmetry error should be nearly zero for a symmetric Jacobian.The perturbation uses ϵ = 1 × 10^-3 in the experiments.
  • Jacobian symmetry results: Table I reports average Jacobian-symmetry error on 17 image patches, showing that all tested denoisers except TDT are far from symmetric.The evaluation uses 16×16 patches and denoisers including MF, NLM, BM3D, TNRD, and DnCNN.
  • Gradient accuracy: For all tested denoisers, the numerical gradient matches RED expression (22) closely but not expression (13).The mismatch with expression (13) is attributed partly to insufficient Jacobian symmetry and partly to insufficient local homogeneity.
  • Local homogeneity results: The local-homogeneity metric eLH,1 has small average error for all denoisers, whereas eLH,2 has errors several orders of magnitude larger except for MF.BM3D has an eLH,2 error several orders of magnitude higher than the other denoisers.
  • Interpreting gradient errors: TDT’s gradient error is attributed to insufficient local homogeneity, despite its symmetric Jacobian.For MF, local homogeneity is satisfied and expression (38) is accurate, while expression (13) is inaccurate because Jacobian symmetry fails.
  • Interpreting gradient errors: NLM, BM3D, TNRD, and DnCNN exhibit both nontrivial Jacobian-symmetry and local-homogeneity errors, making expressions (13) and (38) inaccurate.Overall, the experiments find both RED gradient expressions highly sensitive to small local-homogeneity imperfections.

G. Hessian and Convexity

The paper shows that the Hessian of the RED regularizer differs from the earlier expression even under Jacobian symmetry, potentially affecting convexity. An example further demonstrates that RED iterations can approach a fixed point without minimizing the RED cost.

  • Hessian expression: The derived Hessian expression differs from the expression reported in prior RED work, even when the denoiser has a symmetric Jacobian.This discrepancy arises in the Hessian formulas themselves, not only from nonsymmetric denoisers.
  • Convexity: Even when Jf(x) has eigenvalues in [0, 1], the RED Hessian may fail to be positive semidefinite because of an additional term.The paper notes possible negative implications for convexity of ρred.
  • RED-SD trajectory: In a RED-SD experiment, the fixed-point error decreases asymptotically, but the RED cost does not decrease with iteration.The experiment uses a 3 × 3 median filter, the Starfish image, and noisy measurements with σ2 = 20.
  • Algorithmic implication: Because the monitored RED objective may not decrease, optimization procedures that rely on objective monitoring, such as backtracking line search, are difficult to apply.This follows from the observed divergence between fixed-point convergence and RED-cost behavior.
  • Fixed points versus minimizers: The RED-cost minimizer need not coincide with the RED fixed point, and the cost may be nonsmooth or nonconvex for tested denoisers.The visualization includes TDT, MF, NLM, BM3D, TNRD, and DnCNN.

A. Tweedie Regularization

Tweedie regularization constructs an explicit regularizer from an MMSE denoiser and connects this construction to KDE. Its fixed-point condition matches RED, but the framework is limited to symmetric-Jacobian denoisers, motivating SMD.

  • Tweedie regularization is introduced as a precursor to score-matching by denoising.
  • The framework models noisy pseudomeasurements and defines a regularizer using an MMSE denoiser under a prior model.The likelihood is Gaussian, with pseudomeasurements formed as the image plus Gaussian noise.
  • The Tweedie regularizer has a gradient property that makes its solutions satisfy the RED fixed-point condition.This follows from Tweedie’s formula, which connects the denoiser to the gradient of the regularizer.
  • Tweedie regularization arises naturally when kernel density estimation smooths an empirical image prior.Using KDE as a surrogate prior yields a corresponding MAP optimization problem.
  • The framework addresses unknown priors and MMSE denoisers, but its denoisers have symmetric Jacobians, motivating SMD for non-symmetric cases.Approximating the unknown prior or denoiser can affect estimate quality, while direct gradient computation may be too expensive for large training corpora.

D. Relation to Existing Work

The paper relates RED to Tweedie’s formula, score matching, autoencoder analyses, and plug-and-play methods. It also interprets RED-ADMM and explains why limited inner iterations can be computationally useful.

  • Tweedie’s formula connects RED’s explicit regularizer and fixed-point equation to SURE and autoencoding-based image-prior interpretations.
  • The autoencoder analogy supports score matching rather than energy minimization when reconstruction Jacobians are non-symmetric.The paper distinguishes its exact Tweedie relationship from prior small-noise approximations.
  • RED-ADMM: RED-ADMM is obtained by approximating the proximal update with inner iterations based on the RED fixed-point relationship.The implementation is faithful to ADMM when the number of inner iterations is large.
  • RED-ADMM: I = 1 inner iterations gives the fastest convergence in the reported TNRD-based RED-ADMM runtime experiment.The experiment compares I = 1, 2, 3, 4 using PSNR trajectories versus runtime.
  • RED-ADMM: With I = 1, inexact RED-ADMM replaces the proximal step with a gradient-descent step and becomes reminiscent of proximal gradient.

C. Majorization-Minimization and Proximal-Gradient RED

The paper develops proximal-gradient interpretations of RED through majorization-minimization. RED-PG includes RED-FP as a special case, while the framework supplies convergence conditions and supports acceleration.

  • The proposed RED-PG method uses a quadratic upper bound on the regularizer within a majorization-minimization framework.
  • Convergence is guaranteed when L ≥ Lρ under the stated convexity and Lipschitz-gradient conditions.
  • RED-PG alternates a gradient update involving the denoiser with a proximal update on the loss.
  • Setting L = 1 makes RED-PG identical to the RED-FP algorithm, while arbitrary L > 0 generalizes the step-size choice.The same formulation also extends RED-FP to possibly non-quadratic loss functions.
  • RED-PG and inexact RED-ADMM with I = 1 share alternating proximal and denoiser-based gradient updates, but the ADMM variant adds a state variable.Experiments suggest that this extra state variable is not necessarily advantageous.

D. Dynamic RED-PG

Dynamic RED-PG varies its proximal-gradient parameter according to a fixed schedule because denoiser regularity can prevent line search. The paper also proposes accelerated RED-PG and reports faster practical convergence.

  • A line search for L cannot be evaluated with non-locally-homogeneous or non-symmetric denoisers because the regularizer is unavailable.
  • Dynamic RED-PG: RED-DPG varies Lk according to a fixed schedule by interpolating between selected L0 and L∞ values.
  • Dynamic RED-PG: With appropriate L0 and L∞, RED-DPG can be significantly faster than RED-FP in numerical experiments.
  • RED extends to non-quadratic loss functions, which is important for applications such as phase retrieval.
  • Accelerated RED-PG: RED-APG applies FISTA-style momentum, and experiments suggest it is the fastest among the discussed RED algorithms.
  • Accelerated RED-PG: The paper cannot compare its acceleration schemes with a vector-extrapolation method because the authors could not reproduce that method’s results.

F. Convergence of RED-PG

RED-PG is shown to converge to a fixed point under convex-loss, non-expansive-denoiser, step-size, and fixed-point existence conditions, while experiments compare convergence behavior across RED algorithms.

  • Convergence guarantee: The RED-PG iteration operator is α-averaged, with α determined by the proximal and denoising operators.The proof uses composition of averaged operators and identifies the iteration as a Mann iteration.
  • Convergence guarantee: Under the stated assumptions, RED-PG converges when its iteration operator has at least one fixed point.The assumptions require a proper, convex, continuous loss, a non-expansive denoiser, and L > 1.
  • Convergence guarantee: The iterates form a convergent sequence whose limit is a fixed point of the RED-PG operator.The convergence proof establishes limk→∞∥xk − x⋆∥ = 0 for some fixed point x⋆.
  • Algorithm comparison: With TNRD denoising, RED-DPG and RED-APG appear faster than RED-FP and RED-ADMM-I = 1; RED-APG reaches PSNR = 30 in 15 iterations versus about 50.The comparison uses the starfish deblurring experiment with a 9×9 uniform blur kernel and AWGN variance σ2 = 2.
  • Algorithm comparison: For TNRD denoising, RED-APG and RED-ADMM do not show vanishing fixed-point error or update distance, suggesting convergence to a limit cycle rather than a unique limit point.Other tested algorithms appear to converge toward the fixed-point solution set, while these two only approximately satisfy the fixed-point equation.
  • Algorithm comparison: With TDT denoising, final PSNR values are nearly identical across algorithms but more than 1 dB worse than values around iteration 20.Most fixed-point errors remain near 10^-7, attributed to numerical precision, while normalized update distances decrease to zero for all tested algorithms.

VI. EQUILIBRIUM VIEW OF RED ALGORITHMS

The paper recasts RED algorithms as consensus-equilibrium solvers rather than explicit-cost minimizers, deriving algorithm-specific equilibrium operators and relating RED-PG to RED-ADMM.

  • Equilibrium interpretation: RED algorithms seek consensus-equilibrium solutions, but their denoiser-side operator differs from the one used by PnP-ADMM.The paper identifies G ≠ Gpnp while retaining the consensus-equilibrium framework.
  • RED-ADMM: The RED-ADMM equilibrium is a special case of the fixed-point equation (15).The derivation connects the equilibrium solution generated by RED-ADMM to the same fixed-point equation analyzed elsewhere in the paper.
  • RED-ADMM: For RED-ADMM, the measurement-side operator equals the ADMM operator, while the denoiser-side operator is Gred-admm.Gred-admm is obtained from the RED-ADMM gradient relation ∇ρ(x) = x − f(x).
  • RED-PG: RED-PG has an equilibrium representation whose denoiser-side operator equals Gred-admm when L = β/λ.This equality connects RED-PG and RED-ADMM equilibrium descriptions under the stated parameter relationship.

B. Interpreting the RED Equilibria

The equilibrium view distinguishes RED from PnP-ADMM by showing that RED balances denoiser and measurement residuals to produce a fixed-point solution, while practical explicit-regularization explanations require stronger denoiser conditions.

  • Interpreting RED equilibria: The RED equilibrium formulation is reminiscent of, but generally not equivalent to, an alternative RED formulation proposed earlier.The paper explicitly limits the relationship to resemblance rather than equivalence.
  • Interpreting RED equilibria: PnP-ADMM reports the denoiser output f(y), whereas RED reports a fixed point whose denoiser residual negates its measurement residual.For RED in the denoising case, A = I and the reported solution satisfies the fixed-point equation (15).
  • Explicit regularization: The paper concludes that explicit RED regularization requires both a locally homogeneous denoiser and a symmetric Jacobian.Practical denoisers including median filtering, NLM, BM3D, TNRD, and DnCNN lack sufficient Jacobian symmetry according to the reported numerical evidence.
  • SMD interpretation: SMD explains RED by matching the score, defined as the gradient of the log-prior, rather than designing an explicit regularizer.The paper also establishes tight connections between SMD, kernel density estimation, and constrained MMSE denoising.
  • Contributions: The paper presents new interpretations and faster RED algorithms, then uses consensus-equilibrium analysis to relate RED to PnP-ADMM.The conclusion reports these as the paper’s algorithmic and interpretive contributions.
Loading 1806.02296v4…