Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper proposes an algorithm called SNIPS that solves noisy linear inverse problems via an approximate MMSE estimator which makes use of pre-trained Gaussian denoisers. The estimator is based on MCMC sampling which is driven by a synthetically annealed version of Langevin dynamics. The motivations and background leading up to the algorithms derivation are well discussed. Experiments show interesting results with regard to the diversity and faithfulness of the images generated.


---Edit after author responses---

Having read the other reviews and the responses posted by the authors, I am reducing my original scores from 6 --> 4. 
My main issues are that the submission lacks (i) a comparison with an experimental baseline, and (ii) clarity in explaining the technical sections of the paper.
main_review: Sections 1 and 2 are well written. The problem is clearly stated and the method is well motivated with a good discussion on prior work. However, the authors do not clearly state what the contributions of the current paper are. I suggest the authors highlight these in a subsection at the end of Section 2. It appears Section 3 and 4 are the main contributions of this work, but they fall short in delivering the clarity desired from any original piece of work.


Section 3 is technical and intricate but lacks clarity throughout.
It is not clear why access to the true score function \nabla log p(x|y) is not available. The assumptions that lead to these limitations need to be made clearer at the beginning of Section 3.
The derivations in Section 3.1 are not explained well. It makes very little sense to the reader as to why the specific noise levels and correlations are chosen. The authors ought to provide a lot of intuition here. In Section 3 it is very unclear what quantities are known for the problem, which of those are assumed to be known for the purpose of the analysis, and which can be assumed to be known while designing the algorithm.

Section 2 makes a lot of notational assumptions which are very hard to follow. 

While the derivations in Section 3.2 are pushed to the appendix, the authors need to remind the reader what the significance of each of the equations 7-11 is by mentioning in words what these equations mean.
In Algorithm 1 the notation of the dagger and >, /> appear non-standard. I urge the authors to add a caption to the algorithm which clarifies this notation. 
Line 111: Is the algorithm in equation (2) called the Unadjusted Langevin algorithm (ULA)? If so perhaps the authors should mention that name.



Additional comments/typos:
Line 47: GAN-based and Langevin sampling --> based on GANs and Langevin sampling
Line 182: The quantity \eta_T is not defined explicitly. Please do so
Notation issue: \eta_T, n_T are defined as V^T \eta and V^T n respectively. 
\eta_T,i and n_T,i however is a component of \Sigma V^T\eta_i and \Sigma V^T n_i which is inconsistent. Please change the notation to make it easier to read.
Equations following line 182, please remind the reader that i_1 is a function of j.
limitations_and_societal_impact: The limitations are adequately addressed.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The authors address the problem of conditional sampling using Langevin dynamics. It is known that annealed Langevin dynamics speeds up convergence, and prior work that uses Langevin dynamics for conditional sampling does not correctly model the effects of annealing. Specifically, since there is some annealing noise added to the estimate, the likelihood distribution of the measurements given an estimate will change, and the authors derive approximations to the correct functional form. Experiments show that their new estimator can be implemented in practice.

main_review: __Strengths__:
1. In theory, existing work cannot handle the challenges posed in the paper. The authors define their problem clearly, and they are able to derive approximations to the posterior distribution given access to a generative model that estimates annealed priors.

__Weaknesses__:

1. The key point of this paper is that the distribution $p(y|x)$ must be modified when you do annealing of the distribution $p(x)$, since this can introduce dependencies between the measurement noise and the annealing noise. Prior work would use Bayes rule to calculate the posterior distribution under annealing, and hence would get an incorrect functional form for the annealed posterior distribution. Is the error in your approximated distribution smaller in some helpful way? Overall, since there are no error bounds for sampling from annealed posteriors that converge to the true posterior, I fail to see the significance of an exact derivation of the true annealed posterior. In fact your derivation only gets an approximation to the annealed posterior, and hence will introduce its own error.

1. The writing is extremely imprecise and the contributions are unclear.  Other than statements that prior work cannot handle ill-posed operators and noise, there isn't any empirical or theoretical evidence that prior work fails or that the proposed approach fixes this problem.

1. The authors say that the rational behind sampling in the SVD domain is in the appendix, but this only contains derivations for the conditional likelihood in the SVD domain. There is no theoretical justification for sampling in the SVD domain.

1. There are literally no comparisons to baselines. Reference [1] shows that a direction application of Bayes' rule gives good empirical results for inpainting and compressed sensing, while prior work cited in the paper has shown it for super-resolution, denoising, etc. Does your method have any empirical advantage?

__Missing references__:

[1] shows that posterior sampling is optimal for compressed sensing and needs to be cited.

[1] Jalal, Ajil, Sushrut Karmalkar, Alexandros G. Dimakis, and Eric Price. "Instance-Optimal Compressed Sensing via Posterior Sampling." arXiv preprint arXiv:2106.11438 (2021).
limitations_and_societal_impact: No societal concerns.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper discusses an algorithm for sampling from the posterior distribution of a linear inverse problem with the white Gaussian noise, given the MMSE Gaussian denoiser. 


---Edit after author responses---

After reading the reviews and responses I decided to decrease the score (from 7 to 5) mainly because of insufficient evaluation of the proposed method and issues with the derivations in Section 3.   
main_review: The paper has a nice literature overview and is overall well written. The proposed method combines the newly proposed blurring of the samples by the additional noise with dependence on the measurement noise and the Langevin dynamic algorithm performed in the SVD domain of the known degradation matrix with the correction of the speed size. The sampling relies on an available pre-trained MMSE Gaussian denoiser. The experimental results demonstrate realistic sampling on image deblurring, super-resolution, and compressive sensing tasks.

Though the authors discuss the limitations of the proposed algorithm, in the numerical results the score function is estimated on the base of the same dataset, from which the linearly transformed and the blurred pictures come from. The resulting sampled pictures look really nice, but  which could be applications of the presented results? Would it be possible to assume a bit more realistic setting, when the source database is not available?

limitations_and_societal_impact: The authors discuss the limitations of the work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This manuscript describes a novel method for sampling from the posterior in a linear inverse problem subjected to noise for an arbitrary measurement matrix. This is achieved by combining a black-box prior (such as that derived from a minimum MSE Gaussian denoiser) whose score function is easily computable with an annealed Langevin dynamics framework. The novelty is the construction of the Langevin noise term, which guarantees that the conditional score function is tractable. In addition, the authors propose a heuristic for step size calculation inspired by Newton's method in optimization. The method is evaluated on a variety of linear inverse problems: image deblurring, super resolution, and compressive sensing. For each task, realistic results are achieved and the residual is shown to conform to the imposed statistical model.

main_review: This work proposes a novel and interesting method for the chosen task: sampling from the posterior distribution in a linear inverse problem affected by noise. The motivation of the method and the results are quite compelling. There are, however, some issues with the description of the algorithm that should be addressed. If these changes are made, I would recommend the publication of this manuscript as part of the proceedings. More detailed comments follow below.

First, the convention used for the SVD is a bit non-standard in that the singular value matrix Σ is rectangular (which results in odd expressions such as Σ^T and (Σ^†)^T). I would suggest using the convention that Σ is M×M and V is N×M. Some explanation for the rewrite in eq. (5), where y is written in terms of x-tilde instead of x would also be helpful. Similarly, it would be good to explain why it is desirable that z_T – Σn_T be white and independent of x_T-tilde. Throughout, explanations for various derivations would help the reader to follow the choices made and why. This is especially true for derivations and calculations that are relegated to the supplementary material. Here, it would be good to at least give an intuition for why the result should be true.

The most problematic part is the second half of Section 3.1, the derivation of the annealing noise term. First, the requirement that σ_i s_j ≠ σ_0 for all i, j is a bit worrisome. While it can be easily circumvented by an appropriate choice of variances σ_i, such an inequality constraint suggests an instability in the underlying relationships. The question is what happens when σ_i s_j is close to, but not equal to σ_0. While exact equality is very unlikely (especially given the floating-point representations used in practice), there is nothing preventing these values from being rather close to one another. What would happen if this were the case? Would convergence suffer? Do the calculations come out the same, with factors cancelling out in the limit?

Continuing, the notation i_1 is a bit odd. Where does the subscript one come from? Also, the dependence on j should be made clear, so that i_1 would be come i_1(j) (or simply i_j?). The definition is also only given for s_j ≠ 0. What happens for s_j = 0? This becomes relevant later (line 185) when the special case s_j = 0 is singled out, but this is in fact undefined since i_1 is not given in this case.

The derivation of the noise term itself is quite confusing. First (on line 176), it is stated that η_i is defined as a normally distributed random vector with covariance matrix equal to a multiple of the identity matrix. Then, (on line 182), it is stated that η_{T,i} (the jth component of Σ V^T η_i) is *constructed* to satisfy certain moment conditions. As far as I can tell, what the authors are trying to say here is that η_i has a certain *marginal* distribution, which is a normal distribution with the specified covariance matrix, but that it is also jointly normally distributed with z_T and that the cross-covariance matrix (between η_{T,i} and z_T) is being specified. Nonetheless, this is quite an indirect way of stating the relationship between these random variables.

This becomes more obvious after (on line 183), where the authors state that “this implies that the layers of noise … are all portions of z_T itself”. Again, what I can tease out from this is that the η_{T,i} variables are simply scaled versions of z_T in this case. I think this section would be much better served by explicitly constructing η_i (or η_{T,i}) from z_T (plus an additional independently distributed component). Not only would this be easier to follow, but it would more clearly illustrate the purpose of the construction. The same comment applies to eq. (6). Simply stating that “it can be shown that” (and leaving the calculation to the reader) reduces the clarity of the argument. If the calculations have to be relegated to the supplementary material, at least a brief motivation would be useful here.

Some minor comments follow:

– On line 80, what does it mean for “the entries in the derived score switch mode”? There has been no discussion of modes prior to this.

– It would be helpful for readers less familiar with Langevin dynamics to explain on line 130 why the conditional score function would not be tractable in the general case, since this is a problem that is solved by the proposed algorithm.

– In the problem formulation at the beginning of Section 3.1, it would be good to mention the use of a prior to complete the description of the statistical model (since this is needed to define the posterior).

– The superscript 2 on line 144 is oddly placed, coming right in the middle of some mathematical expressions. It would be better to place it at the end of the sentence.

– In many places (such as lines 179 and 194), the word “white” is used when something more like “heteroscedastic” is meant. A white noise model implies that the components are uncorrelated and that variances of all the components are equal. While this may be the case for η_i, it is not true for Σ V^T η_i. In this case, the covariances are zero, but the variances are different.

– In Sections 3.1 and 3.2, the authors switch between i ≥ i_1, σ_i s_j < σ_0 and s_j < σ_0 / σ_i, all of which are equivalent conditions. I suggest the authors pick one of these characterizations and use it throughout to reduce confusion.

– When giving the step size heuristic in eq. (12), it would be good to provide a brief motivation for why the data term does not enter into the Hessian approximation, since the expression of the score function in eq. (10) indicates that this would be the case. As stated previously, it would also be good to provide some intuition for why these step sizes make sense.

– There is a space missing between the numbers and “dB” on lines 268 and 271.

– What does it mean that “SNIPS does not handle general content images”?

– Several titles in the bibliography are improperly capitalized (probably missing some {} in the BibTeX file), including [3], [7], [8], [14], [21], [24], [30], [35], [36], [40], [48], [50], [53], [54], [55], [56], [57].

UPDATE:
After reading the other reviews and the author responses, I have decided to lower my score from 7 to 5 due to the lack of comparisons to established baselines, which make it difficult to establish the usefulness of the method.
limitations_and_societal_impact: The authors discuss the limitations and necessary extensions in Section 6 of their work. These are reasonable and highlight areas of improvement that should be pursued. As this is a theoretical work, there is no expectation of negative societal impact and the authors have accordingly not discussed it.
review_title: null

Meta-review: This paper solves linear inverse problems via an approximate MMSE estimator using pre-trained Gaussian denoisers. The results look very good since the paper uses NCSNv2 which is an excellent generative model. 

The two major problems are: 
There are really no comparisons with previous experimental baselines. 
This is a major limitation for any scientific paper and the authors need to strengthen their evaluation section by discussing how prior work performs for the problems they solve. There are dozens of papers that solve deblurring, inpainting and compressed sensing problems using deep generative models. (Many papers use NCSNv2 and the more updated Score_SDE by Song et al. for various inverse problems and many others use other types of deep generators). 

Typically visual comparisons and comparisons in MSE and SSIM would help the readers understand when the current method outperforms previous work. 

Further, the technical contribution of the paper was actually not clear to the reviewers. We would encourage the authors to clarify their presentation based on the reviewer feedback and revise their manuscript. 

Decision: Accept (Poster)