# How many measurements are enough? Bayesian recovery in inverse problems with general distributions

arXiv: https://arxiv.org/abs/2505.10630 · HTML: https://mlsanity.com/paper/2505.10630/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 80 references that are in the map.
- First posted on arXiv 15 May 2025.

## Builds on (most cited first, 30 of 43)

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Spectral Normalization for Generative Adversarial Networks](https://mlsanity.com/paper/1802.05957/) (2018)
- [Denoising Diffusion Restoration Models](https://mlsanity.com/paper/2201.11793/) (2022)
- [Solving Inverse Problems in Medical Imaging with Score-Based Generative Models](https://mlsanity.com/paper/2111.08005/) (2021)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Score-based diffusion models for accelerated MRI](https://mlsanity.com/paper/2110.05243/) (2021)
- [Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks](https://mlsanity.com/paper/1906.04893/) (2019)
- [Deep Learning Techniques for Inverse Problems in Imaging](https://mlsanity.com/paper/2005.06001/) (2020)
- [Robust Compressed Sensing MRI with Deep Generative Priors](https://mlsanity.com/paper/2108.01368/) (2021)
- [On instabilities of deep learning in image reconstruction - Does AI come at a cost?](https://mlsanity.com/paper/1902.05300/) (2019)
- [SNIPS: Solving Noisy Inverse Problems Stochastically](https://mlsanity.com/paper/2105.14951/) (2021)
- [Score-Based Diffusion Models as Principled Priors for Inverse Imaging](https://mlsanity.com/paper/2304.11751/) (2023)
- [Bayesian imaging using Plug & Play priors: when Langevin meets Tweedie](https://mlsanity.com/paper/2103.04715/) (2021)
- [Phase Retrieval Under a Generative Prior](https://mlsanity.com/paper/1807.04261/) (2018)
- [On hallucinations in tomographic image reconstruction](https://mlsanity.com/paper/2012.00646/) (2020)
- [Deep Bayesian Inversion](https://mlsanity.com/paper/1811.05910/) (2018)
- [Solving Linear Inverse Problems Using GAN Priors: An Algorithm with Provable Guarantees](https://mlsanity.com/paper/1802.08406/) (2018)
- [Solving Inverse Problems With Deep Neural Networks -- Robustness Included?](https://mlsanity.com/paper/2011.04268/) (2020)
- [Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problem](https://mlsanity.com/paper/2101.08286/) (2021)
- [Bayesian MRI Reconstruction with Joint Uncertainty Estimation using Diffusion Models](https://mlsanity.com/paper/2202.01479/) (2022)
- [Instance-Optimal Compressed Sensing via Posterior Sampling](https://mlsanity.com/paper/2106.11438/) (2021)
- [The troublesome kernel -- On hallucinations, no free lunches and the accuracy-stability trade-off in inverse problems](https://mlsanity.com/paper/2001.01258/) (2020)
- [Solving Inverse Problems with Score-Based Generative Priors learned from Noisy Data](https://mlsanity.com/paper/2305.01166/) (2023)
- [Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk](https://mlsanity.com/paper/1705.07576/) (2017)
- [How I failed machine learning in medical imaging -- shortcomings and recommendations](https://mlsanity.com/paper/2103.10292/) (2021)
- [Modeling Sparse Deviations for Compressed Sensing using Generative Models](https://mlsanity.com/paper/1807.01442/) (2018)
- [Robust Compressed Sensing using Generative Models](https://mlsanity.com/paper/2006.09461/) (2020)
- [Bayesian Imaging With Data-Driven Priors Encoded by Neural Networks: Theory, Methods, and Algorithms](https://mlsanity.com/paper/2103.10182/) (2021)
- [Improving Robustness of Deep-Learning-Based Image Reconstruction](https://mlsanity.com/paper/2002.11821/) (2020)

## Built on by (most cited first, 2 of 2)

- [Error Analysis of Bayesian Inverse Problems with Generative Priors](https://mlsanity.com/paper/2601.17374/) (2026)
- [Christoffel-DPS: Optimal sensor placement in diffusion posterior sampling for arbitrary distributions](https://mlsanity.com/paper/2605.06861/) (2026)

## Abstract (arXiv)

We study the sample complexity of Bayesian recovery for solving inverse problems with general prior, forward operator and noise distributions. We consider posterior sampling according to an approximate prior P, and establish sufficient conditions for stable and accurate recovery with high probability. Our main result is a non-asymptotic bound that shows that the sample complexity depends on (i) the intrinsic complexity of P, quantified by its so-called approximate covering number, and (ii) concentration bounds for the forward operator and noise distributions. As a key application, we specialize to generative priors, where P is the pushforward of a latent distribution via a Deep Neural Network (DNN). We show that the sample complexity scales log-linearly with the latent dimension k, thus establishing the efficacy of DNN-based priors. Generalizing existing results on deterministic (i.e., non-Bayesian) recovery for the important problem of random sampling with an orthogonal matrix U, we show how the sample complexity is determined by the coherence of U with respect to the support of P. Hence, we establish that coherence plays a fundamental role in Bayesian recovery as well. Overall, our framework unifies and extends prior work, providing rigorous guarantees for the sample complexity of solving Bayesian inverse problems with arbitrary distributions.