📊 statistics

Provable diffusion-based posterior sampling for linear inverse problems via DDIM

This paper introduces \pddim, a simple and efficient algorithm that achieves provable convergence to the Bayesian posterior for linear inverse problems by performing coordinate-wise DDIM updates that dynamically switch between diffusion priors and measurement-based predictions based on signal-to-noise ratios.

Original authors: Yuchen Jiao, Na Li, Changxiao Cai, Yuxin Chen, Gen Li

Published 2026-07-22

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yuchen Jiao, Na Li, Changxiao Cai, Yuxin Chen, Gen Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a giant, blurry puzzle. You have a picture of the final result in your head, but the pieces you've been handed are missing, smudged, or mixed up with static noise. This is the world of "inverse problems," a branch of science where researchers try to figure out what the original, perfect image looked like based on a damaged or incomplete version. For decades, scientists have used clever mathematical tricks to guess the missing parts, but these tricks often relied on simple, rigid assumptions about what the picture should look like, like assuming everything is made of straight lines or smooth curves.

Enter "diffusion models," a newer, super-smart type of artificial intelligence that acts like a master artist who has studied millions of photos. Instead of being told "draw a straight line," this AI has learned the complex, messy, and beautiful rules of how real-world images naturally form. It knows that a cat's ear usually has a certain shape, or that a sunset has a specific gradient of colors. Now, the big question for scientists is: How do we use this super-smart AI artist to fix our blurry puzzle pieces without messing up the parts we already know are correct? The challenge is balancing the AI's creative guesses with the hard facts of the measurements we actually have.

This paper introduces a new, clever method called Posterior-DDIM to solve exactly that puzzle. The authors propose a simple but powerful strategy: instead of treating every part of the image the same way, they look at the "signal-to-noise ratio" (SNR) for each specific direction of the image. Think of the image as being made of many different threads. Some threads are very clear and strong (high SNR), while others are weak and covered in static (low SNR).

The authors' main finding is that they can split the job into two distinct modes based on how clear each thread is. For the threads where the measurement is strong and clear, the algorithm simply trusts the data, injecting the observed information directly into the image. For the threads where the data is weak or missing, the algorithm ignores the noisy data and lets the AI artist's "diffusion prior" (its internal knowledge of what images look like) take the lead. It's like having a team of restorers: when a piece of the painting is clearly visible, they carefully trace the existing lines; when a piece is completely gone, they use their expert knowledge to paint in a plausible new section that fits the style.

The paper proves mathematically that this method works. Under specific conditions—like using a very fine step-by-step process and having a perfect AI model—their method is guaranteed to converge to the true, correct answer. In other words, they didn't just guess; they showed that if you follow their steps, you will eventually get the right picture. They also ran extensive experiments on real-world tasks like fixing blurry photos, removing noise, and filling in missing parts of images (inpainting). The results show that their method consistently outperforms existing techniques, often achieving the best scores in multiple categories like sharpness and visual realism.

Crucially, the authors argue against the idea that you need complex, heavy, and slow calculations to get these results. Many previous methods tried to force the AI to obey the measurements by constantly recalculating gradients or using thousands of random guesses, which was computationally expensive. The authors show that by simply adjusting the standard AI update rules in a "coordinate-wise" manner (treating each direction separately), you can get the same or better results with much less effort. They explicitly rule out the need for these heavy computational overheads, proving that a lightweight, efficient approach is not only possible but superior.

The confidence in these results is high. The authors provide rigorous mathematical proofs showing that their sampler converges to the correct Bayesian posterior (the statistically perfect answer) as the process gets finer. Furthermore, their empirical results on datasets like CelebA and ImageNet demonstrate that this method is not just a theoretical curiosity but a practical winner, beating other top-tier algorithms in the majority of tests. They even explored how different settings affect the outcome, finding that a specific balance between "deterministic" (following the data) and "stochastic" (adding creative randomness) updates leads to the best performance. Ultimately, this paper suggests that by listening to the data when it's loud and trusting the AI's intuition when the data is quiet, we can solve some of the trickiest image restoration problems with surprising simplicity and speed.

Technical Summary: Provable Diffusion-Based Posterior Sampling for Linear Inverse Problems via DDIM

Problem Statement

The paper addresses the challenge of solving noisy linear inverse problems of the form $Y = AX_0 + \varepsilon$ , where $X_0 \in \mathbb{R}^d$ is an unknown signal, $A \in \mathbb{R}^{n \times d}$ is a known linear measurement operator, and $\varepsilon \sim \mathcal{N}(0, \sigma^2 I_n)$ is Gaussian noise. The goal is to generate samples from the Bayesian posterior distribution $p_{X_0|Y}$ , conditioned on the observation $y$ .

While diffusion models have emerged as powerful, data-driven priors for capturing complex signal distributions, existing methods for posterior sampling often suffer from one of two limitations:

Lack of theoretical guarantees: Many heuristic approaches (e.g., projection-based methods or approximate score corrections) lack rigorous proof that their generated samples converge to the true posterior.
Computational overhead: Methods that attempt to approximate the posterior score or use Sequential Monte Carlo (SMC) often incur prohibitive computational costs, such as requiring gradient computations of score functions or a large number of particles.

Methodology: Posterior-DDIM

The authors propose Posterior-DDIM, a simple and efficient algorithm that performs posterior sampling by adapting the standard Denoising Diffusion Implicit Models (DDIM) sampler. The core innovation lies in a singular value decomposition (SVD)-based partitioning of the signal space, where updates are tailored to the relative strength of the observation signal-to-noise ratio (SNR) versus the diffusion SNR.

1. SNR-Guided Partitioning

Using the SVD of the measurement matrix $A = U\Sigma V^\top$ , the problem is decoupled into scalar inference problems along each singular direction $v_s$ . The authors define a threshold time $\tau_s$ for each direction where the diffusion SNR ( $\alpha_t/\sigma_t$ ) equals the observation SNR ( $\Sigma_{ss}/\sigma$ ). Based on this, the singular directions are partitioned at any time $t$ into three groups:

Measurement-dominated directions ( $S^{meas}_t$ ): Directions where the observation SNR exceeds the diffusion SNR ( $t \ge \tau_s$ ).
Prior-dominated observed directions ( $S^{prior}_t$ ): Directions where the observation SNR is lower than the diffusion SNR ( $t < \tau_s$ ), but the direction is still observed.
Unobserved directions ( $S^c$ ): Directions in the null space of $A$ where no measurement information exists.

2. Coordinate-Wise Update Rules

The algorithm applies distinct update rules to these groups, requiring only lightweight modifications to the standard DDIM update:

For $S^{meas}_t$ (Measurement-dominated): The algorithm bypasses the learned prior and directly injects a calibrated noisy version of the observation. Specifically, it generates the coordinate $v_s^\top \hat{X}_{t_{i+1}}$ using the auxiliary forward process defined by the measurement $y$ , ensuring the marginal distribution matches the forward diffusion process projected onto that direction.
For $S^{prior}_t$ (Prior-dominated observed): The algorithm follows the standard DDIM dynamics driven by the learned data predictor $\mu_t(\cdot)$ . In the general case where singular values are not identical, a correction term is added to the predictor to account for the varying singular values, ensuring the update remains consistent with the conditional posterior.
For $S^c$ (Unobserved): These coordinates are sampled entirely from the learned diffusion prior conditioned on the observed coordinates. To encourage sufficient exploration of the unobserved subspace, a larger stochasticity parameter $\eta_1$ is used, making the update more Langevin-like.

3. Stochasticity Parameters

The method utilizes two stochasticity parameters, $\eta_0$ and $\eta_1$ , controlling the noise injection in the DDIM updates for $S^{prior}_t$ and $S^c$ , respectively.

$\eta_0$ is kept small (often 0) to maintain a deterministic-like update for observed directions where the prior is the primary guide.
$\eta_1$ is set to be sufficiently large to ensure the unobserved subspace is explored effectively, as its distribution is determined solely by the prior.

Key Contributions

Algorithmic Simplicity: The proposed method reduces posterior sampling to a sequence of simple, coordinate-wise DDIM updates. It explicitly incorporates the measurement model without requiring complex projection steps, likelihood gradient computations, or retraining of the diffusion model.
Theoretical Guarantees: The paper establishes asymptotic posterior correctness. Under the assumption of an exact diffusion prior and sufficiently fine time discretization, the authors prove that the distribution of the samples generated by Posterior-DDIM converges to the true Bayesian posterior $p_{X_0|Y}$ in total variation distance. This holds for both the special case of identical singular values and the general case with arbitrary singular values.
Empirical Performance: Extensive experiments on image restoration tasks (inpainting, super-resolution, Gaussian deblurring, and compressed sensing) demonstrate that Posterior-DDIM outperforms existing diffusion-based samplers (including DPS, DDRM, DDNM+, and ProjDiff) on the majority of evaluation metrics (PSNR, SSIM, LPIPS, and FID).

Experimental Results

The authors evaluated the algorithm on CelebA and ImageNet datasets. Key findings include:

Superiority: Posterior-DDIM achieved the best performance on at least three of the four metrics in most tasks and on at least two metrics in every task considered.
Robustness: The method consistently outperformed baselines across different noise levels and degradation types.
Efficiency: The algorithm requires only 100 function evaluations (NFE) to reach stable performance, comparable to or faster than other methods that often require significantly more steps (e.g., 1000 NFE for DPS).
Hyperparameter Sensitivity: The experiments showed that setting $\eta_0 = 0$ (deterministic update for prior-dominated directions) and a sufficiently large $\eta_1$ (e.g., 16 or 32) yields optimal results.

Significance and Claims

The paper claims to provide a principled and provable framework for integrating diffusion priors with linear measurement models. By converting the complex problem of posterior sampling into simple, direction-wise DDIM updates, the authors bridge the gap between theoretical rigor and practical efficiency.

The significance of this work is highlighted in its ability to:

Offer rigorous theoretical support for DDIM-type samplers in inverse problems, addressing the lack of convergence guarantees in many heuristic methods.
Provide an easy-to-implement solution that preserves the computational efficiency of standard diffusion samplers while explicitly handling the measurement model.
Demonstrate that posterior consistency can be achieved without the computational prohibitions of Sequential Monte Carlo or the heuristic approximations of projection-based methods.

The authors note that while the current work focuses on linear inverse problems, extending this framework to nonlinear settings and characterizing the convergence rates are natural directions for future research.