betaFeedback

WorksMathematics

Diffusion Models are Provably Efficient Priors for Sparse Recovery

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.

Introduction

Diffusion models ([50, 54, 55, 51, 21] (Ho et al. 2020)), as the backbone of modern image and video generation engines ([44]), are one of the driving forces behind the recent remarkable advances of generative artificial intelligence. Since their debut, diffusion models have been adopted across many scientific and engineering domains, such as biological structure prediction ([2, 56]), robotics ([19, 33]), materials ([23]), and many others.

A central idea behind score-based diffusion models is to perturb the data with progressively stronger Gaussian noise and learn the associated score functions, namely the gradients of the log densities at different noise levels, for instance, via score matching ([30]). These scores then guide an iterative denoising process that transforms noise into samples resembling those from the data distribution ([54, 55]). Complementing this empirical success, a flurry of recent theory has established polynomial bounds on the number of sampling steps required when the score functions are accurate, without imposing any smoothness or log-concavity assumptions on the data distribution (see, e.g., [17, 5, 39] (Li et al. 2024)).

Diffusion models as priors

The expressive power of diffusion models makes them attractive priors for ill-posed inverse problems, where the goal is to recover high-dimensional signals from a small number of noisy measurements. Of particular interest is the plug-and-play framework ([10]), in which the same pretrained diffusion model is reused to solve different instances of inverse problems. This flexibility is especially valuable in domains where the same class of signals is observed through different sensing modalities and under varying noise conditions, allowing the substantial cost of training a diffusion model to be amortized across reconstruction tasks.

Posterior sampling provides a natural approach to use a diffusion prior for inverse problems, where one can generate multiple samples from the resulting posterior as candidate reconstructions. However, turning an unconditional diffusion model into a posterior sampler introduces additional difficulties. Running the reverse diffusion directly for posterior sampling requires the scores of the measurement-conditioned distributions at intermediate noise levels, which are not supplied by the pretrained diffusion model. Many empirical methods are thus developed to circumvent this limitation, and have achieved qualitatively impressive performance (see, e.g., [32, 1, 52, 53]).

Despite these empirical advances, the theoretical understanding of diffusion-based inverse solvers remains severely limited. Existing algorithms often come only with asymptotic consistency for sampling from the true posterior [26, 15, 35] (Wu et al. 2023; Xu and Chi 2024). When it comes to non-asymptotic guarantees, they can require exponentially many sampling steps in the worst case (Xu and Chi, 2024), rely on strong assumptions on the algorithm’s initialization [41, 62], or constrain the data distribution to strict log-concavity [62] or small susceptibility [9] to allow more efficient sampling guarantees. Indeed, under standard computational hardness assumptions, Gupta et al. [28]; ); Bruna and Han [9] showed that posterior sampling can be intractable even for linear inverse problems whose unconditional diffusion models admit efficient sampling. These computational barriers rule out a general polynomial-time guarantee for diffusion-based inverse solvers, and motivate the search for structured inverse problems that admit efficient inference and are more representative of where such solvers succeed in practice.

Our contribution

To understand when diffusion priors admit efficient inference, we adopt sparse recovery from noisy linear measurements, a classical problem in compressed sensing [24, 14, 12], as our testbed. We assume access to a pretrained diffusion model that captures a sparsity-promoting Bernoulli–Gaussian prior, under which each coordinate is either zero or drawn from a Gaussian distribution. This setting retains the key challenge associated with a non-log-concave data prior, while remains tractable enough to yield practically meaningful insight into the statistical and computational efficiency of diffusion-based inverse solvers beyond the worst case.

Concretely, we analyze a simple likelihood-guided annealed Langevin algorithm [32] that combines the scores of the noise-perturbed prior with progressively stronger likelihood guidance as the diffusion noise level decreases. We show the algorithm succeeds within a polynomial number of iterations at near-optimal sample complexities for a broad family of sensing matrix designs, including sub-Gaussian random matrices, randomly subsampled orthonormal bases, and deterministic incoherent tight frames.

  • For fixed sparse signals, we establish that under suitable noise and signal strength conditions, with high probability, the reconstructed signal enjoys near-optimal ℓ2\ell_2 recovery guarantees on the order of

σk,\sigma\sqrt{k},

up to logarithmic factors, where kk is the sparsity level, and σ\sigma is the noise level.

  • For sparse signals drawn from the Bernoulli–Gaussian prior, we further establish posterior sampling guarantees in total variation on the order of

α+Esc\alpha+ \sqrt{\mathcal{E}_{\mathrm{sc}}}

after a final denoising step, where α>0\alpha> 0 is the target accuracy, and Esc\mathcal{E}_{\mathrm{sc}} is the score estimation error.

Both guarantees explicitly account for the score estimation error, where they degenerate gracefully as it grows. To the best of our knowledge, our result provides the first polynomial-time posterior sampling algorithm at the near-optimal sample complexity linear in the expected sparsity level using random sensing ensembles, answering an open problem raised in Kumar et al. [38]. Together, these results identify a concrete and benign setting in which a simple diffusion-based solver provably achieves accurate recovery and posterior sampling under a non-log-concave prior, with guarantees that are efficient both statistically and computationally.

Related works

Several recent works have sought non-asymptotic convergence guarantees for diffusion-based posterior sampling in general inverse problems. The convergence rate in Xu and Chi (2024) depends critically on the spectral gap of a Markov chain tied to the dynamics of their underlying algorithm, which can become exponentially small in the problem dimension in the worst case. Leong and Traonmilin [41] developed a deterministic recovery theory leveraging the connection between diffusion and denoising operators Kadkhodaie and Simoncelli [36]. However, their theory does not provide a convergence guarantee with polynomial complexity, since it hinges on an unspecified initial burn-in phase. A notable recent development is Xun et al. [62], which developed a provably efficient posterior sampling algorithm based on annealed Langevin dynamics with polynomial iteration complexities, assuming a log-concave prior. They subsequently went beyond log-concavity by assuming access to direct measurements of the signal of interest at sufficiently low noise levels, which are generally unavailable in practice. Our work removes these restrictions in the setting of sparse recovery with few measurements. Last but not least, Xu [60] showed that diffusion-based posterior sampling is efficient for sparse signal denoising, corresponding to the special case of compressed sensing with an identity sensing matrix. The present paper builds on Xu [60], but significantly goes beyond it by handling general sensing matrices.

We also note that Bayesian approaches have long been applied to high-dimensional sparse linear regression, e.g., George and McCulloch [27]; Ishwaran and Rao [31]; Yang et al. [63]. Due to the challenge of sampling from multi-modal distributions, recent efforts have focused on developing efficient sampling algorithms tailored to sparsity-inducing distributions, such as the spike-and-slab prior [43, 37, 34, 38]. Although the goal of our work is not to compete with existing sparse recovery algorithms, it offers a complementary–and competitive–algorithmic perspective with efficient sampling guarantees, and highlights the benefit of annealing provided naturally by diffusion priors.

Notation. Before proceeding, we introduce several useful notation used throughout the paper. Define the sub-Gaussian norm of a real random variable RR as

∥R∥ψ2:=inf⁡{v>0:EeR2/v2≤2}.\lVert R\rVert_{\psi_2} := \inf\{v > 0 : \mathbb{E}e^{R^2/v^2} \le2\}.

Throughout the paper, we use cc and CC to denote positive universal constants whose values may change between occurrences, where cc is typically taken to be small enough and CC to be large enough. For a matrix BB, we let BijB_{ij} be its (i,j)(i,j)-th entry, BjB_j be its ii-th column, and for index sets JJ and KK, let BJKB_{JK} be the submatrix with rows in JJ and columns in KK, and BJB_J be the submatrix with columns in JJ. The diagonal part of a matrix BB is denoted by diag⁡B\operatorname{diag} B, while diag⁡(ci)\operatorname{diag}(c_i) is the diagonal matrix with entries cic_i. We write [n]:={1,…,n}[n] := \{1,\ldots,n\} and supp⁡x:={i:xi≠0}\operatorname{supp} x := \{i : x_i \ne0\}. Let ∥x∥\lVert x\rVert be the ℓ2\ell_2 norm of a vector xx, and ∥A∥\lVert A\rVert be the spectral norm of a matrix AA. The law of a random variable XX is denoted by L(X)\mathcal{L}(X). The product μ⊗ν\mu\otimes\nu is the joint law of independent draws with laws μ,ν\mu,\nu; the law of their sum has convolution law μ∗ν\mu* \nu.

Problem formulation

We aim at solving an underdetermined linear inverse problem of the form

y=Ax⋆+σζ,ζ∼N(0,Im),(1)y = Ax_\star+ \sigma\zeta,\qquad\zeta\sim\mathcal{N}(0,I_m), \tag*{(1)}

where A∈Rm×nA \in\mathbb{R}^{m\times n} is the sensing or measurement matrix, x⋆x_\star is the signal of interest, and σζ∈Rm\sigma\zeta\in\mathbb{R}^m is the additive Gaussian noise independent of the signal, with a known noise level σ>0\sigma> 0.

Sparse signal prior. Our canonical model of the signal prior is the Bernoulli–Gaussian model, which provides a simple and analytically convenient description of sparsity.

Definition 1 (Bernoulli–Gaussian model). Let s,n∈Ns,n \in\mathbb{N}, with s<ns < n. A random vector

X=(X1,…,Xn)∈RnX = (X_1,\ldots,X_n) \in\mathbb{R}^n

is said to follow the Bernoulli–Gaussian model with sparsity level ss and dimension nn, denoted as BG(s,n)\mathrm{BG}(s,n), if its coordinates are independent and identically distributed according to

Xi=BiZi∼(1−sn)δ0+snN(0,1),i=1,…,n,X_i = B_i Z_i \sim\left(1-\frac{s}{n}\right)\delta_0 + \frac{s}{n}\mathcal{N}(0,1),\qquad i=1,\ldots,n,

where δ0\delta_0 is a point mass at zero, Bi∼Bernoulli⁡(s/n)B_i \sim\operatorname{Bernoulli}(s/n) and Zi∼N(0,1)Z_i \sim\mathcal{N}(0,1) are all mutually independent.

Each coordinate of XX is thus zero with probability 1−s/n1-s/n and standard Gaussian otherwise. The expected support size of XX is E[∣supp⁡(X)∣]=s\mathbb{E}[\lvert\operatorname{supp}(X)\rvert] = s, and therefore, we refer to ss as the sparsity level.

Posterior sampling with diffusion models We consider a Bayesian approach to signal recovery, even when the underlying ground truth signal x⋆x_\star may not be generated from a probabilistic model. We postulate the ground truth signal x⋆x_\star follows a prior distribution p⋆p_\star, for example, BG⁡(s,n)\operatorname{BG}(s,n) for some postulated sparsity level ss. We attempt to solve the inverse problem in (1) by sampling from the posterior distribution of x⋆x_\star given yy, using Bayes’ formula:

p⋆(x∣y)∝p⋆(x) p(y∣x⋆=x)=p⋆(x)exp⁡(L(x;y)),(2)p_\star(x\mid y) \propto p_\star(x)\,p(y\mid x_\star=x)=p_\star(x)\exp\bigl(\mathcal{L}(x;y)\bigr), \tag*{(2)}

where the log-likelihood function of the measurement model (1) is given by

L(x;y):=−12σ2∥y−Ax∥2+Cσ.(3)\mathcal{L}(x;y):=-\frac{1}{2\sigma^2}\lVert y-Ax\rVert^2+C_\sigma. \tag*{(3)}

Here, CσC_\sigma is a constant depending only on σ\sigma.

Rather than developing a posterior sampler tailored to the sparse prior, we instead use sparse recovery as a testbed for a broader question: can a diffusion model (Song et al. [55]), which describes p⋆p_\star only implicitly, enable provably efficient posterior sampling? Concretely, consider the smoothed prior

pt:=p⋆∗N(0,tIn),t>0,(4)p_t:=p_\star* \mathcal{N}(0,tI_n),\qquad t>0, \tag*{(4)}

which is the law of X+tξX+\sqrt{t}\xi, where X∼p⋆X\sim p_\star and ξ∼N(0,In)\xi\sim\mathcal{N}(0,I_n) are independent. We assume access to an estimate s^t(x)\widehat{s}_t(x) of the score function

st(x):=∇log⁡pt(x)s_t(x):=\nabla\log p_t(x)

of the smoothed prior ptp_t, which is well-defined since ptp_t is smooth and positive. In practice, the score functions can be learned, for instance, via score matching (Hyvärinen [30]). Given accurate scores, many diffusion samplers provably generate samples whose law is close to p⋆p_\star (see, e.g., Benton et al. [5]; Chen et al. [17]; Lee et al. [39]; Li et al. (2024)), and hence, the diffusion model (as specified by s^t(x)\widehat{s}_t(x)) encodes the prior information. Nonetheless, we cannot directly access an analytical form of p⋆p_\star.

Goal. Our goal is to recover the signal of interest x⋆x_\star from the measurement yy, assuming access to a diffusion model (as specified by s^t(x)\widehat{s}_t(x)), in a provably efficient manner, both statistically and computationally.

Remark 1 (Unknown sparsifying basis.). One advantage of diffusion-based solvers is that they do not require explicit configuration of the sparsifying basis of the signals of interest. While the observation model in (1) assumes x⋆x^\star is a sparse vector in the standard basis, in general, it is straightforward to extend to the case where x⋆=Ψθ⋆x^\star=\Psi\theta^\star is sparse in some orthonormal basis Ψ\Psi, e.g., the wavelet or discrete cosine basis. Traditional algorithms (Donoho [24]; Candes and Tao [14]) require the basis to be specified in order to be implemented, while diffusion-based algorithms can implicitly capture this information in the score estimates by training directly on the law of the transformed signals x⋆x^\star.

Diffusion-based inverse solver

Many diffusion-based posterior samplers add a guidance term to the reverse-time dynamics of the diffusion model, which steers the iterates to be consistent with the measurements (Chung et al. [20]). For tractability, we analyze one of the simplest schemes of this type, annealed Langevin dynamics with a likelihood guidance term, proposed in Jalal et al. [32]. While this may not be the fastest horse in the race, its simplicity makes a precise analysis possible for deeper mathematical insights.

Tilted targets. To begin with, consider a family of tilted targets. For each level t>0t>0, let

Πt(x)∝pt(x)exp⁡(−∥Ax−y∥22at),at:=σ2+2t,(5)\Pi_t(x)\propto p_t(x)\exp\left(-\frac{\lVert Ax-y\rVert^2}{2a_t}\right),\qquad a_t:=\sigma^2+2t, \tag*{(5)}

where ptp_t is the smoothed prior in (4). It is easy to check that Πt\Pi_t is the conditional law of XX given the prior X∼ptX\sim p_t and y=AX+wy=AX+w, where w∼N(0,atIm)w\sim\mathcal{N}(0,a_tI_m) is independent of XX, with the variance ata_t adding a smoothing term 2t2t to the noise variance σ2\sigma^2. Decreasing the level tt moves the tilted target Πt(x)\Pi_t(x) from a nearly Gaussian law (since ptp_t is close to N(0,tIn)\mathcal{N}(0,tI_n) when tt is large), toward the posterior of the signal given yy (since pt→p⋆p_t \to p_\star and at→σ2a_t \to\sigma^2 as t→0t \to0).

At a fixed level tt, the target Πt\Pi_t is the stationary law of the Langevin diffusion

dXu=(∇log⁡pt(Xu)+AT(y−AXu)at)du+2 dBu,u≥0,(6)\mathrm{d}X_u = \left(\nabla\log p_t(X_u) + \frac{A^\mathsf{T}(y-AX_u)}{a_t}\right)\mathrm{d}u + \sqrt{2}\,\mathrm{d}B_u,\qquad u \ge0, \tag*{(6)}

where (Bu)u≥0(B_u)_{u\ge0} is a standard Brownian motion in Rn\mathbb{R}^n, and the drift is the score of the tilted target

References

  1. [1]Aali, A., Arvinte, M., Kumar, S., and Tamir, J. I. (2023). Solving inverse problems with score-based generative priors learned from noisy data. In 2023 57th Asilomar Conference on Signals, Systems, and Computers, pages 837–843. IEEE.DOI
  2. [2]Abramson, J., Adler, J., Dunger, J., Evans, R., Green, T., Pritzel, A., Ronneberger, O., Willmore, L., Ballard, A. J., Bambrick, J., et al. (2024). Accurate structure prediction of biomolecular interactions with AlphaFold 3. Nature, pages 1–3.DOI
  3. [3]Bajwa, W. U., Calderbank, R., and Mixon, D. G. (2012). Two are better than one: Fundamental parameters of frame coherence. Applied and Computational Harmonic Analysis, 33(1):58–78.DOI
  4. [4]Bauerschmidt, R. and Bodineau, T. (2019). A very simple proof of the LSI for high temperature spin systems. Journal of Functional Analysis, 276(8):2582–2588.DOI
  5. [5]Benton, J., De Bortoli, V., Doucet, A., and Deligiannidis, G. (2024). Nearly d-linear convergence bounds for diffusion models via stochastic localization. In The Twelfth International Conference on Learning Representations.arxiv.org/abs/2308.03686
  6. [6]Bobkov, S. G. and Ledoux, M. (2000). From Brunn–Minkowski to Brascamp–Lieb and to logarithmic Sobolev inequalities. Geometric and Functional Analysis, 10(5):1028–1052.DOI
  7. [7]Boucheron, S., Lugosi, G., and Massart, P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press.
  8. [8]Brascamp, H. J. and Lieb, E. H. (1976). On extensions of the Brunn–Minkowski and Prékopa–Leindler theorems, including inequalities for log concave functions, and with an application to the diffusion equation. Journal of Functional Analysis, 22(4):366–389.
  9. [9]Bruna, J. and Han, J. (2024). Provable posterior sampling with denoising oracles via tilted transport. In Advances in Neural Information Processing Systems, volume 37.arxiv.org/abs/2407.00745
  10. [10]Buzzard, G. T., Chan, S. H., Sreehari, S., and Bouman, C. A. (2018). Plug-and-play unplugged: Optimization-free reconstruction using consensus equilibrium. SIAM Journal on Imaging Sciences, 11(3):2001–2020.arxiv.org/abs/1705.08983
  11. [11]Candès, E. J. and Davenport, M. A. (2013). How well can we estimate a sparse vector? Applied and Computational Harmonic Analysis, 34(2):317–323.arxiv.org/abs/1104.5246
  12. [12]Candès, E. J., Romberg, J. K., and Tao, T. (2006). Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 59(8):1207–1223.arxiv.org/abs/math/0503066
  13. [13]Candès, E. J. and Tao, T. (2005). Decoding by linear programming. IEEE Transactions on Information Theory, 51(12):4203–4215.DOI
  14. [14]Candes, E. J. and Tao, T. (2006). Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE transactions on Information Theory, 52(12):5406–5425.
  15. [15]Cardoso, G., Idrissi, Y. J. E., Corff, S. L., and Moulines, E. (2023). Monte carlo guided diffusion for Bayesian linear inverse problems. arXiv preprint arXiv:2308.07983.arxiv.org/abs/2308.07983
  16. [16]Chafaï, D. (2004). Entropies, convexity, and functional inequalities: On Φ-entropies and Φ-Sobolev inequalities. Journal of Mathematics of Kyoto University, 44(2):325–363.
  17. [17]Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang, A. R. (2023). Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In International Conference on Learning Representations.arxiv.org/abs/2209.11215
  18. [18]Chen, Y., Chewi, S., Salim, A., and Wibisono, A. (2022). Improved analysis for a proximal algorithm for sampling. In Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 2984–3014. PMLR.arxiv.org/abs/2202.06386
  19. [19]Chi, C., Feng, S., Du, Y., Xu, Z., Cousineau, E., Burchfiel, B., and Song, S. (2023). Diffusion policy: Visuomotor policy learning via action diffusion. In Proceedings of Robotics: Science and Systems.arxiv.org/abs/2303.04137
  20. [20]Chung, H., Kim, J., Mccann, M. T., Klasky, M. L., and Ye, J. C. (2023). Diffusion posterior sampling for general noisy inverse problems. In International Conference on Learning Representations.arxiv.org/abs/2209.14687
  21. [21]Dhariwal, P. and Nichol, A. (2021). Diffusion models beat GANs on image synthesis. Advances in Neural Information Processing Systems, 34:8780–8794.arxiv.org/abs/2105.05233
  22. [22]Dirksen, S. (2015). Tail bounds via generic chaining. Electronic Journal of Probability, 20(53):1–29.arxiv.org/abs/1309.3522
  23. [23]Dong, H., Efimov, T., Shah, M., Simmons, J., Donegan, S., De Graef, M., and Chi, Y. (2026). Multimodal diffusion to mutually enhance polarized light and low resolution EBSD data. arXiv preprint arXiv:2604.22212.arxiv.org/abs/2604.22212
  24. [24]Donoho, D. L. (2006). Compressed sensing. IEEE Transactions on information theory, 52(4):1289–1306.
  25. [25]Donoho, D. L., Elad, M., and Temlyakov, V. N. (2005). Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions on Information Theory, 52(1):6–18.DOI
  26. [26]Dou, Z. and Song, Y. (2024). Diffusion posterior sampling for linear inverse problem solving: A filtering perspective. In International Conference on Learning Representations.
  27. [27]George, E. I. and McCulloch, R. E. (1993). Variable selection via Gibbs sampling. Journal of the American Statistical Association, 88(423):881–889.DOI
  28. [28]Gupta, S., Jalal, A., Parulekar, A., Price, E., and Xun, Z. (2024). Diffusion posterior sampling is computationally intractable. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 17020–17059. PMLR.arxiv.org/abs/2402.12727
  29. [30]Hyvärinen, A. (2005). Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(24):695–709.DOI
  30. [31]Ishwaran, H. and Rao, J. S. (2005). Spike and slab variable selection: Frequentist and bayesian strategies. Annals of Statistics, 33(2):730–773.DOI
  31. [32]Jalal, A., Arvinte, M., Daras, G., Price, E., Dimakis, A. G., and Tamir, J. I. (2021). Robust compressed sensing MRI with deep generative priors. In Advances in Neural Information Processing Systems, volume 34.arxiv.org/abs/2108.01368
  32. [33]Janner, M., Du, Y., Tenenbaum, J., and Levine, S. (2022). Planning with diffusion for flexible behavior synthesis. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 9902–9915. PMLR.arxiv.org/abs/2205.09991
  33. [34]Jiang, Q. (2023). From estimation to sampling for Bayesian linear regression with spike-and-slab prior. arXiv preprint arXiv:2307.0558.arxiv.org/abs/2307.05558
  34. [35]Jiao, Y., Li, N., Cai, C., Chen, Y., and Li, G. (2026). Provable diffusion-based posterior sampling for linear inverse problems via DDIM. arXiv preprint arXiv:2607.19333.arxiv.org/abs/2607.19333
  35. [36]Kadkhodaie, Z. and Simoncelli, E. (2021). Stochastic solutions for linear inverse problems using the prior implicit in a denoiser. Advances in Neural Information Processing Systems, 34:13242–13254.arxiv.org/abs/2007.13640
  36. [37]Kumar, S., Sarkar, P., Tian, K., and Zhu, Y. (2025). Spike-and-slab posterior sampling in high dimensions. In Hagtalab, N. and Moitra, A., editors, Proceedings of the Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 3407–3462. PMLR.arxiv.org/abs/2503.02798
  37. [38]Kumar, S., Sarkar, P., Tian, K., and Zhu, Y. (2026). High-magnetization sampling at low temperatures: Ising models and Bayesian sparse linear regression. arXiv preprint arXiv:2609.08873.arxiv.org/abs/2609.08873
  38. [39]Lee, H., Lu, J., and Tan, Y. (2022). Convergence for score-based generative modeling with polynomial complexity. In Advances in Neural Information Processing Systems.arxiv.org/abs/2206.06227
  39. [40]Lee, Y. T., Shen, R., and Tian, K. (2021). Structured logconcave sampling with a restricted Gaussian oracle. In Conference on Learning Theory, pages 2993–3050. PMLR.arxiv.org/abs/2010.03106
  40. [41]Leong, O. and Traonmilin, Y. (2025). A recovery theory for diffusion priors: Deterministic analysis of the implicit prior algorithm. arXiv preprint arXiv:2509.20511.arxiv.org/abs/2509.20511
  41. [43]Montanari, A. and Wu, Y. (2026). Provably efficient posterior sampling for sparse linear regression via measure decomposition. Journal of the American Statistical Association, 121(553):636–654.arxiv.org/abs/2406.19550
  42. [44]Peebles, W. and Xie, S. (2023). Scalable diffusion models with transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4195–4205.arxiv.org/abs/2212.09748
  43. [45]Polyanskiy, Y. and Wu, Y. (2024). Information theory: From coding to learning. Cambridge university press.
  44. [46]Rauhut, H. (2010). Compressive sensing and structured random matrices. In Theoretical Foundations and Numerical Methods for Sparse Recovery, volume 9 of Radon Series on Computational and Applied Mathematics, pages 1–92. de Gruyter, Berlin.DOI
  45. [47]Röckner, M. and Wang, F.-Y. (2001). Weak Poincaré inequalities and L²-convergence rates of Markov semigroups. Journal of Functional Analysis, 185(2):564–603.
  46. [48]Rudelson, M. and Vershynin, R. (2008). On sparse reconstruction from Fourier and Gaussian measurements. Communications on Pure and Applied Mathematics, 61(8):1025–1045.DOI
  47. [49]Rudelson, M. and Vershynin, R. (2013). Hanson-Wright inequality and sub-gaussian concentration. Electronic Communications in Probability, 18:1–9.arxiv.org/abs/1306.2872
  48. [50]Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. (2015). Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning, pages 2256–2265.
  49. [51]Song, J., Meng, C., and Ermon, S. (2020). Denoising diffusion implicit models. In International Conference on Learning Representations.arxiv.org/abs/2010.02502
  50. [52]Song, J., Vahdat, A., Mardani, M., and Kautz, J. (2022). Pseudoinverse-guided diffusion models for inverse problems. In International Conference on Learning Representations.
  51. [53]Song, J., Zhang, Q., Yin, H., Mardani, M., Liu, M.-Y., Kautz, J., Chen, Y., and Vahdat, A. (2023). Loss-guided diffusion models for plug-and-play controllable generation. In International Conference on Machine Learning, pages 32483–32498. PMLR.
  52. [54]Song, Y. and Ermon, S. (2019). Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32.arxiv.org/abs/1907.05600
  53. [55]Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. (2021). Score-based generative modeling through stochastic differential equations. International Conference on Learning Representations.arxiv.org/abs/2011.13456
  54. [56]Trippe, B. L., Yim, J., Tischer, D., Baker, D., Broderick, T., Barzilay, R., and Jaakkola, T. (2022). Diffusion probabilistic modeling of protein backbones in 3d for the motif-scaffolding problem. arXiv preprint arXiv:2206.04119.arxiv.org/abs/2206.04119
  55. [57]Tropp, J. A. (2008). On the conditioning of random subdictionaries. Applied and Computational Harmonic Analysis, 25(1):1–24.DOI
  56. [58]Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press.
  57. [60]Xu, X. (2026). Fantastic Diffusion Models and Where to Apply Them. PhD thesis, Carnegie Mellon University.
  58. [62]Xun, Z., Gupta, S., and Price, E. (2025). Posterior sampling by combining diffusion models with annealed Langevin dynamics. In Advances in Neural Information Processing Systems.arxiv.org/abs/2510.26324
  59. [63]Yang, Y., Wainwright, M. J., and Jordan, M. I. (2016). On the computational complexity of high-dimensional Bayesian variable selection. Annals of Statistics, 44(6):2497–2532.arxiv.org/abs/1505.07925
  60. [64]Zhang, C.-H. (2010). Nearly unbiased variable selection under minimax concave penalty. The Annals of Statistics, 38(2):894–942.DOI

Paper details

vlnc:W_x4k4v58z
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents