Diffusion Posterior Sampling is Computationally Intractable
원문 초록
Diffusion models are a remarkably effective way of learning and sampling from a distribution $p(x)$. In posterior sampling, one is also given a measurement model $p(y \mid x)$ and a measurement $y$, and would like to sample from $p(x \mid y)$. Posterior sampling is useful for tasks such as inpainting, super-resolution, and MRI reconstruction, so a number of recent works have given algorithms to heuristically approximate it; but none are known to converge to the correct distribution in polynomial time. In this paper we show that posterior sampling is \emph{computationally intractable}: under the most basic assumption in cryptography -- that one-way functions exist -- there are instances for which \emph{every} algorithm takes superpolynomial time, even though \emph{unconditional} sampling is provably fast. We also show that the exponential-time rejection sampling algorithm is essentially optimal under the stronger plausible assumption that there are one-way functions that take exponential time to invert.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
SUFFICIENT: A scan-specific unsupervised deep learning framework for high-resolution 3D isotropic fetal brain MRI reconstruction
Meta-learning Slice-to-Volume Reconstruction in Fetal Brain MRI using Implicit Neural Representations
IM-LUT: Interpolation Mixing Look-Up Tables for Image Super-Resolution
PanoDiff-SR: Synthesizing Dental Panoramic Radiographs using Diffusion and Super-resolution
HNOSeg-XS: Extremely Small Hartley Neural Operator for Efficient and Resolution-Robust 3D Image Segmentation
MDPG: Multi-domain Diffusion Prior Guidance for MRI Reconstruction
토론
이 논문과 연결된 포럼 글이 아직 없습니다.