Diffusion Posterior Sampling for Linear Inverse Problem Solving: A Filtering Perspective

This paper provides a link between Bayesian posterior sampling and Bayesian filtering in diffusion models for linear inverse problems. In general, exact posterior sampling is intractable. To overcome this difficulty, this paper introduces a diffusion process to the measurement vector and incorporates the information of the measurement by Bayesian filtering methods in the backward process. In the ideal case, the exactness of the proposed method is theoretically guaranteed, which is realized by the sequential Monte Carlo method using infinitely many particles. Numerical experiments show that the performance of the method is as good as those of the SOTA methods.

This paper proposed a filtering perspective on the linear inverse problem with diffusion models, which yields a novel FPS algorithm. Moreover, this paper gave a theoretical proof that that the FPS algorithm correctly samples from the Bayesian posterior distribution as the number of particles approaches infinity.

This work introduces an efficient, asymptotically accurate diffusion sampling algorithm for linear inverse problems, linking Bayesian posterior sampling to Bayesian filtering in diffusion models, using sequential Monte Carlo methods for filtering, requiring no model re-training, and outperforming or matching existing methods in tasks like image inpainting, super-resolution, and motion deblur.

This paper presents an SMC algorithm for sampling from the posterior of an inverse problem where the prior distribution distribution is a diffusion model, which is a natural way of sampling from the posterior of the diffusion model, due to the sequential structure of the sampling procedure. The resulting procedure does not require any additional training and, as claimed by the authors, samples from the posterior in the limit of infinite particles.

We thank all reviewers for their valuable feedback. We have updated our paper with improvements summarized below:

1. We improved the overall writing quality of our paper with better motivation, exposition, and fixing several typos in the draft.
2. We included a discussion with several additional papers in the introduction, background, and additionally provided one related work paragraph in appendix.
3. We summarized all assumptions for Proposition 4.1 in Assumption 4.1. Unlike before, we clearly introduce these assumptions and compare them with other relevant papers.
4. In Section 5.3, ``Ablation study: Influence of the particle size", we added an analysis on the relationship between the running time of FPS-SMC and the particle size $M$. We also made a table showing that the wall-clock time for running FPS-SMC is approximately $t\propto \sqrt{M}$. We provide additional experimental details in Appendix F.2.

Below we address concerns shared by multiple reviewers.

Q1: Generalization to nonlinear measurements

A: The focus of this work is on linear inverse problems. We would like to emphasize that linear inverse problems are important in their own right. As demonstrated in our paper, they have numerous important applications including image inpainting, super resolution and deblurring.

Extension to nonlinear measurements is non-trivial for FPS and FPS-SMC. When the measurement operator is non-linear, there is no explicit formulation for $p(x_k \mid y_k, x_{k+1})$, and generating the $\{y_k\}$ sequence without $\{x_k\}$ is challenging. That said, it may be possible to linearize such operators for local approximations to enable FPS and FPS-SMC, which we leave for future work.

Q2: FPS-SMC requires heavy computational cost since it uses multiple particles

A: It is correct that the computational cost for FPS-SMC grows in proportion to particle size. However, modern GPUs excel at parallel computation, and the increase in running time can be significantly smaller than the growth in computational cost. To provide more clarity, we added a paragraph and a table in our revised draft to compare the wall-clock time of FPS and FPS-SMC with multiple diffusion-based solvers for inverse problems (in the appendix). Empirically, we observe that the wall-clock time $t$ of FPS-SMC is approximately $t\propto \sqrt{M}$, where $M$ denotes the number of particles. In practice, we recommend FPS which is twice as fast as DPS, but keeps most of the accuracy of FPS-SMC without requiring more particles.

Q3: Adding more literature review

A: In our initial submission, we placed the related work section in Appendix A due to page limit. In the revised draft, we have included additional discussion on relevant literature in introduction and related work, involving some concurrent work like [1,2]. We have also polished our introduction, background section in the main text.

Q4: Code release

A: We will publish code upon publication.

[1] Gabriel Cardoso, Yazid Janati El Idrissi, Sylvain Le Corff, and Eric Moulines. Monte carlo guided diffusion for bayesian linear inverse problems. arXiv preprint arXiv:2308.07983, 2023. [2] Luhuan Wu, Brian L Trippe, Christian A Naesseth, David M Blei, and John P Cunningham. Practical and asymptotically exact conditional sampling in diffusion models. arXiv preprint arXiv:2306.17775, 2023.

The reviewers agree that there is novelty in the proposed method, even though there are concerns about the incremental improvement over baselines and the lack of comparison with more recent works. The theoretical analysis can also benefit from making the assumptions more realistic.

Accept (poster)