stat.MLNov 18, 2026

Diffusion Models are Provably Efficient Priors for Sparse Recovery

Authors: Ivan Lee, Xingyu Xu, Yuejie Chi

Organizations: Department of Statistics and Data Science, Yale University · Department of Electrical and Computer Engineering, Carnegie Mellon University

Abstract

Diffusion models have transformed generative modeling through their ability to capture and generate samples from complex data distributions. This success has spurred substantial interest in using pretrained diffusion models as expressive priors for highly ill-posed inverse problems in imaging and sensing. Despite strong empirical performance, theoretical understanding of this approach remains limited: existing guarantees are often asymptotic or entail prohibitive computational costs in the worst case. In this paper, we address this gap by studying sparse recovery from a small number of linear measurements, a classical problem in compressed sensing. We show that, given an accurate diffusion model capturing a sparsity-promoting Bernoulli-Gaussian prior, a likelihood-guided annealed Langevin sampler provably recovers the sparse signal in polynomial time with near-optimal sample complexity for a broad family of random and deterministic sensing matrices. When the signal is indeed drawn from the postulated prior, we further establish total variation guarantees for posterior sampling after a final denoising step. These results lay a theoretical foundation for statistically and computationally efficient inverse solvers with diffusion priors.

Explore similar work

CardsList
  1. Sparse Scheduled Diffusion Guidance for Inverse Problems

    Mar 9, 2026Abduragim Shtanchaev, Albina Ilina, Yazid Janati +3Diffusion-Based Inverse ProblemsDiffusion Posterior Sampling

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

    Jul 21, 2026Yuchen Jiao, Na Li, Changxiao Cai +2Diffusion Models for Image RestorationBayesian Inverse Problems

  3. Tunable Latent Generative Priors for Compressed Sensing and Inverse Problems

    Mar 7, 2026Sean Gunn, Jorio Cocola, Oliver De Candido +2Generative ModelingCompressed Sensing