Linearly Constrained Diffusion Implicit Models
Vivek Jayaram, Ira Kemelmacher-Shlizerman, Steven M. Seitz, John Thickstun · 2024
Read Linearly Constrained Diffusion Implicit Models by Vivek Jayaram, Ira Kemelmacher-Shlizerman, Steven M. Seitz, John Thickstun (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-00359.txt.
Description
Abstract We introduce Linearly Constrained Diffusion Implicit Models (CDIM), a fast and accurate approach to solving noisy linear inverse problems using diffusion models. Traditional diffusion-based inverse methods rely on numerous projection steps to enforce measurement consistency in addition to unconditional denoising steps.
Catalog record
| CREATOR | Vivek Jayaram, Ira Kemelmacher-Shlizerman, Steven M. Seitz, John Thickstun |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-00359
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Linearly Constrained Diffusion Implicit Models Vivek Jayaram, Ira Kemelmacher-Shlizerman, Steven M. Seitz, John Thickstun Abstract We introduce Linearly Constrained Diffusion Implicit Models (CDIM), a fast and accurate approach to solving noisy linear inverse problems using diffusion models. Traditional diffusion-based inverse methods rely on numerous projection steps to enforce measurement consistency in addition to unconditional denoising steps. CDIM achieves a 10–50× reduction in projection steps by dynamically adjusting the number and size of projection steps to align a residual measurement energy with its theoretical distribution under the forward diffusion process. This adaptive alignment preserves measurement consistency while substantially accelerating constrained inference. For noise-free linear inverse problems, CDIM exactly satisfies the measurement constraints with few projection steps, even when existing methods fail. We demonstrate CDIM’s effectiveness across a range of applications, including super-resolution, denoising, inpainting, deblurring, and 3D point cloud reprojection. Code and an interactive demo can be found on our project website. 1 1 1 https://grail.cs.washington.edu/projects/cdim/ 1 Introduction Recovering an unknown signal from noisy linear measurements is a fundamental challenge encompassing tasks like super-resolution, inpainting, and denoising. These are examples of linear inverse problems, for which we observe a partial measurements {\mathbf{y}}\in\mathbb{R}^{d} that was generated through a linear operator {\mathbf{A}}\in\mathbb{R}^{d\times n} applied to a signal {\mathbf{x}}\in\mathbb{R}^{n} . In the noisy case, measurements {\mathbf{y}} are corrupted with noise sampled i.i.d. from a gaussian distribution with variance \sigma_{y}^{2} : {\mathbf{y}}={\mathbf{A}}{\mathbf{x}}+\bm{\sigma},\quad\text{ where $\bm{\sigma}\sim\mathcal{N}(0,\sigma_{y}^{2}\mathbf{I})$} (1) We aim to use a pretrained diffusion model ( Ho et al., 2020 ) as a prior to solve these underdetermined inverse problems. However, adapting diffusion models to solve inverse problems has traditionally presented two key challenges. First, recovering the original signal from partial measurements is computationally expensive, requiring numerous additional network evaluations at each step to guide the diffusion towards the measurement constraint. Second, we would like to guarantee that the constraints are met to arbitrary precision in the noiseless case, a difficult task when trying to reduce overall steps. Figure 1 : We show several applications of our method including image colorization, denoising, inpainting, and sparse recovery. We highlight the fact that we can handle general noise distributions, such as Poisson noise, and that our method runs in as little as 3 seconds. A common approach to diffusion for inverse problems, used by methods like Diffusion Posterior Sampling (DPS) ( Chung et al., 2022b ) and others works ( Chung et al., 2024 ; Zhu et al., 2024 ) , is to alternate unconditional diffusion steps with projection steps on the measurement error: \nabla_{{\mathbf{x}}_{t}}\|{\mathbf{A}}\hat{\mathbf{x}}_{0}({\mathbf{x}}_{t})-{\mathbf{y}}\|^{2} , where \hat{\mathbf{x}}_{0}({\mathbf{x}}_{t}) is an estimate of the posterior mean \mathbb{E}\left[{\mathbf{x}}_{0}|{\mathbf{x}}_{t}\right] . However, the optimal number and size of these projection steps is difficult to determine as care must be taken to ensure that (1) the steps are sufficient to converge on the measurement criteria, (2) unnecessary projection steps do not increase inference time, and (3) large step sizes do not cause divergence or pull the iterate {\mathbf{x}}_{t} out of distribution. In light of these challenges, methods like DPS opt for many small projection steps which each require a pass through the model. Therefore, despite advances in accelerating unconditional sampling, reliance on numerous small projection steps still limits the speed of inference under constraints. We propose linearly constrained diffusion implicit models (CDIM) to address these challenges. CDIM is a new algorithm for projection-based DDIM sampling that can generate images satisfying measurement constraints under highly accelerated sampling schedules. Our key insight is to guide the number and size of the projection steps with the known distribution of \|{\mathbf{A}}{\mathbf{x}}_{t}-{\mathbf{y}}\|^{2} under the forward noising process given {\mathbf{y}} . This is a tractable chi-squared distribution, and we show that forcing \|{\mathbf{A}}{\mathbf{x}}_{t}-{\mathbf{y}}\|^{2} to stay within a plausible region similarly enforces the optimization target \|{\mathbf{A}}\hat{{\mathbf{x}}}_{0}({\mathbf{x}}_{t})-{\mathbf{y}}\|^{2} to stay within a plausible region under the forward noising process. Notably the former is computable without a network evaluation, allowing us to apply strategies like binary search or line search on step size without costly overhead. We emphasize that the speedup of CDIM does not simply come from adopting an accelerated unconditional DDIM schedule, but rather from a smarter projection strategy that greatly reduces the number of projection steps required for constrained sampling. This allows outputs to match partial observations under accelerated sampling without introducing a large number of additional network evaluations. In contrast, works such as Zhu et al. (2024) use DDIM as a sampling strategy yet still require 200 additional network evaluations for constrained sampling, showing that DDIM alone is not enough to accelerate the entire proecess. To further demonstrate this, we present qualitative examples that simply using DPS with DDIM accelerated sampling yields blurry or divergent results, even when the projection step size is tuned for optimal performance. Furthermore, CDIM exactly recovers noiseless measurements, even for out-of-distribution inputs (impossible with DPS), while requiring 10-50x fewer projection steps. Under Gaussian measurement noise, our step size criterion naturally generalizes from the noiseless case without introducing additional network evaluations. We further extend CDIM to handle Poisson noise through a reformulation based on Pearson residuals. Empirically, CDIM achieves high-quality reconstructions in under 2.5 seconds, whereas prior methods such as DPS and MCG ( Chung et al., 2024 ) require over 70 seconds. Across tasks including super-resolution, box inpainting, deblurring, and random inpainting, CDIM delivers comparable or superior reconstruction quality while operating an order of magnitude faster. 2 Related Work Diffusion models ( Ho et al., 2020 ) have emerged as powerful generative models, building upon early work in nonequilibrium thermodynamics ( Sohl-Dickstein et al., 2015 ) and implicit models ( Mohamed and Lakshminarayanan, 2017 ) . Denoising Diffusion Implicit Models (DDIM) ( Song et al., 2021 ) was a notable work that improved the efficiency of diffusion sampling through non-markovian sampling. This was further advanced through stochastic differential equations ( Song et al., 2020 ) and numerical ODE solvers like PNDM ( Liu et al., 2021 ) . Applying diffusion models to inverse problems has been an active research area. DPS ( Chung et al., 2022b ) was a notable method that uses alternating projection steps to guide the diffusion process. DDNM ( Wang et al., 2022 ) , DDRM ( Kawar et al., 2022 ) , SNIPS ( Kawar et al., 2021 ) , and PiGDM ( Song et al., 2023a ) use linear algebraic approaches and singular value decompositions. Techniques such as DMPS ( Meng and Kabashima, 2022 ) , FPS ( Dou and Song, 2023 ) , LGD ( Song et al., 2023b ) , DPMC ( Zhu et al., 2024 ) , and MCG ( Cardoso et al., 2023 ) , and DAPs ( Zhang et al., 2025 ) focus on likelihood approximation for improved sampling. Guidance mechanisms have been incorporated through classifier gradients ( Dhariwal and Nichol, 2021 ) , data consistency enforcement ( Chung et al., 2022c ) , and low-frequency feature matching Choi et al. (2021) . Other approaches use projection ( Boys et al., 2023 ; Chung et al., 2024 ; Christopher et al., 2024 ) or optimization ( Chan et al., 2016 ; Wahlberg et al., 2012 ; Zhu et al., 2023 ; Huang et al., 2024 ) . DMPlug Wang et al. (2024) backpropagates through the entire diffusion process, leading to extremely slow inference. DSG