mlsanityData to 14 Oct 2026

Instance-Optimal Compressed Sensing via Posterior Sampling

arXiv 2106.11438 ↗First posted 21 Jun 2021cs.LG cs.IT math.ITcited by 43

Not on the map. Why?

Abstract (arXiv)

We characterize the measurement complexity of compressed sensing of signals drawn from a known prior distribution, even when the support of the prior is the entire space (rather than, say, sparse vectors). We show for Gaussian measurements and any prior distribution on the signal, that the posterior sampling estimator achieves near-optimal recovery guarantees. Moreover, this result is robust to model mismatch, as long as the distribution estimate (e.g., from an invertible generative model) is close to the true distribution in Wasserstein distance. We implement the posterior sampling estimator for deep generative priors using Langevin dynamics, and empirically find that it produces accurate estimates with more diversity than MAP.

Key facts. Cited by 43 papers in the map (data through 14 Oct 2026). Builds on 38 of its 82 references that are in the map. First posted on arXiv 21 Jun 2021.

Builds on

38 of 82 references.

References · 38

  1. 2018A Style-Based Generator Architecture for Generative Adversarial Networkscited by 6,013
  2. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,101
  3. 2017Progressive Growing of GANs for Improved Quality, Stability, and Variationcited by 2,988
  4. 2018Glow: Generative Flow with Invertible 1x1 Convolutionscited by 1,545
  5. 2020Improved Techniques for Training Score-Based Generative Modelscited by 1,043
  6. 2016Pixel Recurrent Neural Networkscited by 816
  7. 2017Wasserstein GANcited by 639
  8. 2017Compressed Sensing using Generative Modelscited by 339
  9. 2020Deep Learning Techniques for Inverse Problems in Imagingcited by 291
  10. 2015Statistical physics of inference: Thresholds and algorithmscited by 128
  11. 2018Deep Decoder: Concise Image Representations from Untrained Non-convolutional Networkscited by 120
  12. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 116
26 more
  1. 2019Invertible generative models for inverse problems: mitigating representation error and dataset biascited by 94
  2. 2018Phase Retrieval Under a Generative Priorcited by 73
  3. 2017One Network to Solve Them All --- Solving Linear Inverse Problems using Deep Projection Modelscited by 67
  4. 2017Learned D-AMP: Principled Neural Network based Compressive Image Recoverycited by 65
  5. 2018Stochastic seismic waveform inversion using generative adversarial networks as a geological priorcited by 48
  6. 2019Learning-Based Low-Rank Approximationscited by 41
  7. 2018Blind Image Deconvolution using Deep Generative Priorscited by 40
  8. 2020Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximationcited by 39
  9. 2017Global Guarantees for Enforcing Deep Generative Priors by Empirical Riskcited by 37
  10. 2018Modeling Sparse Deviations for Compressed Sensing using Generative Modelscited by 33
  11. 2019Inverting Deep Generative models, One layer at a timecited by 33
  12. 2020Robust Compressed Sensing using Generative Modelscited by 33
  13. 2019Information-Theoretic Lower Bounds for Compressive Sensing with Generative Modelscited by 25
  14. 2020Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priorscited by 21
  15. 2019Exact asymptotics for phase retrieval and compressed sensing with random generative priorscited by 20
  16. 2019Fast and Provable ADMM for Learning with Generative Priorscited by 18
  17. 2018Task-Aware Compressed Sensing with Generative Adversarial Networkscited by 17
  18. 2019Inference with Deep Generative Priors in High Dimensionscited by 17
  19. 2017Inference in Deep Networks in High Dimensionscited by 13
  20. 2019Global Guarantees for Blind Demodulation with Generative Priorscited by 11
  21. 2019(Learned) Frequency Estimation Algorithms under Zipfian Distributioncited by 10
  22. 2018Algorithmic Aspects of Inverse Problems Using Generative Modelscited by 8
  23. 2019Robust One-Bit Recovery via ReLU Generative Networks: Near-Optimal Statistical Rate and Global Landscape Analysiscited by 8
  24. 2019Lower Bounds for Compressed Sensing with Generative Modelscited by 8
  25. 2019Surfing: Iterative optimization over incrementally trained deep networkscited by 5
  26. 2017Bayesian Compressive Sensing Using Normal Product Priorscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 13; 2023: 13; 2024: 6; 2025: 4; 2026: 3.

43 papers.

Sort:

By area:

  1. 2022Denoising Diffusion Restoration Modelscited by 963
  2. 2021Robust Compressed Sensing MRI with Deep Generative Priorscited by 286
  3. 2023Solving Linear Inverse Problems Provably via Posterior Sampling with Latent Diffusion Modelscited by 157
  4. 2023Beyond First-Order Tweedie: Solving Inverse Problems using Latent Diffusioncited by 78
  5. 2022Diffusion Model Based Posterior Sampling for Noisy Linear Inverse Problemscited by 60
  6. 2022MIMO Channel Estimation using Score-Based Generative Modelscited by 50
  7. 2023Solving Inverse Problems with Score-Based Generative Priors learned from Noisy Datacited by 40
  8. 2021Fairness for Image Generation with Uncertain Sensitive Attributescited by 31
  9. 2022Interpretable by Design: Learning Predictors by Composing Interpretable Queriescited by 28
  10. 2023What's in a Prior? Learned Proximal Networks for Inverse Problemscited by 25
  11. 2022Theoretical Perspectives on Deep Learning Methods in Inverse Problemscited by 22
  12. 2022Quantized Compressed Sensing with Score-based Generative Modelscited by 15
31 more
  1. 2023MRI Reconstruction with Side Information using Diffusion Modelscited by 15
  2. 2023Removing Structured Noise with Diffusion Modelscited by 14
  3. 2022Generative Principal Component Analysiscited by 12
  4. 2022Score-Guided Intermediate Layer Optimization: Fast Langevin Mixing for Inverse Problemscited by 11
  5. 2023CS4ML: A general framework for active learning with arbitrary data based on Christoffel functionscited by 11
  6. 2023AmbientFlow: Invertible generative models from incomplete, noisy measurementscited by 11
  7. 2022Non-Iterative Recovery from Nonlinear Observations using Generative Modelscited by 9
  8. 2021Data Summarization via Bilevel Optimizationcited by 8
  9. 2021Score-Based Generative Models for Robust Channel Estimationcited by 8
  10. 2022Deep Model-Based Architectures for Inverse Problems under Mismatched Priorscited by 8
  11. 2022Misspecified Phase Retrieval with Generative Priorscited by 7
  12. 2023A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensingcited by 7
  13. 2022Projected Gradient Descent Algorithms for Solving Nonlinear Inverse Problems with Generative Priorscited by 5
  14. 2023A unified framework for learning with nonlinear model classes from arbitrary linear samplescited by 5
  15. 2023Deep Joint Source-Channel Coding with Iterative Source Error Correctioncited by 3
  16. 2024Generalized Eigenvalue Problems with Generative Priorscited by 3
  17. 2023Optimizing Sampling Patterns for Compressed Sensing MRI with Diffusion Generative Modelscited by 2
  18. 2023Adversarial Score-Based Generative Models for MMSE-achieving AmBC Channel Estimationcited by 2
  19. 2024Spectral Guarantees for Adversarial Streaming PCAcited by 2
  20. 2025How many measurements are enough? Bayesian recovery in inverse problems with general distributionscited by 2
  21. 2025Learning Single Index Models with Diffusion Priorscited by 2
  22. 2022Regularized Training of Intermediate Layers for Generative Models for Inverse Problemscited by 1
  23. 2024Robustness and Exploration of Variational and Machine Learning Approaches to Inverse Problems: An Overviewcited by 1
  24. 2024Attention Incorporated Network for Sharing Low-rank, Image and K-space Information during MR Image Reconstruction to Achieve Single Breath-hold Cardiac Cine Imagingcited by 1
  25. 2024Integrating Generative and Physics-Based Models for Ptychographic Imaging with Uncertainty Quantificationcited by 1
  26. 2025Diffusion Model Based Signal Recovery Under 1-Bit Quantizationcited by 1
  27. 2026DeMark: A Query-Free Black-Box Attack on Deepfake Watermarking Defensescited by 1
  28. 2026Tunable Latent Generative Priors for Compressed Sensing and Inverse Problemscited by 1
  29. 2024Improving Decoupled Posterior Sampling for Inverse Problems using Data Consistency Constraintcited by 0
  30. 2025Diffusion Models for Solving Inverse Problems via Posterior Sampling with Piecewise Guidancecited by 0
  31. 2026Christoffel-DPS: Optimal sensor placement in diffusion posterior sampling for arbitrary distributionscited by 0