Dear Reviewer HCev, we would like to thank you for taking the time to review our paper. We are happy that you found our paper interesting. Below we address your main concerns.

(W1) While it is true that $p_{\ell_k | k+1} ^\theta(\cdot | x_{k+1})$ is Gaussian, we emphasize that even in the case of linear inverse problems, the DPS approximation yields $\hat{g}_{\ell_k} ^\theta(x _{\ell})$ $=\mathcal{N}(y; A \hat{m}^\theta _{0|\ell_k}(x _{\ell_k}), \sigma^2 _y I)$ (or $p^\theta _{\ell_k}(y|\cdot)$ with the new notation). The mean of this Gaussian distribution is non-linear in $x _{\ell_k}$ which means that $\hat\pi^\theta _{\ell_k|k+1}(\cdot |x _{k+1})$ is not necessarily a Gaussian distribution. It would be the case only if the mean in the potential $\hat{g}^\theta _{\ell_k}(x _{\ell_k})$ were linear in $x _{\ell_k}$. Finally, further non-linearities in the mean of the potential arise when dealing with non-linear inverse problems as considered in the paper. Thus, the Gaussian variational approximation, or any sort of approximation, is necessary.

(W2) This is a fair point. In our methodology we try to approximate, at each step, the conditional distribution $\pi_{\ell_k | k+1}(\cdot | x_{k+1})$ with $\ell_k$ much smaller than $k$. This distribution can be unimodal or multi-modal with anisotropic structure in the modes, as opposed to the transition $\pi_{k|k+1}(\cdot | x_{k+1})$ which is well-approximated when the covariance of the Gaussian approximation is isotropic. Let us give an example. Assume that the target distribution is $\pi = \mathrm{N}(\mu, \Sigma)$. We can compute exactly the covariance $Cov(X_\ell| X_{k+1})$ of the backward transition $\pi_{\ell|k+1}(\cdot | x_{k+1})$ for any $\ell \in [0:k]$. It is given by

$$Cov(X_\ell| X_{k+1}) = (\alpha_\ell - \alpha_{k+1}) \bigg[(1 - \alpha_{k+1}) \Sigma^{-1} + \mathrm{I}\bigg]^{-1} + \frac{(1 - \alpha_\ell)(1 - \alpha_{k+1} / \alpha_\ell)}{1 - \alpha_{k+1}} \mathbf{I}$$

It is seen that when $\ell$ is much smaller than $k$ the covariance can be very different from an isotropic one. To account for this, we allow more flexibility in our variational approximation by optimizing the diagonal terms and, in practice, we found that this improves the performance. Of course, optimizing over the full covariance matrix would be better, however, this is not feasible in practice because of the large size of the matrix in high dimension setups.

(W3) As far as we are concerned, the only method we know of that is close to our methodology when $\ell_k = k$ is the work in [1] that we mention in the related works section and explain how it is related. As for the other methods such as DPS, they do not exactly interpret as the case $\ell_k = k$ and more approximations are required. DPS cannot be framed as a special case of our algorithm but we can still obtain a special case that closely matches it. This is now thoroughly explained in Appendix C.3.

(W4) We now explain how the upper bound is obtained in Appendix C.1.

Regarding your questions:

(Q1) We now include an extended table including the PSNR and SSIM values in Tables 7, 8 in the appendix, as well as in the new table 9 for latent diffusion. Please note that initially we did not include the PSNR and SSIM as these provide ambiguous results that poorly reflect the actual performance of the algorithms. As an example, DDNM has the best PSNR and SSIM on the Half mask task (see tables 7 and 8), but it does not provide accurate reconstruction on ImageNet and FFHQ as seen in figures 15 and 16. See also the reconstructions of DDNM in the figures 9 to 14 the paper [1]. The LPIPS on the other hand aligns well with the qualitative results that we display. As for the FID, it requires running all the algorithms and tasks on a large number of images (1000 at least) and this is prohibitively expensive to do in our case given the number of tasks/algorithms we consider on FFHQ/latent FFHQ, ImageNet as well as the ECG dataset for which we have trained our own diffusion model.

(Q2) In order to extend our methodology to faster solvers, we require the equivalent of the identity (3.4) in the main paper. This is for example feasible for DDIM-type samples and we will add the derivation in the final version of the paper. As for other fast solvers such as EDM [2] it is not yet clear how they can be used within our methodology and we leave this for future research. Finally, please note that the other reviewers have requested some changes in the notations as well as in the presentation. We have implemented these modifications by making some important changes to section 3 so as to explain the method more intuitively. We have also added a figure to illustrate the idea behind our method.

Dear Reviewer eMe4, we would like to thank you for your comments and positive feedback regarding our paper.. Below we address your concerns:

(W1) We welcome your suggestion for using boldface for the vectors. We have now implemented this in the updated version of the paper that we have uploaded. We would also like to mention that following the suggestions by the other reviewers, we have also changed some of the notations to improve the readability and revised significantly Section 3 of the paper in order to make the presentation more intuitively accessible. In addition, we have added a Figure to illustrate the intuition.

(W2) We understand your concern about the number of test samples. In our original submission, we focus on illustrating the wide applicability of our method to different image reconstruction tasks, considering 10 different tasks. However, given our limited computational resources, we had to limit the number of test samples to 50.
Indeed, for instance, running a single task for 3 algorithms on 1k images would have required 600 GPU hours. Additionally, running fewer tasks would not highlight the strength of MGPS, which is a general algorithm that can be applied to different problems and modalities. For the time being we have sought a compromise and we have increased the sample size to 300 on a subset of the experiments, including 95% confidence intervals. The new results align with our initial findings; see the general comment above. Note that we have run these experiments on what we consider to be the most difficult tasks but we are currently running experiments reaching 1000 samples for the final version of the paper. Given the confidence intervals, we expect to see no significant difference with what we currently have.
Finally, we would like to insist that our set of experiments is designed (i) to show that our method provides a good approximation of the posterior distribution, and (ii) to demonstrate its wide applicability. Regarding the first point, we compare with the exact posterior in the Gaussian mixture example. Regarding the second one, we have considered 10 various tasks for the image experiments, compared against 7 competitors, and used both pixel space and latent space diffusion adding up to 3 different priors. Then, we have also considered the ECG data experiment, for which we have trained our own generative model, to show that our method works on different modalities. We ensured to run the experiments for all the competitors and refrained from using the values given in the papers and so this effectively limited the number of images we initially considered for evaluation, due to our limited computational budget.

(W3) We also include the PSNR/SSIM and have updated the tables in the paper; see Table 7 and Table 8. Regarding these metrics, we would like to insist that our method performs well on the three metrics at the same time. On the other hand, while DDNM achieves the best PSNR, it does not perform well in LPIPS. In fact, higher PSNR does not translate to good reconstructions as evidenced by Figure 13 and Figure 15. Similarly, other authors have observed the same reconstructions for DDNM; see for example the figures 9 to 14 in [1].
Finally, we did not include the FID since we need a much larger number of samples to get a robust estimate. Still, since we are now in the process of increasing the sample size up to a regime where accurate estimation of FID is possible, we will make sure to include it in the final version of the paper once the experiments are finished running. We believe that by considering different types and extensive experiments, especially a toy experiment in which the posterior is available in closed form, we have provided strong evidence in favor of our method.

[1] Zhang, Guanhua, Jiabao Ji, Yang Zhang, Mo Yu, Tommi S. Jaakkola, and Shiyu Chang. "Towards coherent image inpainting using denoising diffusion implicit models." (2023).

Dear Reviewer,

Thank you for your prompt response and for raising your score. We understand your concern about seeing some experiments with 1000 images, especially for computing the FID, as "fewer experiments are not a bad thing if it means more robust testing." To address this, we have selected two tasks that we consider the most challenging and have tested our algorithm against the closest competitors on 1000 image on the three priors: half mask and JPEG. Below, we provide the four metrics (including the FID), and it is evident that MGPS outperforms all reported competitors on the FID by a noticeable margin. We hope this addresses your concerns. Please let us know if there are any other tasks you would like us to evaluate before the end of the rebuttal period to address all of your concerns and ensure all promises are fulfilled.

HALF MASK

JPEG2

Latent diffusion

Dear Reviewer bHyn, we would like to thank you for taking the time to review our paper. We are happy you found that our paper has good merit. Below we address your concerns.

(W1-2) Thank you for this feedback. We have implemented all your suggestions in the revised version paper which is now updated in openreview. Notably we have: modified Section 3 so that the idea is explained more intuitively. Now we start the paragraph “Midpoint decomposition” with a straight-to-the-point explanation of what our method tries to achieve. The explanation is accompanied with a visual explanation in Figure 1. We thank the reviewer for this good point. changed the notations. The $g$ function has been replaced by a likelihood function $p(y|\cdot)$. Reviewer eMe4 has also suggested using boldface for the vectors and we believe that it also improves the readability. You have also suggested adding the $y$ conditioning to $\pi$, which is a sensible idea. Still, if we implement this modification we would also need to add it to the conditional distributions to be consistent in the notations, i.e. $\pi_{i|j}(x_i | x_j)$->$\pi_{i|j}(x_i | x_j, y)$ and such. As we believe that this will lead to notational overload we decided not to implement it. Please check out the modifications in the paper and let us know if you think we should make any further adjustments.

(W3-4) We have prioritized running a more diverse set of experiments (10 tasks on images, 2 tasks on ECG) on the 7 competitors at the cost of using a smaller number of sample images, due to computational constraints. In the updated version of the paper we provide extended results on the most difficult tasks and on a larger set of images; more precisely we have drawn without replacement 300 images from both the ImageNet and FFHQ validation datasets. Finally, following your suggestion we now also include PSNR and SSIM. These new results are consistent with the initial findings of the paper. Please see the main comment. Our method performs well on the three metrics at the same time. While competitors such as DDNM or RedDiff may have in some cases a larger PSNR or SSIM, they still exhibit a large LPIPS, resulting in subpar reconstructions, as evidenced in the appendix Figures 13, 14 and 15 for example.

(W5) In all the experiments we use DPS and PGDM with n=1000 steps. This can be checked in the configuration files of the code we have provided in the supplementary material, namely files dps.yaml and pgdm.yaml in configs/experiments/sampler/ folder. The sentence in the experiment Section was ambiguous and is now fixed. We meant that the runtime of our algorithm with $n=300$ steps is larger than the runtime of DPS and PGDM.

Thank you for the references, we were aware of only one of these works.

Note on ECG:

Thank you for your comment. We understand that the introduction of the ECG application may seem sudden. To clarify, the aim of this experiment is to explore the application of posterior sampling algorithms beyond classical image-related tasks to demonstrate their generalizability and societal impact.

Medical Context: Cardiovascular diseases account for approximately 1/3 of global deaths. Better detection could improve management of these conditions. Wearable devices like SmartWatches have a good potential for improving diagnosing cardiovascular diseases, as patients may experience brief episodes of symptoms (e.g., paroxysmal Atrial Fibrillation) that may not be detected during a doctor's visit. Using these monitors for extended periods can help ensure a timely and accurate diagnosis. However, they only provide a partial view (lead I instead of 12 leads) of cardiac electrophysiology.

Challenge of Classification from Incomplete ECGs: A recent study showed that the Apple Watch correctly identified atrial fibrillation (AF) in only 34 out of 90 episodes [1]. We propose completing ECGs to 12 leads using posterior sampling algorithms to address the issue of incomplete ECGs. To our knowledge, we are the first to use ECG completion with posterior sampling for detecting anomalies in incomplete ECGs. We hope this clarification helps to better understand the motivation behind our choice of the ECG application and the importance of our work for the posterior sampling community. We will add a comment on this in the final version of the paper. Please feel free to suggest any additional changes you deem necessary.

[1] Dhruv R. Seshadri and Barbara Bittel and Dalton Browsky and Penny Houghtaling and Colin K. Drummond and Milind Y. Desai and A. Marc Gillinov. Accuracy of Apple Watch for Detection of Atrial Fibrillation, Circulation (2020), https://doi.org/10.1161/CIRCULATIONAHA.119.044126

Dear Reviewer U6Fn, we would like to thank you for taking the time to review our paper and for the positive feedback. Below we address your concerns.

(W1) We agree with the reviewer that it is valuable to explore the impact of $\eta$ on other tasks and to obtain further theoretical results. The example of Gaussian prior with linear inverse problem is appealing as it ensures that all terms (guidance and denoising densities) remain Gaussian, enabling an explicit form of the posterior to be obtained as shown in Appendix B. However, this advantage does not extend to more general priors and nonlinear inverse problems, where analysis becomes more complex, even in relatively simple cases such as Gaussian mixtures. While working on the image experiments, specifically on the ImageNet dataset, we found empirically that the optimal values ($\eta \approx 0.5)$ we obtained in the Gaussian example also bring significant improvements for the image reconstructions, compared to setting $\eta \approx 1$ or $\eta \approx 0$. We are currently working on adding these empirical findings, and we will include the same in the appendix of the paper as soon as they are completed.

(W2) A theoretical analysis of the algorithm would definitely be valuable. Deriving the dependence of the Wasserstein-2 distance on the choice of the sequence, which could then be optimized, is challenging even in the simple Gaussian case. In the more general case, deriving a bound on the KL divergence between the posterior and the marginal of the surrogate model that is informative wrt the choice of the midpoint sequence, first requires a proper study of the DPS approximation. Specifically, we must bound the discrepancy between the true potential $g_k$ (now $p_k(y|\cdot)$ with the new notation), and its approximation $g(m^\theta _{0|k}(x_k))$. Then, we would need to use this analysis to bound the one-step KL divergence between the true posterior transition and the surrogate transition. We have already taken some steps in this direction and believe that further technical and non-trivial work is required. Overall, we believe that such an analysis is a very good future direction of research and is out of the scope of the current paper, whose aim is to deliver a convincing proof of concept.

(W3) We would like to assure the reviewer that we prioritized using the code and hyperparameters provided by the authors of the original papers and fine-tuned each method for each dataset as needed. In some instances, we have even contacted the authors to check that we are correctly using their code. Furthermore, we have included the code used for our experiments with our submission. First, while it may appear that some of the methods underperform on some tasks/images compared to the original publications, as you point for Figures 13 and 15, please note that they still produce competitive reconstructions on others; see for example Figure 15, 18, and 23 in the updated version of the paper. Second, we would like to stress that other papers report similar reconstructions on the same tasks. For example, see Figure 10,12 in [1], and Figure 9, 10 in [2], which display similar patterns. That being said, we would also like to stress that these discrepancies appear more frequently on the ImageNet dataset than the FFHQ one. This can be explained by the fact that ImageNet is notoriously challenging due to its diversity, encompassing 1000 classes. This also seems to happen on one of the most difficult tasks, namely the half mask one. The reviewer is right in pointing out these disparities. In the updated version of the paper, which you can check out, we comment on the same; see Section D.6.

Results on FFHQ

LPIPS

PSNR

SSIM

Results on ImageNet

LPIPS

PSNR

SSIM

Result on FFHQ with LDM

LPIPS

PSNR

SSIM

We would like to thank the reviewers once again for their insightful comments.

We have finalized the previously mentioned experiments. To strengthen our conclusions and calculate the FID, we reran MGPS and the two closest competitors on 1000 images for the following five tasks: half mask, JPEG, motion deblur, nonlinear deblur, and high dynamic range, using the three priors (ImageNet, FFHQ, FFHQ latent). The tables presented below show that MGPS significantly outperforms the other competitors, including for the FID, with no significant change in other metrics compared to what we calculated on a smaller dataset.

We believe we have addressed all the reviewers' concerns. However, we remain open to any additional feedback that could further improve the quality and robustness of our paper and would be happy to address any further questions before the end of the rebuttal period.