Theoretical understanding of Plug-and-Play (PnP) algorithms, where an off-the-shelf denoiser is used for image regularization , is an active research topic. In this work, we study the problems of exact and stable signal recovery from compressively sensed (CS) measurements using PnP algorithms. We focus on a class of linear denoisers for which it is possible to associate a convex regularizer Φ . We consider the CS problem of minimizing Φ ⁡ ( 𝒙 ) subject to 𝐀 ⁢ 𝒙 = 𝐀 ⁢ 𝛏 , where 𝐀 is the random sensing matrix and 𝛏 is the ground truth. We prove that if 𝐀 is Gaussian and 𝛏 lies in the range of the associated denoiser 𝐖 , then the minimizer is almost surely 𝛏 if 𝑟 𝑎 𝑛 𝑘 ⁡ ( 𝐖 ) is less than the number of measurements and almost never otherwise. We extend the result to subgaussian matrices, except that we can guarantee exact recovery only with high probability. For noisy measurements, we consider a robust analogue of the recovery problem and prove that the error between the recovered and the ground-truth signal is bounded by the noise strength . In particular, we derive the sample complexity of CS as a function of reconstruction error and success rate. We perform numerical experiments to validate our theoretical findings.

Presents corrections to the article “On the Contractivity of Plug-and-Play Operators”.

In plug-and-play (PnP) regularization, the proximal operator in algorithms such as ISTA and ADMM is replaced by a powerful denoiser. This formal substitution works surprisingly well in practice. In fact, PnP has been shown to give state-of-the-art results for various imaging applications. The empirical success of PnP has motivated researchers to understand its theoretical underpinnings and, in particular, its convergence. It was shown in prior work that for kernel denoisers such as the nonlocal means, PnP-ISTA provably converges under some strong assumptions on the forward model. The present work is motivated by the following questions: Can we relax the assumptions on the forward model? Can the convergence analysis be extended to PnP-ADMM? Can we estimate the convergence rate? In this letter, we resolve these questions using the contraction mapping theorem: (i) for symmetric denoisers, we show that (under mild conditions) PnP-ISTA and PnP-ADMM exhibit linear convergence; and (ii) for kernel denoisers, we show that PnP-ISTA and PnP-ADMM converge linearly for image inpainting. We validate our theoretical findings using reconstruction experiments.

In plug-and-play (PnP) regularization, the knowledge of the forward model is combined with a powerful denoiser to obtain state-of-the-art image reconstructions. This is typically done by taking a proximal algorithm such as FISTA or ADMM, and formally replacing the proximal map associated with a regularizer by nonlocal means, BM3D or a CNN denoiser. Each iterate of the resulting PnP algorithm involves some kind of inversion of the forward model followed by denoiser-induced regularization. A natural question in this regard is that of optimality, namely, do the PnP iterations minimize some f+g , where f is a loss function associated with the forward model and g is a regularizer? This has a straightforward solution if the denoiser can be expressed as a proximal map, as was shown to be the case for a class of linear symmetric denoisers. However, this result excludes kernel denoisers such as nonlocal means that are inherently non-symmetric. In this paper, we prove that a broader class of linear denoisers (including symmetric denoisers and kernel denoisers) can be expressed as a proximal map of some convex regularizer g . An algorithmic implication of this result for non-symmetric denoisers is that it necessitates appropriate modifications in the PnP updates to ensure convergence to a minimum of f+g . Apart from the convergence guarantee, the modified PnP algorithms are shown to produce good restorations.