PaperlayerView exact revision on arXiv

Source-linked AI summary

Plug-and-Play ADMM for Image Restoration: Fixed Point Convergence and Applications

Stanley H. Chan, Xiran Wang, Omar A. Elgendy

arXiv:1605.01710v2cs.CV

TL;DR

Plug-and-Play ADMM has promising empirical performance, but its convergence conditions and efficient implementation for image restoration were unclear. The paper introduces a continuation-based method analyzed for bounded denoisers, proves fixed-point convergence, and develops fast implementations for super-resolution and single-photon imaging. Experiments compare the method with existing algorithms and report promising results.

  • Problem

    General Plug-and-Play ADMM lacks known convergence guarantees for arbitrary denoisers, and efficient implementations for common restoration problems remain unclear.

  • Method

    The paper adds a continuation scheme to Plug-and-Play ADMM and analyzes it for bounded denoisers, while developing fast implementations for super-resolution and single-photon imaging.

  • Results

    The proposed Plug-and-Play ADMM has provable fixed-point convergence for bounded denoisers and demonstrates promising experimental performance in the presented applications.

  • Takeaways & Limitations

    A broad asymptotic denoiser condition supports fixed-point convergence, while application-specific techniques make Plug-and-Play ADMM faster to implement.

Abstract

from arXiv · show

Alternating direction method of multiplier (ADMM) is a widely used algorithm for solving constrained optimization problems in image restoration. Among many useful features, one critical feature of the ADMM algorithm is its modular structure which allows one to plug in any off-the-shelf image denoising algorithm for a subproblem in the ADMM algorithm. Because of the plug-in nature, this type of ADMM algorithms is coined the name "Plug-and-Play ADMM". Plug-and-Play ADMM has demonstrated promising empirical results in a number of recent papers. However, it is unclear under what conditions and by using what denoising algorithms would it guarantee convergence. Also, since Plug-and-Play ADMM uses a specific way to split the variables, it is unclear if fast implementation can be made for common Gaussian and Poissonian image restoration problems. In this paper, we propose a Plug-and-Play ADMM algorithm with provable fixed point convergence. We show that for any denoising algorithm satisfying an asymptotic criteria, called bounded denoisers, Plug-and-Play ADMM converges to a fixed point under a continuation scheme. We also present fast implementations for two image restoration problems on super-resolution and single-photon imaging. We compare Plug-and-Play ADMM with state-of-the-art algorithms in each problem type, and demonstrate promising experimental results of the algorithm.

I. INTRODUCTION

The paper frames image restoration as MAP estimation solved through ADMM's modular inversion and denoising steps, enabling off-the-shelf denoisers in Plug-and-Play ADMM. This flexibility has produced promising empirical results, but the denoising subproblem's prior and theoretical behavior remain important concerns.

  • Problem formulation: Image restoration can be formulated as a MAP problem that combines a forward imaging model with a prior on the latent image.The MAP formulation is equivalent to an optimization problem involving data fidelity and prior terms.
  • ADMM framework: ADMM converts the unconstrained optimization into a constrained problem and solves it through alternating subproblems involving an augmented Lagrangian.Under standard convexity and saddle-point conditions, the conventional ADMM iterates converge to the solution.
  • ADMM framework: ADMM's modular structure separates an inversion step involving the forward model from a denoising step involving the prior.The denoising subproblem can recover standard total-variation denoising when the prior is the total variation norm.
  • Plug-and-Play ADMM: Plug-and-Play ADMM replaces the prior-based denoising subproblem with an off-the-shelf denoising algorithm Dσ.The resulting method is heuristic because the denoiser is not necessarily specified through an explicit prior.
  • Plug-and-Play ADMM: Plug-and-Play ADMM has shown better empirical performance than some state-of-the-art methods across several image reconstruction problems.The cited observations motivate studying its theoretical foundations despite its heuristic construction.

C. Challenges of Plug-and-Play ADMM

The paper identifies unresolved questions about Plug-and-Play ADMM's convergence, implicit prior, and efficient implementation. It addresses convergence and implementation by introducing bounded-denoiser theory, continuation, and fast application-specific methods.

  • Open challenges: General Plug-and-Play ADMM convergence is unknown because the denoiser may be nonlinear and lacks a closed-form expression.Earlier convergence analysis covered symmetric smoothing filters, while classical ADMM theory assumes an explicit closed, proper, convex prior.
  • Open challenges: The implicit prior corresponding to a general off-the-shelf denoiser is unclear beyond symmetric smoothing filters.The paper explicitly distinguishes this unresolved prior-identification issue from the convergence and implementation questions it addresses.
  • Open challenges: Efficient implementation is challenging because Plug-and-Play ADMM's variable splitting can require multiple splits or an inner conjugate-gradient solver.These alternatives introduce extra multipliers and parameters, or require an iterative solver that can be computationally expensive.
  • Proposed approach: Bounded denoisers approach the identity operator as the denoising parameter vanishes, a weaker condition than non-expansiveness.The paper argues this class is broad and uses it to establish fixed-point convergence under continuation.
  • Applications: The paper develops fast implementations for super-resolution and single-photon imaging.Polyphase decomposition gives closed-form super-resolution subproblem solutions, while separability enables a fast single-photon implementation.
  • Proposed approach: The proposed continuation scheme increases ρk, while the denoising strength is controlled by σk and λ/ρk.The paper gives monotone and adaptive update rules, including ρk+1 = γρk when the relative residue condition is met.

B. Global and Fixed Point Convergence

Because general Plug-and-Play denoisers may not define a conventional prior or satisfy global-convergence conditions, the paper analyzes fixed-point convergence instead. Under bounded-denoiser and bounded-gradient assumptions, the proposed continuation scheme converges to a fixed point.

  • Classical global convergence requires a closed, proper, convex prior, while general Plug-and-Play denoisers lack known convergence guarantees.
  • Fixed-point convergence is used because the denoiser may be arbitrary and an associated prior g may not exist.This guarantees that the nonlinear algorithm enters a steady state asymptotically.
  • A bounded denoiser is asymptotically invariant, satisfying Dσ → I as σ → 0 and excluding trivial mappings such as Dσ(x) = 0.
  • Theorem 1 states that, under bounded gradients of f and any bounded denoiser, x(k), v(k), and u(k) converge to fixed limits.
  • The continuation scheme drives ρk → ∞, reducing the influence of inversion and denoising while ensuring x(k) → v(k).

D. Stopping Criteria

The stopping rule monitors successive changes in the primal, auxiliary, and dual variables, with tolerance-based termination for practical reconstruction. Experiments indicate that tol ≈10^-3 is often sufficient, while parameter initialization has differing effects on stability and final PSNR.

  • The algorithm terminates when successive changes in x, v, and u are sufficiently small relative to a tolerance level.An alternative aggregate criterion is also considered.
  • tol ≈10^-3 often preserves reconstruction quality because PSNR becomes steady below this threshold across image sizes.This behavior was observed on 10 image super-resolution tests.
  • For γ ∈ (1, 2) and ρ0 ∈ (10^-5, 10^-2), tol ≈10^-3 is usually valid unless γ is close to 1 and ρ0 is extremely small.
  • The proposed monotone and adaptive update rules are more robust to ρ0 than the original constant-ρ Plug-and-Play ADMM.The original method requires a highly precise ρ0, whereas the proposed method works over a wider range.
  • Random initial guesses have little effect on limiting PSNR, with a reported standard deviation of 0.0059 dB.Across 100 random initializations, PSNR stayed within ±0.0176 dB of its average at 99.7% probability.

A. Application 1: Image Super-resolution

The super-resolution application develops a closed-form solution for the difficult x-subproblem under uniform downsampling and circular convolution, replacing iterative conjugate-gradient computation.

  • Super-resolution uses a linear forward model combining an anti-aliasing convolution filter H with a binary sampling matrix S.
  • When G = SH, the matrix H^T S^T S H is generally neither diagonal nor Fourier-diagonalizable, making the f-subproblem nontrivial.
  • Polyphase implementation: Under standard K-fold downsampling and circular convolution, polyphase decomposition reduces the relevant system to a finite impulse response filter.
  • Polyphase implementation: Proposition 1 states that S H H^T S^T is equivalent to applying the 0th polyphase component of H H^T as a finite impulse response filter.
  • Polyphase implementation: The resulting subproblem can be implemented in closed form using the Fourier transform rather than an inner iterative solver.
  • The closed-form solution is exact under periodic boundary conditions; nonperiodic boundaries require alternative solutions or circular padding followed by cropping.

C. Application 2: Single Photon Imaging

The single-photon imaging application models binary thresholded photon detections and exploits separability to solve each image variable independently through an efficient one-dimensional procedure.

  • A quanta image sensor uses K tiny single-photon detectors, or jots, to acquire light corresponding to each conventional image pixel.
  • Photon arrivals at each jot follow a Poisson distribution, and the sensor outputs a binary bit by thresholding the photon count at q.
  • For q = 1, the observation probabilities are e^-s_i when y_i = 0 and 1 − e^-s_i when y_i = 1.
  • The recovery objective estimates x from the observed binary bits y using the summed negative log-likelihood.
  • Because the f-subproblem is separable, each x_j is solved independently as a one-dimensional root-finding problem.
  • An offline lookup table indexed by K0, ρ, and e_xj enables efficient solution of the scalar optimization.

IV. EXPERIMENTAL RESULTS

The experiments use BM3D consistently across all evaluations and do not compare Plug-and-Play ADMM across different denoisers.

  • BM3D is used in all experiments, while comparisons among different denoisers are explicitly outside the paper’s focus.

A. Image Super-Resolution

The super-resolution experiments evaluate Plug-and-Play ADMM against several methods across multiple configurations, including Gaussian-filter settings where model mismatch affects competing algorithms. The proposed method generally performs competitively or better, with visual results showing sharper edges and fewer halo artifacts.

  • Experimental setup: The experiments use 10 grayscale test images sized 256 × 256 to 512 × 512 across four configurations.Four experimental configuration sets are studied, with results reported in Table I.
  • Experimental setup: The comparison includes DCNN, SPSR, TSE, GPR, and other existing super-resolution methods, with some relying on external training databases.TSE and GPR are single-image methods, whereas DCNN, SPSR, and SR require external training data.
  • Model assumptions: For Gaussian anti-aliasing configurations, Ours-M uses the correct filter while Ours-M* reconstructs under a bicubic-model assumption.This distinction addresses competing implementations that support only the bicubic model.
  • Quantitative results: The proposed method performs best overall in configurations 1 and 2, while Ours-M shows a significant advantage in configurations 3 and 4 under the correct Gaussian-filter model.With the bicubic assumption, Ours-M* remains better than the other methods for configuration 3 but is slightly worse than GPR for configuration 4.
  • Visual results: In the color experiment, the proposed method produces sharper edges and fewer halo artifacts than SPSR, TSE, and GPR, while DCNN performs better than in Table II.The authors attribute DCNN’s stronger visual result as a possibility to training data correlations with the test image.
  • Single-photon imaging: For single-photon imaging, the evaluation averages eight independent trials over 10 images, and the proposed color reconstruction shows less visual noise.The experiment processes the three color channels individually and reports average and standard deviation values.

APPENDIX A COUNTER EXAMPLE OF NON-EXPANSIVE DENOISER

The appendix constructs a counterexample showing that non-local means can be expansive rather than non-expansive. Its input-dependent weighting makes the denoising operator nonlinear, producing κ = 1.1775.

  • Counterexample construction: The appendix tests whether non-local means satisfies the non-expansiveness requirement by seeking an image pair with κ > 1.The pair can be obtained from an inpainting problem using constant ρ, although its construction method is not essential.
  • Operator construction: Non-local means is represented as a weighted average whose weights depend on image patches and are normalized into a doubly stochastic matrix.Sinkhorn-Knopp is applied to enforce the doubly stochastic property.
  • Result: κ = 1.1775 demonstrates that the non-local-means operator violates non-expansiveness for the constructed pair.The violation occurs because the weighting operators differ for distinct inputs, making the mapping nonlinear.
  • Implication for the algorithm: The proposed Plug-and-Play ADMM addresses this expansive behavior by forcing ρ →∞, which drives σ →0.The continuation scheme reduces the influence of inversion and denoising as ρ grows.

APPENDIX B PROOF OF THEOREM 1

The proof establishes convergence of the continuation-based Plug-and-Play ADMM by showing that its iterate sequence is Cauchy under all possible parameter-update patterns. The iterates therefore converge to a fixed point in the complete space R3n.

  • Proof setup: The proof represents each iteration by the triplet θ(k) = (x(k), v(k), u(k)) and equips its domain with a distance function D.Convergence is analyzed through distances between successive triplets.
  • Convergence conclusion: Because R3n is complete, the Cauchy sequence converges to θ∗ = (x∗, v∗, u∗).Consequently, x(k), v(k), and u(k) each converge in Euclidean norm.
  • Update cases: The parameter update has two cases: either ρ is increased when the distance condition fails, or ρ remains fixed when Δk+1 ≤ηΔk.The proof separately analyzes the consequences of both update cases.
  • Case analysis: All asymptotic behaviors reduce to three situations describing whether the two update cases occur infinitely or finitely often.The sequence is shown to converge under each of these situations.
  • Cauchy property: The successive-iterate distances satisfy bounds that establish {θ(k)} as a Cauchy sequence under the analyzed cases.The proof derives the needed bounds using lemmas and first-order optimality relations.
  • Convergence condition: The contraction-related bounds use γ > 1 to obtain the desired result for the continuation update.This condition appears in the final bound used by the proof.
Loading 1605.01710v2…