Technical Summary: Noise Combination Sampling for Linear Inverse Problems

1. Problem Statement

Pretrained diffusion models (DMs) have demonstrated significant potential in solving inverse problems (e.g., image inpainting, deblurring, super-resolution, and scientific imaging) in a zero-shot manner by incorporating observation information into the generation process. However, existing methods face an inherent dilemma:

• Excessive Integration: Aggressively injecting observation constraints can disrupt the generative process, pushing the sampling trajectory off the learned data manifold and causing instability.
• Insufficient Integration: Weak integration fails to adequately enforce the constraints imposed by the inverse problem, leading to poor reconstruction quality.

Current solutions often rely on complex hyperparameter tuning, long sampling schedules, or variational inference approaches that require expensive searches over multiple parameters to compensate for these limitations. Furthermore, while methods like Denoising Diffusion Codebook Models (DDCM) offer efficient compression, they often rely on greedy searches with exponential computational complexity when combining multiple noise vectors.

2. Methodology: Noise Combination Sampling (NCS)

The authors propose Noise Combination Sampling (NCS), a framework that approximates the measurement score $\nabla_{x_t} \log p(y | x_t)$ by synthesizing an optimal noise vector from a noise subspace, rather than explicitly modifying the denoising update with external gradients.

Core Mechanism

In standard Denoising Diffusion Probabilistic Models (DDPM), the reverse update is:
$$x_{t-1} = \mu(x_t, t) + \sigma_t \epsilon_t, \quad \epsilon_t \sim \mathcal{N}(0, I)$$
For conditional generation, the noise term $\epsilon_t$ is replaced by a synthesized noise vector $\epsilon^*_t$ that aligns with the conditional score direction. NCS restricts $\epsilon^*_t$ to the span of a finite set of Gaussian noise vectors (a "noise codebook") $\{\epsilon^i_t\}_{i=1}^K$:
$$\epsilon^*_t = \sum_{i=1}^K \gamma_i \epsilon^i_t$$
The goal is to find combination weights $\gamma$ that maximize the alignment between the synthesized noise and the conditional score direction $c = \nabla_{x_t} \log p(y | x_t)$.

Theoretical Formulation

Instead of directly optimizing cosine similarity, NCS adopts an inner-product-based surrogate objective, which admits a computationally efficient closed-form solution.

• Optimization: Maximize $\langle c, \sum \gamma_i \epsilon^i_t \rangle$ subject to $\|\gamma\|_2 = 1$.
• Closed-Form Solution: Let $E_t = [\epsilon^1_t, \dots, \epsilon^K_t]$. The optimal weights are:
  $$\gamma^* = \frac{E_t^\top c}{\|E_t^\top c\|_2}$$
  This formulation allows the conditional information to be naturally embedded into the noise component, preserving the denoising structure and keeping the trajectory on the learned manifold.

Relationship to Existing Methods

NCS unifies several existing plug-and-play solvers (DPS, MPGD, $\Pi$GDM, DAPS) as special cases of optimal noise combinations.

• DDCM Connection: The authors demonstrate that DDCM is a special case of NCS where the combination weights are constrained to be one-hot (selecting exactly one noise vector). NCS generalizes this by allowing linear combinations of multiple vectors.
• Complexity: While DDCM relies on greedy search for multi-vector combinations (exponential complexity), NCS achieves competitive performance with linear complexity $O(K)$ via the closed-form solution.

Parameter Selection

The paper analyzes the Signal-to-Noise Ratio (SNR) scaling of the synthesized noise. It suggests choosing the codebook size $K \approx \sqrt{n}$, where $n$ is the effective dimension of the measurement space (often $n \ll d$ for ill-posed problems). This scaling ensures effective guidance while maintaining the noise's Gaussian-like structure.

3. Key Contributions

1. Novel Framework: Introduction of NCS, which formulates measurement score approximation as an inner-product minimization problem with a closed-form solution, enabling stable conditional control without step-wise hyperparameter tuning.
2. Theoretical Unification: Demonstration that NCS unifies existing inverse problem solvers (DPS, MPGD, etc.) and generalizes DDCM. It proves that DDCM is a special case of NCS under a one-hot constraint.
3. Efficiency in Compression: Application of NCS to generative image compression, showing that it achieves competitive quantization quality with linear-time complexity in the number of noise vectors $m$, significantly outperforming the greedy search of DDCM.
4. Robustness and Performance: Extensive experiments showing that NCS improves performance across diverse inverse problems and sampling regimes, particularly in low-step settings ($T < 100$), with negligible computational overhead (less than 4% increase in inference time).

4. Experimental Results

The authors evaluated NCS on image restoration tasks (inpainting, super-resolution, deblurring) and scientific inverse problems (black hole imaging, inverse scattering, compressed sensing MRI) using FFHQ, ImageNet, and specialized scientific datasets.

• Inverse Problems: NCS-DPS and NCS-MPGD consistently outperformed their baseline counterparts and state-of-the-art methods (e.g., RED-Diff, DAPS) across various metrics (PSNR, FID, LPIPS). Notably, NCS achieved superior results with fewer diffusion steps (e.g., 20 or 100 steps), where baselines often struggled with instability.
• Compression: In generative compression experiments, NCS achieved comparable rate-distortion performance to DDCM while reducing the number of diffusion steps by a factor of 10 (e.g., from 1000 to 100 steps). This resulted in a 10x speedup in compression time with minimal reconstruction degradation.
• Computational Cost: The overhead introduced by NCS is negligible. On an NVIDIA RTX 4090, the per-step overhead was approximately 1–3ms compared to a ~130ms model inference time, resulting in a total slowdown of only 1–4%.

5. Significance and Claims

The paper claims that NCS offers a fundamental shift in how conditional information is integrated into diffusion models. By embedding guidance into the noise vector rather than perturbing the trajectory directly, NCS:

• Stabilizes Generation: It avoids the instability associated with explicit gradient guidance, particularly in low-step regimes.
• Eliminates Tuning: It operates effectively with a single default setting, removing the need for complex hyperparameter searches required by existing methods.
• Accelerates Inference: It enables high-quality reconstruction with significantly fewer diffusion steps, making diffusion-based inverse solvers more practical for real-time applications.
• Generalizes Compression: It provides a theoretically grounded, efficient alternative to DDCM for generative compression, solving the exponential complexity bottleneck of multi-vector selection.

The authors acknowledge that while NCS-DPS shows limited improvement over DAPS in some specific cases and can encounter failure modes similar to DPS (e.g., collapse to dark images), the overall framework provides a robust, unified, and efficient approach to solving linear inverse problems and generative compression.