Recovery Analysis for Plug-and-Play Priors using the Restricted Eigenvalue Condition
Year: 2021

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 fixedpoints 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.

heading: 1 Introduction
text: Many imaging problems—such as denoising, inpainting, and super-resolution—can be formulated as an inverse problem involving the recovery of an image x∗ ∈ Rn from noisy measurements
y = Ax∗ + e , (1)
where A ∈ Rm×n is the measurement operator and e ∈ Rm is the noise. Compressed sensing (CS) [1, 2] is a related class of 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) [3, 4]. While traditional CS recovery relies on sparsity-promoting priors, recent work on compressed sensing using generative models (CSGM) [5] has broadened this perspective to priors specified through pre-trained generative models. CSGM has prompted a 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-play priors (PnP) [10, 11] and regularization by denoising (RED) [12] are two methods related to CSGM that can also leverage pre-trained deep models as priors for inverse problems. However, unlike CSGM, the regularization in PnP/RED is not based on restricting the solution to the range of a generative model, but rather on denoising the iterates with an 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 to investigate the theoretical properties and interpretations of PnP/RED algorithms [19–30].
35th Conference on Neural Information Processing Systems (NeurIPS 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 a 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 as 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://github.com/wustl-cig/pnp-recovery.

heading: 2 Background
text: Inverse problems. A common approach to estimating x∗ in (1) is to solve an optimization problem:
min x∈Rn
g(x) + h(x) with g(x) = 1
2 ‖y −Ax‖22 , (2)
where g is a data-fidelity term that quantifies consistency with the observed data y and h is a regularizer that encodes prior knowledge on x. For example, a widely-used regularizer in inverse problems is the nonsmooth total variation (TV) function h(x) = τ‖Dx‖1, where D is the gradient operator and τ > 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 z∈Rk
1 2 ‖y −AW(z)‖22 , (3)
where W : Rk → Im(W) ⊆ Rn is a pre-trained generative model, such as StyleGAN-2 [34, 35]. The set Im(W) 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 (ILO) [37] that can recover highlyrealistic 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:
‖Ax−Az‖22 ≥ µ‖x− z‖22 − η ∀x, z ∈ Im(W) , (4) where µ > 0 and η ≥ 0. 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 a family of iterative algorithms that are based on replacing the proximal operator proxγh of the regularizer h within a proximal algorithm [39] by a more general denoiser D : Rn → Im(D) ⊆ Rn, such as BM3D [40] or DnCNN [41]. For example, the widely used proximal gradient method (PGM) [42–45] can be implemented as a PnP algorithm as [46]
xk = T(xk−1) with T := D(I− γ∇g) , (5) where g is the data-fidelity term in (2), I denotes the identity mapping, and γ > 0 is the step size. Remarkably, this heuristic of using denoisers not associated with any h within a proximal algorithm exhibited great empirical success [13–18] and spurred a great deal of theoretical work on PnP [19–28]. In particular, it has been recently shown in [23] that, when the residual of D is Lipschitz continuous, PnP-PGM converges to a point in the fixed-point set of the operator T that we denote Fix(T).
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
xk = xk−1 − γG(xk−1) with G := ∇g + τ(I− D) , (6) where γ > 0 is the step size and τ > 0 is the regularization parameter. For a locally homogeneous D that has a strongly passive and symmetric Jacobian, the solution of RED solves (2) with h(x) = (τ/2)xT(x− D(x)) [12, 22]. Subsequent work has resulted in a number of extensions of RED [29, 30,47–49]. For example, it has been shown in [29] that, when D is a 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-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 as a class of algorithms in compressive sensing known as approximate message passing (AMP) [54–57]. Another related family of algorithms are those based on the idea of deep unrolling (for an 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 [59–64]. Deep image prior [65] and deep decoder [66] also use neural networks as 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.

heading: 3 Recovery Analysis for PnP and RED
text: 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 := I−D of the operator D is bounded by δ and Lipschitz continuous with constant α > 0, which can be written as
‖R(x)‖2 ≤ δ and ‖R(x)− R(z)‖2 ≤ α‖x− z‖2, ∀x, z ∈ Rn . (7)
The rationale for stating Assumption 1 in terms of the residual R is based on our interest in residual deep neural nets that take a 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-widely 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, ν] for images in [0, ν]n ⊂ Rn for some ν > 0. The α-Lipschitz continuity of R can be enforced by using any of the recent techniques for training Lipschitz constrained deep neural nets [23, 67–69]. Fig. 1 presents an empirical evaluation of the Lipschitz continuity of R used in our simulations. Assumption 2. The measurement operator A ∈ Rm×n satisfies the set-restricted eigenvalue condition (S-REC) over Im(D) ⊆ Rn with µ > 0, which can be written as
‖Ax−Az‖22 ≥ µ‖x− z‖22, ∀x, z ∈ Im(D) . (8)
S-REC in Assumption 2 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 a 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,70–72], including for those synthesized by generative models [5,6,9,37].
Despite this limitation, Assumption 2 is 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 to hold only over the image set Im(D) rather than over the whole Rn. This suggests a 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) := {x ∈ Rn : x = D(x)} of the fixed points of D. Note that Fix(D) is equivalent to the set Zer(R) := {x ∈ Rn : R(x) = 0} of the zeros of the residual R = I − 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 Zer(R), but these results can be equivalently stated using Fix(D).
We first state the PnP recovery in the setting where there is no noise and x∗ ∈ Zer(R). Theorem 1. Run PnP-PGM for t ≥ 1 iterations under Assumptions 1-2 for the problem (1) with no noise and x∗ ∈ Zer(R). Then, the sequence xt generated by PnP-PGM satisfies
‖xt − x∗‖2 ≤ c‖xt−1 − x∗‖2 ≤ ct‖x0 − x∗‖2 , (9) where x0 ∈ Im(D) and c := (1 + α)max{|1− γµ|, |1− γλ|} with λ := λmax(ATA).
The proof of the theorem is available in the Supplement. Theorem 1 extends the theoretical analysis of PnP in [23] by showing convergence to the true solution x∗ of (1) instead of the fixed points Fix(T) of T in (5). The condition x0 ∈ Im(D) can be easily enforced by simply passing any initial 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
1
µ(1 + 1/α) < γ <
2 λ − 1 λ(1 + 1/α) , (10)
which is possible if α < 2µ/(λ− µ). Since all PnP algorithms have the same fixed points [20, 24], 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 to Fix(T).
We now present a more general result that relaxes the assumptions in Theorem 1. Theorem 2. Run PnP-PGM for t ≥ 1 iterations under Assumptions 1-2 for the problem (1) with x∗ ∈ Rn and e ∈ Rm. Then, the sequence xt generated by PnP-PGM satisfies
‖xt − x∗‖2 ≤ c‖xt−1 − x∗‖2 + ε ≤ ct‖x0 − x∗‖2 + ε(1− ct) (1− c) , (11)
where x0 ∈ Im(D) and ε := (1 + c) [( 1 + 2 √ λ/µ ) ‖x∗ − projZer(R)(x∗)‖2 + 2/ √ µ‖e‖2 + δ(1 + 1/α) ] (12)
and c := (1 + α)max{|1− γµ|, |1− γλ|} with λ := λmax(ATA).
Theorem 2 extends Theorem 1 by allowing x∗ to be outside of Zer(R) and extends the analysis in [5] by considering operators D that do not necessarily project onto the range of a generative model. In the error bound ε, the first two terms are the distance of x∗ to Zer(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) ∩ Zer(∇g) 6= ∅, 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 = I− R is nonexpansive. Assumption 3. The denoiser D is nonexpansive
‖D(x)− D(z)‖2 ≤ ‖x− z‖2, ∀x, z ∈ Rn .
This is related but different from Assumption 1 that assumes the residual R is α-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 R 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. 1 indicates that D used in our experiments is nonexpansive.
Theorem 3. Suppose that Assumptions 1-3 are satisfied and that Zer(∇g) ∩ Zer(R) 6= ∅, then PnP and RED have the same set of solutions: Fix(T) = 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(∇g) ∩ Zer(R) 6= ∅ implies that there exist vectors that are noise/artifact free according to R and consistent with the measurements y. While this assumption is not universally applicable to all the inverse problems and priors, it still provides a highly-intuitive 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 a step size that satisfies the condition in (10), then T is a contraction over Im(D), which implies that PnP-PGM converges linearly to its unique fixed point in Im(D). The direct corollary of our analysis is that, in the noiseless scenario y = Ax∗ with x∗ ∈ Zer(R), the image x∗ is the unique fixed point of both PnP and RED over Im(D). It is worth mentioning that several of our assumptions have been stated in a way that simplifies mathematical exposition, but can alternatively be presented in a significantly weaker form. For example, the boundedness assumption in (1)—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 of RED-SD (see page 4 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 a 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.

heading: 4 Numerical Evaluation
text: Before presenting our numerical results, it is important to note that PnP and RED are well-known methods and it is 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
context of our theory. Our goal in this section is thus to both (a) empirically evaluate the recovery performance of PnP/RED and (b) compare their performances relative to widely-used CS algorithms.
We consider two scenarios: (a) CS using random projections and (b) CS for magnetic resonance imaging (CS-MRI). In order to gain a deeper insights into performance under subsampling, we use an idealized noise-free setting; however, we expect similar relative performances under noise. For each scenario, we include comparisons with several well-established methods based on deep learning.
We consider two priors for PnP/RED: (i) an AWGN denoiser and (ii) an artifact-removal (AR) operator trained to remove artifacts specific to the PnP iterations. We implement both priors1 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 as a nonexpansive residual network R that predicts the noise residual from a noisy input image. Thus, R satisfies the necessary condition for the nonexpansiveness of D. Similar to [74], we train the AR prior by including it into a 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 to g. The reconstruction quality is quantified using the peak signal-to-noise ratio (PSNR) in dB.

heading: 4.1 Reconstruction of Natural Images from Random Projections
text: We adopt a simulation setup widely-used in the CS literature, in which non-overlapping 33 × 33 patches of an image are measured using the same m× n random Gaussian matrix A, whose rows have been orthogonalized [62, 77]. The patches are vectorized to n = 1089-length vectors x∗. The training data for the denoiser is generated by adding AWGN to the images from the BSD500 [78] and
1For additional details and code see the Supplement and the GitHub repository.
DIV2K datasets [79]. We pre-train several deep models as denoisers for σ ∈ [1, 15], using σ intervals of 0.5, and use the denoiser achieving the best PSNR value in each experiment. We use the same set of 91 images as in [77] to train the AR operators that are implemented on individual image patches at a time for the CS ratios (m/n) of {10%, 30%, 40%, 50%}. In order to 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∇g. Our first numerical study in Fig. 1 evaluates the Lipschitz continuity of our pre-trained denoisers and the AR operators by following the procedure in [23]. We use the residual R and its corresponding operator D = I − R and plot the histograms of α1 = ‖R(x) − R(z)‖2/‖x − z‖2 and α2 = ‖D(x)− D(z)‖2/‖x− z‖2 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. 1 confirms empirically that both R and D are contractive operators.
Theorem 2 establishes that the sequence of iterates xt generated by PnP-PGM converges to the true solutions x∗ up to an error term. Fig. 2 illustrates the convergence behavior of PnP/RED in terms of ‖xt − x∗‖22/‖x∗‖22 and peak signal-to-noise ratio (PSNR) for CS with subsampling ratio of 30% on Set11. 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.
We 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 all deep learning-based methods that have publicly available implementations. The numerical results on Set11 and BSD68 with respect to four measure-
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 performance2 compared to all the other methods, outperforming PnP using the AWGN denoiser by at least 0.57 dB on BSD68. Fig. 3 (top) shows visual examples for an image from Set11. 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 to other methods.

heading: 4.2 Image reconstruction in Compressed Sensing MRI
text: 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 an image x∗ from its sparsely-sampled Fourier measurements. We simulate a single-coil 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 for PnP/RED were trained using the brain dataset from [62], where the test set contains 50 slices of 256× 256 images (i.e., n = 65536). We train seven variants of DnCNN, each using a separate noise level from σ ∈ {1, 1.5, 2, 2.5, 3, 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 σ = 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 TV [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 in Fig. 3 (bottom). It can been seen that PnP/RED with an AWGN denoiser matches the performance of ISTA-Net+
2We did not use RED with the AR prior in our experiments since it is expected to 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.

heading: 4.3 Comparison with generative models on human faces
text: 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× 33× 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 σ ∈ {1, 2, 3, 4, 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 to 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 a state-of-the-art generative model specifically trained on face images. However, PnP (AR) achieves better PSNR and a similar visual quality as ILO.

heading: 5 Conclusion and Future Work
text: 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 a 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-removal operators that take into account the actual artifacts within PnP iterates.
The work presented in this paper has a 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 a given measurement operator. One can also consider the Lipschitz assumptions on R/D as a limitation, since those can have a 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 non-Lipschitz-constrained priors, we expect that this will reduce their stability and ultimately hurt their recovery performances. A relatively minor limitation of our simulations is that they were performed without AWGN. One can easily re-run our 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 on PnP/RED that will lead to extensions and improvements to our results.

heading: 6 Broader impact
text: 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 a 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
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 a 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-1813910, CCF-2043134, and CCF-2046293 and by the Laboratory Directed Research and Development program of Los Alamos National Laboratory under project number 20200061DR.

Review summaries:
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.  

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.