Research map / Learning theory and algorithms / Sample complexity
How many measurements are enough? Bayesian recovery in inverse problems with general distributions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives non-asymptotic sample complexity bounds for Bayesian posterior-sampling recovery in inverse problems with general prior, forward operator, and noise distributions, specialized to Lipschitz generative priors, sparse priors, and subsampled orthogonal (e.g., Fourier) measurements.
Problem
How many linear measurements suffice for stable and accurate Bayesian recovery via posterior sampling from an approximate prior, when the prior, forward operator and noise distributions are arbitrary?
Approach
Bounds the posterior-sampling error probability in terms of the approximate covering number of the approximate prior and concentration bounds for the forward operator taken only over the difference set of the prior's support, yielding sample complexity log-linear in latent dimension for generative priors and governed by coherence for subsampled orthogonal transforms.
Key results
- Subgaussian measurements: recovery with error at most 34(eta+sigma) with high probability when m >= c[log Cov_{eta,delta}(P) + log(1/delta)], i.e., linear in the log covering number.
- For Lipschitz generative priors, log Cov scales as O(k log[L(sqrt(k)+log(1/delta))/eta]), giving near-optimal O(k log k) measurements.
- For subsampled orthogonal transforms, the measurement requirement scales with coherence mu(U;D); for sparse priors this gives m = O(s^2) up to log factors due to a quadratic bottleneck.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use subgaussian random measurement matrices | Bayesian posterior sampling · General priors with Gaussian noise | measurements required for recovery: m ≥ c(β,κ) · [min (log Cov_{η,δ} (ℛ), log Cov_{η,δ} (𝒫)) + log(1/δ)] | Helped |
| Use randomly subsampled orthogonal measurements | Bayesian posterior sampling · General priors with Gaussian noise | measurements required for recovery: m ≥ c · μ(U ; D) · [log (Cov_{η,δ}(𝒫)) + log(1/δ)] | Mixed |
| Use a Lipschitz generative prior with latent dimension k | Bayesian posterior sampling · Lipschitz generative DNN priors | measurements required for recovery: ord{k log(k)} | Helped |
| Use a sparse-vector prior with sparsity s | Bayesian posterior sampling with subgaussian measurements · s-sparse vectors | measurements required for recovery: ord{s log(n/s)} | Helped |
| Use a sparse-vector prior with subsampled orthogonal measurements | Bayesian posterior sampling · s-sparse vectors | measurements required for recovery: m = ord{s^2} up to log terms | Mixed |
| Reduce the Lipschitz constant L of the generative model | Lipschitz generative priors · Lipschitz generative DNN priors | approximate covering number: log(Cov_{η,δ}(𝒫)) ≤ k log [1 + 2√k L/η (1 + √(2/k log(1/δ)))] | Helped |
| Use a prior with smaller coherence | Bayesian recovery with subsampled orthogonal measurements · Subsampled orthogonal transforms | recovery from a fixed number of measurements | Helped |
Surprising findings
- Sample complexity for subsampled orthogonal transforms with sparse priors scales as s^2 rather than s, a quadratic bottleneck from the generality of the analysis.
Limitations
- Main result requires the noise distribution to have a density (density shift bound), an unpleasant technical assumption.
- Quadratic bottleneck in coherence-dependent bounds for generative ReLU priors (k^2 log k) and sparse priors (s^2).
- No numerical experiments; does not address computational posterior sampling.
Experimental setup
Builds on: Bayesian compressed sensing with Gaussian matrices Compressed sensing with generative models (Bora et al.) coherence-based subsampled orthogonal recovery approximate covering numbers
Closest papers by meaning
- Provable Posterior Sampling with Denoising Oracles via Tilted Transport (NeurIPS 2024 · similarity 0.89)
- Sparse Bayesian Generative Modeling for Compressive Sensing (NeurIPS 2024 · similarity 0.88)
- Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing (NeurIPS 2026 · similarity 0.88)
- Divide-and-Conquer Posterior Sampling for Denoising Diffusion priors (NeurIPS 2024 · similarity 0.88)
- Principled Probabilistic Imaging using Diffusion Models as Plug-and-Play Priors (NeurIPS 2024 · similarity 0.87)
- Learning Diffusion Priors from Observations by Expectation Maximization (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.