Recovery Analysis for Plug-and-Play Priors using the Restricted Eigenvalue Condition
Authors: Jiaming Liu
Salman Asif
Brendt Wohlberg
Ulugbek Kamilov
Venue: NeurIPS 2021 Poster (2021)
Keywords: inverse problems
compressive sensing
plug-and-play priors
regularization by denoising

Abstract: The plug-and-play priors (PnP) and regularization by denoising (RED) methods have become widely used for solving inverse problems by leveraging pre-trained deep denoisers as image priors.  While the empirical imaging performance and the theoretical convergence properties of these algorithms have been widely investigated, their recovery properties have not previously been theoretically analyzed.  We address this gap by showing how to establish theoretical recovery guarantees for PnP/RED by assuming that the solution of these methods lies near the fixed-points of a deep neural network. We also present numerical results comparing the recovery performance of PnP/RED in compressive sensing against that of recent compressive sensing algorithms based on generative models. Our numerical results suggest that PnP with a pre-trained artifact removal network provides significantly better results compared to the existing state-of-the-art methods.

Recovery Analysis for Plug-and-Play Priors using the Restricted Eigenvalue Condition
Jiaming Liu
M. Salman Asif University of California, Riverside sasif@ece. ucr.edu
Washington University in St. Louis j jiaming. liu@wustl.edi
Brendt Wohlberg
Ulugbek S. Kamilov
Los Alamos National Laboratory brendt@ieee.c .rg
Washington University in St. Louis kamilov@vustl.ed
Abstract
The plug-and-play priors (PnP) and regularization by denoising (RED) methods have become widely used for solving inverse problems by leveraging pre-traing trained deep denoisers as image priors. While the empirical imaging performance and the theoretical convergence properties of these algorithms have been widely investi- gated, their recovery properties have not previously been theoretically analyzed. We address this gap by showing how to establish theoretical recovery guarantees for PnP/RED by assuming that the solution of these methods lies near the fixed- points of a deep neural network. We also present numerical results comparing the recovery performance of PnP/RED in compressive sensing against that of recent compressive sensing algorithms based generative models. Our numerical results suggest that PnP with a pre-trained artifact removal network provides significantly better results compared to the existing state-of-the-att methods.
Introduction
Many imaging problems- such as denoising, inpainting, and super-resolution can be formulated as an inverse problem involving the recovery of an image E IR" from noisy measurements
Ax" +e,
(1)
where A R is the measurement operator and e RT is the noise. Compressed sensing (CS) [1,2] is a related class inverse problems that seek to recover a sparse vector x from m < n measurements. The sparse recovery is possible under certain assumptions on the measurement matrix, such as the restricted isometry property (RIP) [1] or the restricted eigenvalue condition (REC) []. While traditional CS recovery relies on sparsity-promoting priors, recent work compressed sensing using generative models (CSGM) [5] has broadened this perspective to priors specified through pre-trained generative models. CSGM has prompted large amount of follow-up work on the design and theoretical analysis of algorithms that can leverage generative models as priors for image recovery [6-9]. Plug-and aad--aad priors (PnP) [10, 11] and regularization by denoising (RED) [12] are two methods related to CSGM that can also leverage pre-trained deep models priors for inverse problems. However, unlike CSGM, the regularization in PnP/RED is not based on restricting the solution to the range of generative model, but rather denoising the iterates with existing additive white Gaussian noise (AWGN) removal method. The effectiveness of PnP/RED has been shown in a number of inverse problems [13-18], which has prompted researchers investigate the theoretical properties and interpretations of PoP/RED algorithms [19-30].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Despite the rich literature on both PnP/RED and CSGM, the conceptual relationship between these two classes of methods has never been formally investigated. In particular, while PnP/RED algorithms enjoy computational advantages over CSGM by not requiring nonconvex projections onto the range of generative model, they lack theoretical recovery guarantees available for CSGM. In this paper, we address this gap by presenting the first recovery analysis of PnP/RED under the assumptions of CSGM. We show that if a measurement matrix satisfies a variant of REC from [5] over the range of a denoiser, then the distance of the PnP solutions to the true x" can be explicitly characterized. We also present conditions under which the solutions of both PnP and RED coincide, providing sufficient conditions for the exact recovery of x using both methodologies. Our results highlight that the regularization in PnP/RED is achieved by giving preference to images near the fixed points of pre-trained deep neural networks. Besides new theory, this paper also presents numerical results directly comparing the recovery performance of PnP/RED against the recent algorithms in compressed sensing from random projections and subsampled Fourier measurements. These numerical results lead to new insights highlighting the excellent recovery performance of both PnP and RED, as well as the benefit of using priors specified pre-trained artifact removal (AR) operators rather than AWGN denoisers.
All proofs and some technical details that have been omitted for space appear in the Supplement, which also provides more background and simulations. The code for our numerical evaluation is available at: https://ga /githbb. com http//uslllccc
2 Background
Inverse problems. A common approach to estimating x' in (1) is to solve an optimization problem:
1 min g(x) + h(x) with g(x) = 2 - A
(2)
#Ek
where is data-fidelity term that quantifies consistency with the observed data and h is a regularizer that encodes prior knowledge on æ. For example, a widely-used regularizer in inverse problems is the nonsmooth total variation (TV) function h(x)) = Dzlli where D is the gradient operator and 7 > 0 is the regularization parameter [31-33].
Compressed sensing using generative models. Generative priors have recently become popular for solving inverse problems [5], which typically require solving the optimization problem:
min EER
- fly AW())
(3)
where W : 12 + Im(W) C RT is a pre-trained generative model, such as StyleGAN-2 [34, 35]. The set Im (m( is the image set (or the range set) of the generator W. In the past few years, several algorithms have been proposed for solving this optimization problem [6-9], including the recent algorithms PULSE [36] and intermediate layer optimization (IL.)) [37] that can recover highly- realistic images. The recovery analysis of CSGM was performed under the assumption that A satisfies the set-restricted eigenvalue condition (S-REC) [5] over the range of the generative model:
A
A=
μ|| x =1:3 77 Vx, Im(W).
(4)
where y > 0 and v) 2 O. S-REC implies that the pairwise distances between vectors in the range of the generative model must be well preserved in the measurement space. It thus broadens the traditional notions of REC and the restricted isometry property (RIP) in CS beyond sparse vectors [38].
PnP and RED. PnP [10, 11] refers to family of iterative algorithms that are based replacing the proximal operator prox.,, of the regularizer h within a proximal algorithm [39] by a more general denoiser D R + Im) C IR"", such as BM3D [40] or DnCNN [41]. For example, the widely used proximal gradient method (PGM) [42 45] can be implemented
PnP algorithm as [46]
x² (11=11) with T D(I Vg)
where g is the data fide-fidelity term in (2), I denotes the identity mapping. and 7 > 0 is the step size. Remarkably, this heuristic of using denoisers not associated with any within a proximal algorithm exhibited great empirical success [13-18] and spurred great deal of theoretical work on PnP [19-28]. In particular, has been recently shown in [23] that, when the residual of Lipschitz continuous, PnP-PGM converges to point in the fixed-point set of the operator T that we denote Fix(T).
2

---

RED [12] is a related method, inspired by PnP, for integrating denoisers as priors for inverse problems. For example, the steepest descent variant of RED (SD-RED) [12] can be summarized as
c k- - -G(x"=1 with G = Vg + DD).
(6)
where 7 > 0 is the step size and 7 > 0 is the regularization parameter. For a locally homogeneous D that has a strongly passive and symmetrie Jacobian, the solution of RED solves (2) with h(xx) =
(T/2) (x D(x)) [12,22], Subsequent work has resulted in a number of extensions of RED [29, (0,47-49]. For example, it has been shown in [29] that, when D is nonexpansive operator, SD-RED converges to a point in the zero set of operator G that we denote as Zer(G).
Other related work. While not directly related to our main theoretical contributions, it is worth briefly mentioning other important related families of algorithms that also use deep neural nets for regularizing ill- ill-posed imaging inverse problems (see recent reviews of the area [50-53]). This work is most related to methods that rely on pre-trained priors that are integrated within iterative algorithms, such class of algorithms in compressive sensing known approximate message passing (AMP) [54-57]. Another related family of algorithms are those based on the idea of deep unrolling (for overview see Section IV-A in [53]). Inspired by LISTA [58], the unrolling algorithms interpret iterations of a regularized inversion as layers of a CNN and train it end-to-end in a supervised fashion 559-64). Deep image prior [65] and deep decoder [66] also use neural networks prior for images; instead of using a pre-trained generative network, they learn the parameters of the network while solving the inverse problem using the available measurements.
3 Recovery Analysis for PnP and RED
We present two sets of theoretical results for PnP-PGM (5) using the measurement model (1) and the least-squares data-fidelity term (2). We first establish recovery bounds for PnP under a set of sufficient conditions, and then address the relationship between the solutions of PnP and RED. The proofs of all the theorems will be provided in the Supplement. We start by discussing two assumptions that serve as sufficient conditions for our analysis of PnP.
Assumption 1. The residual R == 1- D of the operator D is bounded by 8 and Lipschitz continuous with constant 0, which can be written as
R[xx) S 8 and [[R(x) - (R()))R(z)]le S a||x 2112, Vz, Z E RR
(7)
The rationale for stating Assumption in terms of the residual based on our interest in residual deep neural nets that take noisy or an artifact-corrupted image at the input and produce the corresponding noise or artifacts at the output. The success of residual learning in the context of image restoration is well known [41]. Prior work has also shown that Lipschitz constrained residual networks yield excellent performance without sacrificing stable convergence [23,29].
Related assumptions have been used in earlier convergence results for PnP [19,23], For example, one of the most-widelyy known PnP convergence results relies on the boundedness of D [19]. The Lipschitz continuity of the residual R has been used in the recent analysis of several PnP algorithms in [23]. Both of these assumptions are relatively easy to implement for deep priors. For example, the boundedness of R can be enforced by simply bounding each output pixel to be within [0, v) for images in [0, 2/ R for some > O. The Lipsshhii continuity of R can be enforced by using any of the recent techniques for training Lipschitz constrained deep neural nets 23.67769). Fig. 1 presents an empirical evaluation of the Lipschitz continuity of R used in our simulations.
Assumption 2. The measurement operator A E mm=x satisfies the set-restricted eigenvalue condi- tion (S-REC) over lm(D) C IR" with > O, which can be written as
Ax Azl 2 /a| - 2112. Var z E Im(D)
(8)
S-REC in Assumption was adopted from the corresponding assumption for CSGM stated in (4), which establishes a natural conceptual link between those two classes of methods. The main limitation of Assumption 2, which is also present in the traditional RIP/REC assumptions for compressive sensing, lies in the difficulty of verifying it for given measurement operator A. There has been significant activity in investigating the validity of related conditions for randomized matrices for different classes of signals [4, [4.70-72), including for those synthesized by generative models [5,6,9377].
3

---

max
max
max
# samples
0.95
(a)
(b)
(c)
(d)
Figure 1: Empirical evaluation of the Lipschitz continuity of and D used in our simulations and stated in Assumptions and 3. As described in the main text, we trained two rypes of Lipschitz constrained networks, where the first simply denoises AWGN and the second removes artifacts
specific to the PnP iterations. (a) and (b) show the histograms of [|R(x) R(z R(z)|l2/|[== - = for the denoiser and the artifact-rmooaa operator, respectively. (c) and (d) show the histograms of [ID(x:) - D(z))ll/|{az despite the fact that Lipschitz continuity was only imposed on the residual during training.
z||2 for the same two operators. Note the empirical nonexpansiveness of D
Despite this limitation, Assumption 2 still conceptually useful as it allows us to relax the strong convexity assumption used in the convergence analysis in [23] by stating that it is sufficient for the strong convexity hold only over the image set Im) rather than over the whole IR... This suggests new research direction for PnP on designing deep priors with range spaces restricted to satisfy S-REC for some A. In the Supplement, we present an empirical evaluation of μ for the measurement operators used in our experiments by sampling from Im(D).
Consider the set Fix(D) == {ar R x D(a=)} of the fixed points of D. Note that Fix(D) is equivalent to the set (R) = { E TR R(x) = 0} of the zeros of the residual R = 1 D. Intuitively, Zer(R) consists of all images that produce no residuals, and therefore can be interpreted as the set of all noise-free images according to the network. Similarly, when R is trained to predict artifacts in an image, Zer(R) is the set of images that are artifact-free according to R. In the subsequent analysis, we use the notation (R), but these results can be equivalently stated using Fix(D).
We first state the PnP recovery in the setting where there is noise and x Zer(R).
Theorem 1. Run PnP-PGM for t 2 1 iterations under Assumptions 1-2 for the problem (1) with no noise and x= Zer( Then, the sequence x² generated by PnP-PGM satisfies
|| x=1|2 1|2 S c|lx'~1 x=1l2 S c¹ 1x x x²|12.
where x: E Im(D) and e = (1 + a) max {|1 7/44, - >11 with = Amax (ATA) A).
The proof of the theorem is available in the Supplement. Theorem I extends the theoretical analysis the true solution x" of (1) instead of the fixed points Fix(T) of T in (5). The condition x" E lm(D) can be easily enforced by simply passing any initial
of PnP in [23] by showing convergence
image through the operator D. One does not necessarily need 1, for the convergence result in Theorem 1. As shown in [23], the coefficient c in Theorem 1 is less than one if
2 p(1 1/a)) < <>< A x(1+1/a)
1
1
(10)
which is possible if a 2p/(A- μ1). Since all PnP algorithms have the same fixed points [20, 200, our result implies that PnP can exactly recover the true solution x" to the inverse problem, which extends the existing theory in the literature that only shows convergence Fix(T).
We now present more general result that relaxes the assumptions in Theorem
Theorem 2. Run PnP-PGM for t 2 1 iterations under Assumptions 1-2 for the problem (1) with x² E R. and E RT Then, the sequence x' generated by PnP-PGM satisfies
| -- x S cllxt-11 x x=112 + S <c'll=" x²122 + s(1
(11)
(1 (1-c) c)
where x0 E lD) and
= c) [11 (1 1/+22//// 1/11 projzer(R)) (2=") )l12 2/ 5(1 + 1/a))
(12)
and c (1+ a max[11 744, } with A = Amax A (ATA).

---

Theorem 2 extends Theorem 1 by allowing x" to be outside of Zer(R) and extends the analysis in [5] by considering operators that do not necessarily project onto the range of generative model. In the error bound e, the first two terms are the distance of x to Zer(R) (R) and the magnitude of the error e, and have direct analogs in standard compressed sensing. The third term is the consequence of the possibility for the solution of PnP not being in the zero-set of R and one can show that when Zer(R) n Zer( (Vg) + Ø, then the third term disappears. As reported in the Supplement, we empirically verified that the distance of the PnP solution to Zer(R) is small for both the denoiser and the artifact- removal operators used in our experiments.
Our final result explicitly relates the solutions of PnP and RED. In order to obtain the result, we need an additional assumption that the denoiser D R is nonexpansive.
Assumption 3.
The denoiser nonexpansive
[D(x)) D(2)ll2 S | 2||2,
Vx, Z E IR"
This is related but different from Assumption 1 that assumes the residual R a-Lipschitz continuous.
The convergence of SD-RED in (6) to Zer(G) can be established for a nonexpansive operator D [29]. In principle, the nonexpansiveness of D can be enforced during the training of the prior in the same manner as that of the more general Lipschitz continuity. However, the prior in our numerical evaluations is trained to have a contractive residual R without any explicit constraints on D. As a reminder, the nonexpansiveness of is only a necessary (but not sufficient) condition for the nonexpansiveness of D [73]. Despite this fact, our empirical evaluation of the Lipschitz constant of D in Fig. indicates that D used in our experiments is nonexpansive.
Theorem 3. Suppose that Assumptions 1-3 are satisfied and that Zer(Vg) n Zer(R) o Ø0, then PnP and RED have the same set of solutions: Fix Zer(G).
As a reminder, the solutions of PnP correspond to the fixed-points of the operator T defined in (5), while those of RED to the zeroes of the operator G defined in (6). The assumption that Zer(Vg) n Zer(R) # Ø implies that there exist vectors that are noise/artifact free according to R and consistent with the measurements y. While this assumption not universally applicable to all the inverse problems and priors, it still provides a highly-intuitiv sufficient condition for the PnP/RED equivalence. Although the relationship between PnP and RED has been explored in the prior work [22, 30], to the best of our knowledge, Theorem 3 is the first to prove explicit equivalence. If one additionally considers PnP-PGM with step size that satisfies the condition in (10), then is contraction over lD), which implies that PnP-PGM converges linearly to its unique fixed point in (D) The direct corollary of our analysis that, in the noiseless scenario y = Ax. with xx E Zer(R)) the image xt is the unique fixed point of both PnP and RED over lm()).
worth mentioning that several of our assumptions have been stated in way that simplifies mathematical exposition, but can alternatively be presented in a significantly weaker form. For example, the boundedness assumption in (I)-which is used only in the proof of Theorem 2-does not have to hold everywhere, but only at the fixed points of PnP. Indeed, as can be seen in eq. (6) of the Supplement, the constant is only used to bound the norm of the residual at the fixed-point of PnP-PGM. Similarly, we do not need the nonexpansiveness of D in Assumption 3 to be true everywhere, but only at the fixed points RED-SD (see page of the Supplement).
In summary, our theoretical analysis reveals that the fixed-point convergence of PnP/RED algorithms can be strengthened to provide recovery guarantees when S-REC from CSGM is satisfied. Since PnP/RED algorithms do not require nonconvex projections onto the range of generative model, they enjoy computational benefits over methods that use generative models as priors. However, the literature on generative models is rich with theoretical bounds and recovery guarantees compared to that of PnP/RED. We believe that our work suggests an exciting new direction of research for PnP/RED by showing that a similar analysis can be carried out for PnP/RED.
4 Numerical Evaluation
Before presenting our numerical results, it is important to note that PnP and RED are well-known methods and not our aim to claim any algorithmic novelty with respect to them. However, comparing PnP/RED to state-of-the-art compressed sensing (CS) algorithms is of interest in the
5

---

x11
35.52 dB
35.01
35.06 dB
PSNR (dB)
8
1.129x10
1.127x
1.112x10'
2000
4000
1200
2400
1200
2400
(a) RED (denoising)
(b) PnP (denoising)
(c) PnP (AR)
Empirical evaluation of the convergence of PnP/RED the true solution x" using denoiser and an artifact removal (AR) operator. Average normalized distance and PSNR relative to the true solution x" are plotted with the shaded areus representing the range of values altained over all test images. Note the similar recovery performance of PnP and RED, as well as the improvement in performance due to a prior trained remove artifacts specific to PnP iterations (rather than AWGN denoiser).
Figure 2:
Table I: Numerical evaluation of the CS recovery in terms of PSNR (dB) on BSD68 and Set1
CS Ratio
BSD68
Set11
Method
10%
30%
40%
50%
10%
30%
40%
50%
TV
24.56
28.61
30.27
31.98
24.47
30.21
32,29
34.27
SDA [76]
23.12
26.38
27.41
28.35
22.65
26.63
27.79
28.95
ReconNet [77]
24.15
27.53
29.08
29.86
24.28
28.74
30.58
31.50
ISTA-Net [62]
25,02
29.93
31.85
33.61
25.80
32.91
35.36
37.43
ISTA-Net* [62]
25.33
30.34
32.21
34.01
26.64
33.82
36.06
38.07
RED (denoising)
24.97
30.20
32.25
34.39
27.70
35.01
37.28
39.26
PnP (denoising)
25.06
30.31
32.29
34.35
27.76
35.06
37.30
39.21
PuP (AR)
26.46
31.33
33.18
34.92
28.98
35.53
37.34
39.29
context of our theory. Our goal in this section is thus to both (a) empirically evaluate the recovery performance of PuP/RED and (b) compare their performances relative widely-used CS algorithms.
We consider two scenarios: (a) CS using random projections and (b) CS for magnetic resonance imaging (CS-MRI). In order gain deeper insights into performance under subsampling, idealized noise-free setting; however, we expect similar relative performances under noise. For each scenario, include comparisons with several well-established methods based on deep learning.
consider two priors for PnP/RED: (i) an AWGN denoiser and (ii) an artifuct-removal (AR) operator trained to remove artifacts specific the PnP iterations. We implement both priors' using the DnCNN architecture [41], with its batch normalization layers removed for controlling the Lipschitz constant of the network via spectral normalization [68]. We train the denoiser
nonexpansive residual network that predicts the noise residual from a noisy input image. Thus, R satisfies the necessary condition for the nonexpansiveness of D. Similar [74], we train the AR prior by including it into deep unfolding architecture that performs PnP iterations. When equipped with spectral normalization [68], the residual R of the AR operator still satisfies Lipschitz continuity assumptions and achieves superior performance compared to the denoiser (as corroborated by our results). Our implementation also relies on the scaling strategy from [75] for controlling the influence of D relative g. The reconstruction quality is quantified using the peak signal-to-noise ratio (PSNR) in dB.
4.1 Reconstruction of Natural Images from Random Projections
We adopt a simulation setup widely-used in the CS literature, in which non-overlapping 33 x 33 patches of image measured using the have been orthogonalized [62, 77]. The patches are vectorized to n = 1089-Iength vectors x²" The training data for the denoiser is generated by adding AWGN the images from the BSD500 [78] and
random Gaussian matrix A, whose rows
For additional details and code see the Supplement and the GitHub repository.

---

Ground truth
TV
ISTA-Net+
RED (denoising)
PnP (denoising)
PnP (AR)
23.17
25.72
26.87
26.92
Ground truth
TV
ISTA-Net+
RED (denoising)
PnP (denoising)
PnP (AR)
Figure 3: Visual evaluation of various compressive sensing algorithms at 10% sampling on two imaging problems: (top) reconstruction of Butterfly from Seill; (bottom) reconstruction of a brain MR image from its radial Fourier measurements. The pink box in the bottom image provides the error residual that was amplified by 10x for better visualization. Nole the similar performance of PnP and RED, as well as the competitiveness of both relative to other methods. Additionally, note the improvement due the usage of AR prior instead of an AWGN denoiser within PnP.
Table 2: Average PSNR values for various CS-MRI methods on test images from [62].
CS Ratio
10%
20%
30%
40%
50% %
Method
TV
31.36
35.62
38.41
40.43
42.20
ADMM--Nt [61]
34.19
37.17
39.84
41.56
43.00
ISTA-Net [62]
34,65
38.70
40.97
42.65
44.12
RED (denoising)
34.37
38.63
40.94
42.62
44.21
PnP (denoising)
34.56
38.74
41.06
42.73
44.24
PnP (AR)
35,21
39.05
41.28
42.96
44.47
DIV2K datasets [79]. We pre-train several deep models as denoisers for a E [1, 15), using a intervals of 0.5, and use the denoiser achieving the best PSNR value in each experiment. We use the of 91 images as in [77] to train the AR operators that are implemented on individual image patches at time for the CS ratios (m/n)) of (10%, 30%, 40%, 50%]. In order overcome the block-artifacts in the recovered images, we implement PnP and RED regularizers over the entire image while still using the per-patch measurement model for Vg.
Our first numerical study in Fig. I evaluates the Lipschitz continuity of our preitrained denoisers and the AR operators by following the procedure in [23]. We the residual R and its corresponding operator D =
and plot the histograms of a1 = |[(x)) R(z) ||2/| æ z and a2 = [D(x)) D(z))12/||2
z|12 over 1160 AWGN corrupted image pairs extracted from BSD68. The maximum value of each histogram is indicated by a vertical bar, providing an empirical bound on the Lipschitz constants. Fig. confirms empirically that both R and D contractive operators.
Theorem establishes that the sequence of iterates x' generated by PnP-PGM converges to the true solutions x² up | x ||/|[<**] [ and peak signal-to-noiss ratio (PSNR) for CS with subsampling ratio 30% on Setll. The shaded areas represent the range of values attained across all test images. The results in Fig. 2 are consistent with our general observation that the PnP/RED algorithms converge in all our experiments for both types of priors and achieve excellent recovery performance.
term. Fig. 2 illustrates the convergence behavior of PnP/RED in terms of
also report the average PSNR values obtained by five baseline CS algorithms, namely TV [33], SDA [76]. ReconNet [77], ISTA-Net [62] and ISTA-Net+ [62]. TV is an iterative methods that does not require training, while the other four are deep learning- methods that have publicly available implementations, The numerical results Setll and BSD68 with respect to four measure-
7

---

Ground truth
PULSE
ILO
Ground truth
PULSE
ILO
E
E
68
24.87
26.20
40.40
RED (denoising)
PnP (denoising)
PnP (AR)
RED (denoising)
PnP (denoising)
PnP (AR)
E
E
Figure 4: Visual evaluation of PnP/RED and two methods using generative models priors the CelebA HQ [82] dataset at 10% CS sampling. Note the visual and quantitative similarity of PuP and RED when both are using AWGN denoisers. PnP using visually matches the performance of ILO based on StyleGAN2, which highlights the benefit of using pre-trained AR operators within PnP. Best viewed by zooming in the display.
artifact-remove (AR) prior
Table 3: Average PSNR (dB) values for several algorithms on images from CelebA HQ
CS Ratio
10%
20%
30%
40%
50%
Method
TV
32.13
35.24
37.41
39.35
41.29
PULSE [36]
27.45
29.98
33.06
34.25
34.77
ILO [37]
36.15
40.98
43.46
47.89
48.21
RED (denoising)
35.46
41.59
45.65
48.13
52.17
PnP (denoising)
35.61
41.51
45.71
48.05
52.24
PnP (AR)
39.19
44.20
48.66
51.32
53.89
ment rates are summarized in Table 1. We observe that the performances of PnP and RED are nearly identical to one another. The result also highlights that PnP using the AR prior provides the best performance" compared to all the other methods, outperforming PnP using the AWGN denoiser by at least 0.57 dB on BSD68. Fig. (top) shows visual examples for image from Setl 1. Note that both PnP and RED yield similar visual recovery performance. The enlarged regions in the image suggest that PnP (AR) better recovers the fine details and sharper edges compared other methods.
4.2 Image reconstruction in Compressed Sensing MRI
MRI is a widely-used medical imaging technology that has known limitations due to the low speed of data acquisition. CS-MRI [80, 81] seeks to recover image x" from its sparsely-sanpled Fourier measurements. We simulate a single-coil CS CS-MRI using radial Fourier sampling. The measurement operator A is thus A PF, where P is the diagonal sampling matrix and F is the Fourier transform.
The priors PnP/RED were trained using the brain dataset from [62], where the test set contains 50 slices of 256 x 256 images (i.e., = 65536). We train seven variants of DrCNN, each using separate noise level from a E (1, 1.5, 5, 2, 2,5, 3,4,5, 4,5.. Similarly, we separately train the AR operators for different CS ratios (m/n), initializing the weights of the models from the pre-trained denoiser with a 2. For these sets of experiments, we also equipped PnP/RED with Nesterov acceleration [83] for faster convergence. We compare PnP/RED against publicly available implementations of several well-known methods, including
[33], ADMM-Net [61], and ISTA-Net* [62]. The last two are deep unrolling methods that train both image transforms and shrinkage functions within the algorithm.
Table 2 reports the results for five CS ratios. The visual comparison can be found Fig. (bottom). It can been seen that PnP/RED with AWGN denoiser matches the performance of ISTA-Net*
We did RED with the AR prior experiments since is expected closely match PnP.

---

and outperforms ADMM-Net at higher sampling ratios, while PnP with an AR prior improves over PnP/RED with an AWGN denoiser [84]. Note also the similarity of PnP and RED performances.
4.3 Comparison with generative models on human faces
We numerically evaluated the recovery performance of PnP/RED in CS against two recent algorithms using generative models: PULSE [36] and ILO [37]. Similar to the measurement matrix used for grayscale images, we use orthogonalized random Gaussian matrices for sampling image blocks of size 33 x 33 x 3. The test images correspond to 15 images randomly selected from CelebA HQ [82] dataset, each of size 1024 1024 pixels. We use the DIV2K [79] and 200 high quality face images from FFHQ dataset [34] to train the PnP/RED denoisers for color image denoising at six noise levels corresponding to a 2, 7, 10). We use the same training set to train the AR operators for CS ratios of [10%, 50%]. using the ratio intervals of 10%. Similar to CS-MRI, we equipped PnP/RED with Nesterov acceleration. The PSNR comparison between different methods is presented in Table 3. It can be seen that ILO outperforms PULSE in terms of PSNR, which is consistent with the results in [37]. Note also how PnP/RED match or sometimes quantitively outperform ILO at high CS ratios, with PnP (AR) leading significantly better results compared to PnP (denoising). Fig. 4 provides visual reconstruction examples. Note the ILO images are sharper compared to PnP/RED with denoisers because ILO uses
art generative model specifically trained on face images. However, PnP (AR) achieves better PSNR and a similar visual quality as ILO.
5 Conclusion and Future Work
The main goal of this work is to address the theoretical gap between two-widely used classes of methods for solving inverse problems, namely PnP/RED and CSGM. Motivated by the theoretical analysis of CSGM, we used S-REC to establish recovery guarantees for PnP/RED. Our theoretical results provide a new type of convergence for PnP-PGM that goes beyond simple fixed-point convergence by showing convergence relative to the true solution. Additionally, we show the full equivalence of PnP and RED under some explicit conditions on the inverse problem. While the focus of this work is mainly theoretical, we presented several numerical evaluations that can provide additional insights into PnP/RED and their performance relative to standard methods used in compressed sensing. Empirically, we observed the similarity of PnP/RED in image reconstruction from subsampled random projections and Fourier transform. We also provided additional evidence on the suboptimality of AWGN denoisers compared to artifact-removai operators that take into account the actual artifacts within PnP iterates.
The work presented in this paper has certain number of limitations and possible directions for improvement. The main limitation of our theoretical analysis, which is common to all compressive sensing research, is in the difficulty of theoretically verifying S-REC for given measurement operator. One can also consider the Lipschitz assumptions on R/D as limitation, since those can have negative impact on the recovery. However, our results suggest that even with Lipschitz constrained priors, PnP/RED are competitive with widely-known CS algorithms. While PnP/RED can be implemented using noa-Lisschizzccnstriimme and ultimately hurt their recovery performances. A relatively minor limitation of our simulations is that they were performed without AWGN. One can casily re-run code by including AWGN and we expect that the relative performances will be preserved for a reasonable amount of noise. We hope that this work will inspire further theoretical and algorithmic research PnP/RED that will lead to extensions and improvements to our results.
priors, we expect that this will reduce their stability
6 Broader impact
This work is expected to impact the area of imaging inverse problems with potential applications to computational microscopy, computerized tomography, medical imaging, and image restoration. There is growing need in imaging to deal with noisy and incomplete measurements by integrating multiple information sources, including physical information describing the imaging instrument and learned information characterizing the statistical distribution of the desired image. The ability to accurately solve inverse problems has the potential to enable new technological advances for imaging. These advances might lead to new imaging tools for diagnosing health conditions, understanding
9

---

biological processes, or inferring properties of complex materials. Traditionally, imaging relied on linear models and fixed transforms (filtered back projection, wavelet transform) that are relatively straightforward to understand. Learning based methods, including PnP and RED, have the potential to enable new technological capabilities; yet, they also come with downside of being much more complex. Their usage might thus lead to unexpected outcomes and surprising results when used by non-experts. While we aim to use our method to enable positive contributions to humanity, one can also imagine nonethical usage of imaging technology. This work focuses on understanding theoretical properties of imaging algorithms using learned priors, but it might be adopted within broader data science, which might lead to broader impacts that we have not anticipated.
Acknowledgments and Disclosure of Funding
Research presented in this article was supported by NSF awards CCF- CCF-2043134, and CCF-2046293 and by the Laboratory Directed Research and Development program of Los Alamos National Laboratory under project number 2020006IDR,
References
[1] E. J. Candès, J. Romberg, and T. Tao, "Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information." IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489-509, Fehruary 2006.
[2] D. I.. Donoho, "Compressed sensing," IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1289-1306, April 2006.
[3] P. T. Bickel, R. Ya' acov, and T. B. Alexandre, "Simultaneous analysis of lasso and Danizig selector," Ann. Statist. vol. 37, no. 4, pp. 1705-1732, 2009.
[4] M. J. Wainwright, High- Righh-Dimessioal Statistics: A Non-Asymptotic Viewpeint, Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
[5] A. Bora, A. Jalal, E. Price, and A. G. Dimakis, "Compressed sensing using generative priors," in Proc. 34th Int, Conf. Machine Learning (ICML), Sydney, Australia, Aug. 2017. pp. 537-546.
[6] V. Shah and C. Hegde, "Solving linear inverse problems using GAN priors: An algorithm with provable guarantees." in Proc. IEEE Int. Conf. Acoustics, Speech and Signal Process., Calgary, AB, Canada, Apr. 2018. pp. 1609-4613.
[7] C. Hegde, "Algorithmic aspects of inverse problems using generative models," in Proc. Allerton Conf. Communication. Control, and Computing, Monticellu, IL. USA, Oct. 2018, pp. 166-172.
[8] F. Latorre, A. Eftekhari, and V. Cevher, "Fast and provable ADMM for learning with generative priors," in Advances in Neural Information Processing Systems 33, Vancouver, BC, USA, December 8-14, 2019, pp- 12027-12039.
[9] R. Hyder, V. Shah, C. Hegde, and M. S. Asif, "Altemattin phase projected gradient descent with generative priors for solving compressive phase retrieval." in Proc. IEEE Int. Conf. Acoustics, Speech and Signal P Process., Brighton, UK, May 2019, pp. 7705-7709.
[10] S. V. Venkatakrishnan, C. A. Bouman, and B. Wohlberg, "Plug-and-play priors for model based recon- struction," in Proc. IEEE Global Conf. Signal Process. and Inf. Process. (GlohalStP), Austin, TX, USA, December 3-5, 2013, pp. 945-948.
[11] S. Sreehari, S. V. Venkatakrishhan, B. Wohlberg, G. T. Buzzard, I. F. Drummy, J. P. Simmons, and C. A. Bouman, "Plug-and-play priors for bright field electron tomography and sparse interpolation." IEEF Trans. Comp. Imag., vol. 2, no. 4, pp. 408-423, December 2016.
[12] Y. Romano, M. Flad, and P. Milanfar, "The little engine that could: Regularization by denoising (RED)" SIAM J. Imaging Sci., vol. 10, no. 4, pp. 1804-1844, 2017.
[13] K. Zhang, W. Zuo, S. Gu, and L. Zhang, "Learning deep CNN denoiser prior for image restoration," in Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), Honolulu, HI, USA, July 2017, pp. 2808 2017-
[14] C. A. Metzler, P. Schniter, A. Vecraraghavan, and R. G. Baraniuk, "prDeep: Robust phase retrieval with flexible deep network," in Proc. 35th Int. Conf. Machine Learning (ICML), Stockholm, Sweden, June 2018, pp. 3501-3510.
[15] W. Dong, P. Wang. W. Yin, G. Shi, F. Wu, and X. Lu, "Denoising prior driven deep neural network for image restoration." IEEE Trans. Patt. Anol. and Machine Intell., vol. 41, no. 10, pp. 2305-22 2318, Oct. 2019.
10

---

[16] K. Zhang. W. Zuo, and L. Zhang. "Deep plug-and-play super-resolution for arbitrary blur kernels." in
Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), Long Beach, CA, USA, June 16-20. 2019. pp.
[17] R. Ahmad, C. A. Bouman, G. T. Buzzard, S. Chan, S. Liu, E. T. Reehorst, and P. Schniter, "Plug-and-play methods for magnetic resonance imaging: Using denoisers for image recovery." IEEE Signal Processing Magazine, vol. 37, no. 1. pp. 105 116, 2020.
[18] K. Wei, A. Aviles-Rivers J. Liang, Y. Fu. C.-B. Schönlieb, and H. Huang. "Tuning-free free plug-and -ndaay proximal algorithm for inverse imaging problems." in Proc. 37th Int. Conf. Machine Learning (ICML). 2020.
[19] S. H. Chan, X. Wang, and O. A. Elgendy, "Plug-and ADMM for image restoration: Fixed-poine convergence and applications." IEEE Trans. Comp. Imag. vol. 3, no. 1. pp. 84-98, March 2017.
[20] T. Meinhardt, M. Moeller, C. Hazirbas, and D. Cremers, "Learning proximal operators: Using denoising networks for regularizing inverse imaging problems," in Proc. IEEE Int. Conf. Comp. Vis. (ICCV), Venice Italy, Oct. 2017, pp. 1899-1808.
[21] G. T. Buzzard, S. H. Chan, S. Srechari, and C. A. Bouman, "Plug-and-plas unplugged: Optimization free reconstruction using consensus equilibrium." SIAM J. Imaging Sci., vol. 11, no. 3, pp. 2001-2020 2018.
[22] E. T. Reehorst and Schniter, "Regularization by denoising: Clarifications and new interpretations"" JEEE Trans. Comput. Imag. vol. 5, no. 1. pp. 52 67, Mar. 2019.
[23] E. K. Ryu, J. Liu. S. Wnag. X. Chen, Z. Wang. and W. Yin, "Plug-and-plac methods provably converge with properly trained denoisers," in Proc. 36th Int. Conf. Machine Learning (ICML). Long Beach, CA. USA, June 2019, pp. 5546-5557.
[24] Y. Sun, B. Wohlberg, and U. S. Kamilov, "An online play- algorithu for regularized image reconstruction," IEEE Trans. Comput. Imag., vol. 5, no. 3, pp. 395 408, Sept. 2019.
[25] T. Tirer and R. Giryes, "Image restoration by iterative denoising and backward projections." IEEE Trans. Image Process., vol. 28, no. 3. pp. 1220- 1220-1234, 2019.
[26] A. M. Teodoro, J. M. Bioucas-Diaa and M. A. T. Figueiredo, "A convergent image fusion algorithm using scenc-adapted maussian-mixturr-bassse denoising," IEEE Trans. Image Process., vol. 28, no. 1, pp. 551-463, Jan. 2019,
[27] X. Xu, Y. Sun, J. Liu, B. Wohlberg, and U. S. Kamilov, "Provable convergence of plug-and and-play priors with MMSE denoisers," IEEE Signal Process. Lett., vol. 27, pp. 1280- 1284, 2020.
[28] Y. Sun. Z. Wu, B. Wohlberg, and U. S. Kamilov, "Scalable glug-and-play ADMM with convergence guarantees." IEEE Trans. Comput. Imag., vol. pp. 849-863, July 2021.
[29] Y. Sun, J. Liu, and U. S. Kamilov, "Block coordinate regularization by denoising," in Proc. Advances in Neural Information Processing Systems 33, Vancouver, BC, Canada, Dec. 2019, pp. 382-392.
[30] R. Cohen, M. Elad, and P. Milanfar, "Regularization by denoising via fixed-point projection (red-pro))" SIAM Journal Imaging Sciences, vol. 14, no. 3. pp. 1374 1406, 2021.
[31] L. I. Rudin, S. Osher, and E. Fatemi, "Nonlinear total variation based noise removal algorithms," Physica
D. vol. 60. no. 1-4, pp. 259-268, November 1992.
[32] M. Bioucas- and M. T. Figueiredo, "A new TwIST: Two-step iterative shrinnaage/tnresholding algorithms for image restoration," IEEE Trans. Image Process. vol. 16, no. 12, pp. 2992-3004, December 2007.
[33] A. Beck and M. Teboulle, "Fast gradient- based algorithm for constrained total variation image denoising and deblurring problems," IEEE Trans. Image Process., vol. 18, no. 11. pp.
November 2009.
[34] T. Karras, S. Laine, and T. Aila, "A style-based generator architecture for generative adversarial networks." in Pruc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), Long Beach, CA. USA, June 2019, pp. 4396 4405.
[35] T. Karras, S. Laine, M. Aittala, J. Hellsten, J. Lehtinen, and T. Aila, "Analyzing and improving the image quality of StyleGAN," Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), Seattle, WA, USA, June 2020, pp. $107-8116.
[36] S. Menon, A. Damian. S. Hu, N. Ravi, and C. Rudin, "PULSE: Self-supervised photo upsampling via latent space exploration of generative models," in Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), Seattle, WA, USA, June 2020, pp. 2434-2442.
[37] G. Daras, J. Dean, A. Jalal, and A. G. Dimakis, "Intermediate layer optimizationfor inverse problems using deep generative models," 2021, arXiv:2102.07344.
[38] E. Candès and M. B. Wakin, "An introduction to compressive sensing." JEEE Signal Process. Mag., vol.
25, no. 2. pp. 21-30, March 2008.
11

---

[39] Parikh and S. Boyd, "Proximal algorithms." Foundations and Trends in Optimization, vol. 1, no. 3, pp. 123-231, 2014.
[40] K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, "Image denoising by sparse 3-D monnform-domast collaborative filtering," IEEE Trans. Image Process., vol. 16, no. 16, pp. 2080-2095, August 2007.
[41] K. Zhang, W. Zuo, Y. Chen. D. Meng. and L. Zhang. "Beyond a Gaussian denoiser: Residual learning of deep CNN for image denoising," IEEE Trans. Image Process., vol. 26, no. 7, pp.
July 2017.
[42] M. A. I. Figueiredo and R. D. Nowak, "An EM algorithm for wavelet-based image restoration." IEEE Trans. Image Process., vol. 12, no. 8, pp. 906-916, August 2003.
[43] Daubechies, M. Defrise, and C. De Mol, "An iterative thresholding algorithm for linear inverse problems with a sparsity constraint," Commun. Pure Appl. Math., vol. 57, no. 11, pp. 1413-145) 1457, November 2004,
[44] J. Bect, L. Maran-Feraud, G. Aubert, and A. Chambolle, "A un-unfieed variational framework for image restoration," in Proc. ECCV, Springer, Ed., New York, 2004, vol. 3024, pp. 1-13.
[45] A. Beck and M. Teboulle, "A fast iterative shrinkage-thresholdii algorithm for linear inverse problems," SIAM J. Imaging Sciences, vol. 2, no. 1, pp. 183-202, 2009.
[46] U. S. Kamilov, H. Mansour, and B. Wohlberg, "A plug-and-plaa priors approach for solving nonlinear imaging inverse problems," /EEE Signal Process. Letr., vol. 24, no. 12, pp. 1872-1876 December 2017.
[47] G. Mataev, M. Elad, and P. Milanfar, "DeepRED:
Deep image prior powered by RED," in Proc. IEEE Int. Conf. Comp. Vis. Workshops (ICCVW), Seoul, South Korea, Oct 27- 2, 2019, pp. 1-10.
[48] Liu, Y. Sun, C. Fldeniz, W. Gan, An, and U. S. Kamilov, "RARE: Image reconstruction using deep priors learned without ground truth." IEEE J. Sel. Topics Signal Process. vol. 14, no. 6, pp. 1088-1099, 2020.
[49] M. Xie, J. Liu, Y. Sun, W. Gan, B. Wohlberg, and U. S. Kamilov, "Joint reconstruction and calibration using regularization by denoising with application to computed tomography," in Proc. IEEE Int. Conf. Comp. Vis. Workshops (ICCVW), October 2021, pp. 5028-4031
[50] M. T. McCann, K. H. Jin, and M. Unser, "Convolutional neural networks for inverse problems in imaging: A review," IEEE Signal Process. Mag.. vol. 34, no. 6, pp. 85 85-95, 2017.
[51] A. Lucas, M. Iladdi, R. Molina, and A. K. Katsaggelos, "Using deep neural networks for inverse problems in imaging: Beyond analytical methods," IEEE Signal Process. Mag., vol. 35, no. 1, pp. 20-36, Jan. 2018.
[52] F. Knoll, K. Hammernik, C. Zhang, S. Moeller, T. Pock, D. K. Sodickson, and M. Akcakaya, "Deep-lcarning methods for parallel magnetic resonance imaging reconstruction: A survey of the current approaches, trends, and issues," IEEE Signal Process. Mag., vol. 37, no. I, pp. 128-140, Jan. 2020.
[53] G. Ongie, A. Jalal, C. A. Metzler, R. G. Baraniuk, A. G. Dimakis, and R. Willett, "Deep learning techniques for inverse problems in imaging." IEEE J. Sel. Areas Inf. Theory, vol. 1, no. 1. pp. 39
39- 56, May 2020.
[54] J. Tan, Y. Ma, and D. Baron, "Compressive imaging via approximate message passing with image denoising," " IEEE Trans. Signal Prucess., vol. 63, no. 8. pp. 2085-2092, Apr. 2015.
[55] C. A. Metzler, A. Malcki, and R. G. Baraniuk, "From denoising compressed sensing," IEEE Trans. Inf. Theory, vol. 62, no. 9. pp. 5117-5144, September 2016.
[56] C. A. Metzler, A. Maleki, and R. Baraniuk, "BM3D-PRGAMP. Compressive phase retrieval based on BM3D demoising," in Proc. IEEE Int. Conf. Image Proc., Phoenix, AZ, USA. September 25-28, 2016, pp. 2504-2 -2508.
[57] A. Fletcher, S. Rangan, S. Sarkar, and P. Schniter, "Plug-in estimation in high-dimensional linear inverse problems: A rigorous analysis." in Proc. Advances in Neural Information Processing Systems 32, Montréal, Canada, Dec 3-8, 2018, pp. 7451-7460.
[58] K. Gregor and Y. LeCun, "Learning fast approximation of sparse coding," in Proc. 27th Int. Conf. Machine Learning (ICML), Haifa, Israel, June 21-24, 2010, pp. 399-406.
[59] U. Schmidt and S. Roth, "Shrinkage fields for effective image restoration." in Proc. IEEE Conf. Computer Vision and Pottern Recognition (CVPR), Columbus, OH, USA, June 23-28, 2014, pp. 1781-....
[60] Y. Chen, W. Yu, and T. Pack, "On learning optimized reaction diffuction processes for effective image restoration." in Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), Boston, MA, USA. June 8-10, 2015, pp. 5261-5269.
[61] Y. Yang, J. Sun, H. Li, and Z. Xu, "Deep ADMM-N- Net for compressive sensing MRI," in Proc. Advances in Neural Information Processing Systems 29, 2016, pp. 10-18.
[62] J. Zhang and B. Ghanem, "ISTA-Net: Interpretable optimization iisoonniiidiiidddd deep network for image compressive sensing." in Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), 2018, pp. 18377
12

---

[63] H. K. Aggarwal, M. P. Mani, and M. Jacob, "MoDL: Model-based deep learning architecture for inverse problems." IEEE Trans. Med. Imag. vol. 38, 2, pp. 405, Feb. 2019.
[64] J. Liu, Y. Sun, W. Gan, B. Wohlberg, and U.S. Kamilov, "SGD-Net: Efficient model-based feep learning with theoretical guarantees," IEEE Trans. Comput. Imaging, vol. 7, pp. 598 610, 2021.
[65] D. Ulyanov, A. Vedaldi, and V. Lempitsky. "Deep image prior." in Prec. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), Salt Lake City, UT, USA, June 18-22, 2018, pp. 9446-9454.
[66] R. Heckel and P. Hand, "Deep decoder: Concisc image representations from untrained non-convolutional networks," in Int. Conf. on Learning Representations (ICLR), 2018.
[67] M. Terris, A. Repetti, J.-C. Pesquet, and Y. Wiaux. "Building firmly nonexpansive convolutional neural networks," in Proc. IEEE Int. Conf. Acoustics, Speech and Signal Process., Barcelona, Spain, May 2020, pp. 8658-8662.
[68] T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida, "Spectral normalization for generative adversarial networks," in Int. Conf. Learning Representations (ICLR), Vancouver, Canada, Apr. 2018.
[69] M. Fazlyab, A. Robey, Hassani. H., M. Marari, and G. Pappas. "Efficient and accurate estimation of Lipschitz constants for deep neural networks," " in Proc. Advances in Neural Information Processing Systems 33, Vancouver, BC, Canada, Dec. 2019, pp. 11427-11438.
[70] Elad, Sparse and Redundant Representations, Springer. 2010.
[71] S. Foucart and H. Rauhut, A Methematical Introduction to Compressive Sensing, Birkhauser, 2013,
[72] R. Vershynin, High-DDmensioon
Probability: An Introduction with Applications in Data Science, Cam- bridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
[73] H. H. Bauschke and P. L. Combettes, Conver Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2 edition, 2017.
[74] D. Gilton, G. Ongie, and R. Willett, "Deep equilibrium architectures for inverse problems in imaging." 2021, MIXiv:2102.0794.
[75] X. Xu, J. Liu, Y. Sun, B. Wohlberg, and U.S. Kamilov, "Boosting the performance of plug-and and-play priors via denoiser scaling," in 2020 54th Asilomar Conference on Signals, Systems, and Computers. IEEE, 2020,
pp. 1305 1312.
[76] A. Mousavi, A. B. Patel, and R. G. Baraniuk, "A deep learning approach to structured signal recovery," in Proc. Allerton Conf. Communication, Control, and Computing, Allerton Park, II, USA, September 30-October 2, 2015, pp. 1336-1343.
[77] K. Kulkarni, Lohit, Turaga, R. Kerviche, and A. Ashok, "ReconNet: Non-iterative reconstruction of images from compressively sensed measurements," in Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), Las Vegas, NV, USA, June 2016, pp. 449-458.
[78] D. Martin, C. Fowikes, D. Tal, and Malik, "A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics." in Proc. IEEE Int. Conf. Comp. Vis. (ICCV), Vancouver, Canada, July 7-14, 2001. pp. 416-423.
[79] E. Agustsson and R. Timofte, "Ntire 2017 challenge on single image super-resolution: Dataset and study," in Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR) Workshops, July 2017, vol. 3, pp. 126-135.
[80] M. Lustig, D. L. Donoho, and J. M. Pauly, "Sparse MRI: The application of compressed sensing for rapid MR imaging," Magn. Reson. Med., vol. 58, no. 6, pp. 1182-1195, December 2007.
[81] M. Lustig, D. L. Donoho, J. M. Santos, and J. M. Pauly, "Compressed sensing MRI," IEEE Signal Process. Mag., vol. 25, no. 2. pp. 72-82 72-82,77 2008.
[82] T. Karras, T. Aila, S. Laine, and J. Lehtinen, "Progressive growing of GANs for improved quality, stability, and variation." in Inf. Conf. on Learning Representations (ICLR), 2018.
[83] Y. Nesterov, Introductory Lectures on Convex Optimization: Basic Course, Kluwer Academic Publishers, 2004.
[84] N. Eslahi and A. Foi, "Anisotropic spatiotemporal regularization in compressive video recovery by adaptively modeling the residual errors as correlated noise," " in IEEE Image, Video, and Multidimensional Signal Processing Workshop, Zagorochoria, Greece, June 2018, pp. 1-5.
13


Reviews:
[{"review_id": "kYAzRiftsqD", "reviewer": "Reviewer_V21i", "summary": "This paper considers recovery guarantees for Plug-and-Play algorithms (PnP), where an image denoiser is used to solve inverse problems such as compressed sensing. Theoretical results show that under certain assumptions, the error between the estimate and ground truth decay linearly, and experiments show that the practical implementations of the proposed algorithm gives state of the art reconstructions.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "__Strengths__:\n1. This paper provides the first recovery guarantees for PnP methods in compressed sensing. While traditional results consider asymptotic convergence of the algorithms, this paper characterizes the error decay between the estimate and the ground truth. \n\n1. The authors elaborate the results clearly. They first state a Theorem for ground truth lying in the range of the denoiser, then extend it to arbitrary signals, and finally show that the fixed points of their proposed PnP algorithm coincides with that of RED, another popular PnP algorithm.\n\n1. The authors also propose a novel algorithm that uses PnP along with an artefact removal network. While the results have better PSNRs, I cannot see any difference in reconstruction quality.\n\n__Weaknesses__:\n1. An obvious weakness is that under assumption 1, if $ \\|\\| x - D(x) \\|\\|_2 \\leq \\delta $ for all $x \\in \\mathbb{R}^n$, then the range of $D$ will need to contain a full dimensional subset of $\\mathbb{ R }^n$. This immediately implies that for S-REC to hold, the number of measurements needs to be at least $n$, and compressed sensing recovery should not be possible. This only seems to affect Theorem 2 and Theorem 3, since Theorem 1 assumes $x^*$ lies in the range of $D$ and hence does not require the previous assumption.\n\n1. I have some concerns about the constants. If $\\alpha < 1$, then assumption 1 implies that $ | x - z | - | D(x) - D(z) | \\leq | x - z - D(x) + D(z) | \\leq \\alpha | x - z | \\Rightarrow |D(x) - D(z) | \\geq ( 1 - \\alpha ) | x - z | $. Since $D$ needs to be both Lipschitz ( from Assumption 3) and reverse-Lipschitz (from the previous derivation), the range of $D$ must be the whole of $\\mathbb{R}^n$, making this a terrible denoiser. This makes the condition $\\alpha \\geq 1$ necessary, which later affects the parameters $c$ in equation 9 and $\\varepsilon$ in equation 12. I think there is some range of parameters that are physically meaningful, but the authors should detail this.\n\n1. The artefact removal network seems to help the PnP method, but it is difficult to find any qualitative differences between the reconstructions with / without this extra network. Additionally, the use of this network seems somewhat auxiliary to the rest of the results.\n\n__Novelty and significance__:\nWhile I am not an expert on PnP methods, to the best of my knowledge this is the first result that gives a non-asymptotic recovery result wrt the ground truth $x^*$.\n\n__Clarity__:\nI found the paper easy to read, and the results were elaborated clearly.\n\n__Score justification__:\nOverall I think this is a good paper. The analysis techniques are fairly standard, but are used innovatively and make connections between existing work, for e.g., the link between S-REC and Restricted Strong Convexity. While I think assumption 1 is currently too strong, I think the rest of the analysis is novel and informative, and perhaps future work can avoid this assumption. Hence I'm in favor of acceptance.\n\n__General comments__:\n1. In line 58 and line 69, use the actual spaces $\\mathbb{R}^n$ and $\\mathbb{R}^n$ instead of $Im(W)$, $Im(D)$. This helps avoid confusion on the dimension of the output.\n\n1. It is worth pointing out the scaling of the term $\\lambda = \\sigma_{\\max} (A^T A)$. Even for sub-gaussian matrices, this can be as bad as $O(\\sqrt{ \\frac{ n }{ m } })$ \n\n1. Please restate the Theorem statement in the appendix / proofs.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No obvious societal concerns.", "review_text": "", "extra_scores": {"ethical_concerns": "No obvious ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "k9kVMy5NjEu", "reviewer": "Reviewer_4SHo", "summary": "This paper contains three theoretical results as well as a numerical comparison for the regularization by denoising (RED) and plug-and-play prior (PnP) algorithms, in which energy minimization algorithms for inverse problems are used as a template to derive algorithmic schemes that utilize denoising (or artifact removal) networks instead of regularizers. The paper shows that under (compressed-sensing-like) assumptions the recovery of certain solutions can be guaranteed (Theorem 1), and subsequently extends it to an error bound in the presence of noise and no assumptions on the solution to be recovered (Theorem 2). Finally, it is shown that RED and PnP have the same fix point sets if the used denoising network is non-expansive (Theorem 3). In the numerical results, a comparison on the exemplary problem of compressed sensing image recovery is conducted to conclude that artifact removal networks (specialized on removing artifacts that arise in the considered reconstruction problem) perform significantly better than generic denoising networks.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well-written, the motivation is clear, and the theorems are presented in an easy-to-follow way. Thus, the paper fully convinced me in terms of its clarity. Similarly, I do think the work is significant in the sense that getting a better theoretical understanding and control of the well-working approaches that utilize deep learning is important. Considering the success of compressed sensing, I consider this work as a small next step towards establishing similar results for PnP/RED priors. The presented theoretical results are new, but also not surprising. Moreover, the numerical experiments are almost orthogonal to the theory. This is partially due to the difficulty of verifying the assumptions from the theorems (as the authors themselves rightfully mention as a limitation in section 5). Yet, an in-depth discussion on what the conditions of the theorem mean / what kind of guarantees they provide would have been interesting. For instance, \n- assuming estimates as they arise in compressed sensing (e.g. assuming Im(D) \\subset k-sparse vectors) how Lipschitz continuous (value of \\alpha) should D be for c in Theorem 1 to be less than one?\n- The estimate in Thm. 2 crucially depends on the distance of $x^*$ to Zer(R). While the supplement shows that the algorithm converges to values of $\\|R(x^t)\\|$ that are somewhat small, I am not sure how large the contribution of this part of the error term is. I would be curious to see different results of a fixed point iteration of $D$. I would hope for this to converge to a point in Zer(R), and this might illustrate the thin line between desirable properties for convergence (averaged / contractive operators), and performance. In line 226 it is stated that \"both R and D are contractive operators\", which, however, means Zer(R) is a singleton and the distance term in Theorem 2 has to be large for some images. Please comment on this.  \n\nIn summary, I believe this is a well-written paper with some new results that could spark further research in the important topic of understanding the behavior when using generic denoising / artifact removal networks as regularizers.\n\nMinor comments\n- Regarding Fig. 1, in my experience trying to adversarially find points at which the network indicates a large Lipschitz constant gives a better impression of the true Lipschitz constant than random sampling. In particular, I am not sure if $D$ really is a contraction (while also believing that this is not necessarily desirable as pointed out above). \n- Before eq. (10) it says \"is less that one if\" >> \"than\"\n- In line 206 \"the residual R of the AR operator still satisfies Lipschitz continuity assumptions\". Does it satisfy a Lipschitz continuity assumption (which is something any conv-relu network does because it is piecewise linear with finitely many pieces), or does is it 1 or 2 Lipschitz (as the denoisers are). Since imposing Lipschitz continuity reduces the denoising performance this is important to state. \n- The $c$ in the line before 52 in the supplementary material is missing a power $t$\n\n----------------------\nAfter writing the above review I checked the code in more detail: The \"SpectralNorm\" class seems to run the power methods on the weights of convolutional layers by considering the weights as a matrix. I don't think that this computes the right normalization constant as the results may differ from computing the power method for actual convolutions or doing the appropriate  computation in Fourier space. I think it is worth checking the difference.  I also tested the Lipschitz assumption, and it can break for small perturbations, e.g. when choosing\nu1 = torch.randn([1, 1, 20, 20]).to(device)\nu2 = u1+ 1e-5*torch.randn([1, 1, 20, 20]).to(device)\nf1 = dncnnModel(u1)\nf2 = dncnnModel(u2)\n(yielding Lipschitz constants of around 7 for the provided models) but this is likely due to the limited precision / numerical errors?\n\n------------------------\nI would like to thank the authors for their detailed explanations in the rebuttal. I think this is a very nice piece of work!", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the limitations and impact are adequately discussed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "W7U-KOXBvL4", "reviewer": "Reviewer_rXws", "summary": "In this work, the authors analyze Plug and Play (PnP) methods for solving inverse problems, and utilize the framework from compressive sensing with generative models to derive theoretical guarantees. In particular, the authors show that in a linear inverse problem, if 1) the residual operator of a denoiser is Lipschitz and 2) the measurement matrix satisfies a restricted eigenvalue condition over the range of the denoiser, then linear convergence of the PnP algorithm can be established for suitable parameter choices. Moreover, under a similar set of assumptions, an equivalence between PnP and Regularization by Denoising (RED) is derived, in that both algorithms have the same set of solutions. Empirical evaluations also show 1) supporting evidence for aspects of the theory holding for trained neural network-based denoisers and 2) that PnP algorithms compete with, and can outperform, state-of-the-art compressive sensing approaches using deep generative priors.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Originality: \n\nThe theoretical results presented in this work are, to the reviewer’s knowledge, the first to combine results related to CS with generative priors to PnP methods. The particular convergence analysis seems to be an extension of [23], by showing that the S-REC property over the range of the denoiser is sufficient for convergence, rather than the strong convexity and smoothness property of the data fidelity term as assumed in [23]. Indeed, in the appendix it is shown that S-REC is equivalent to (restricted) strong convexity of the data fidelity term. Moreover, all iterates are shown to be in the image of the denoiser (by definition of the PnP algorithm). On this note, it would be good if the authors could comment on the larger technical difference between the proof technique presented here and that of [23]. For example, does focusing on S-REC to prove convergence provide technical hurdles over [23]?\n\n# Quality: \n\n- Strengths: - The paper adds novel analysis to the literature on theoretical guarantees for PnP algorithms, and have the potential to spark future research into using tools from generative priors to analyze PnP algorithms. - It is well-written and easy to follow. - The theoretical guarantees provide convergence rates on the algorithm, and experimental evidence is shown for some of the theoretical assumptions to approximately hold in practice with neural network-based denoisers. - The empirical results showcase the effectiveness of PnP algorithms against state-of-the-art generative prior-based approaches.\n\n- Weaknesses: - It is unclear when the S-REC property would hold for denoisers, or how many measurements are required for it to hold. In the case of CSGM, there is a clear connection between the “complexity” of the generative model and the sample complexity required for $A$ to satisfy S-REC (namely, $m = O(k \\log L)$ random Gaussian measurements suffice for an $L$-lipschitz generator with latent dimension $k$). However, the authors did not comment on what scenarios we should expect this condition to hold for neural network-based denoisers. What sorts of notions of “complexity” could potentially hold for the range of denoisers that would provide some intuition as to when we should expect S-REC to hold? Since the image of $D$ consists of clean, natural images, we should expect it to be approximately low-dimensional. Are there aspects of their architectures that could provide some (quantitative) answers as to how low-dimensional the image of $D$ might be in practice?\n\n# Clarity: \n\nOverall, the paper is well-written. I found the discussion of the results and proofs easy to follow and related work seems to be cited properly. The following are a few typos found:\n- pg 2 line 60: “optimizatio” -> “optimization”, pg 9 line 296: “reduced” -> “reduce”\n\n# Significance: \n\nI think it is interesting to draw a connection between PnP methods and generative prior-based methods, as both have some similarities in terms of their philosophy (namely, they detach learning data-driven priors from downstream inverse problems). Given the recent developments in [23] along with the combined analysis of CSGM and the present work, there’s certainly the possibility for more follow-up work from the community to provide further theoretical analyses for PnP methods using some of the tools from the field of generative priors. This could spark studies of the “complexity” of denoisers and the relationship between the architectures of denoisers and the quality of the PnP algorithm for various measurement operators. It would also be of interest to see if techniques from generative prior-based approaches for nonlinear inverse problems could then aid in deriving guarantees for PnP methods applied to nonlinear measurements.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately discussed various limitations and broader impacts in Sections 5 and 6 of the manuscript.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides the first recovery guarantees for Plug-And-Play (PnP) and Regularization by Denoising (RED) methods for compressed sensing.  While it uses similar analysis as in the literature for compressed sensing from generative priors, this extension is significant because it shows those tools work for a class of methods that are computationally cheaper than generative models.  This work could be improved by a study of the conditions under which the Set-Restricted Eigenvalue Condition holds in the present context.  Despite this weakness, the work has the potential to inspire additional theoretical interest in PnP/RED for solving inverse problems.  In the camera ready, please clarify where the residual boundedness and the nonexpansiveness of D must hold, as discussed with the reviewers.
Decision: Accept (Poster)