# Instance-Optimal Compressed Sensing via Posterior Sampling

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

## 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 (most cited first, 30 of 38)

- [A Style-Based Generator Architecture for Generative Adversarial Networks](https://mlsanity.com/paper/1812.04948/) (2018)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Progressive Growing of GANs for Improved Quality, Stability, and Variation](https://mlsanity.com/paper/1710.10196/) (2017)
- [Glow: Generative Flow with Invertible 1x1 Convolutions](https://mlsanity.com/paper/1807.03039/) (2018)
- [Improved Techniques for Training Score-Based Generative Models](https://mlsanity.com/paper/2006.09011/) (2020)
- [Pixel Recurrent Neural Networks](https://mlsanity.com/paper/1601.06759/) (2016)
- [Wasserstein GAN](https://mlsanity.com/paper/1701.07875/) (2017)
- [Compressed Sensing using Generative Models](https://mlsanity.com/paper/1703.03208/) (2017)
- [Deep Learning Techniques for Inverse Problems in Imaging](https://mlsanity.com/paper/2005.06001/) (2020)
- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [Deep Decoder: Concise Image Representations from Untrained Non-convolutional Networks](https://mlsanity.com/paper/1810.03982/) (2018)
- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [Invertible generative models for inverse problems: mitigating representation error and dataset bias](https://mlsanity.com/paper/1905.11672/) (2019)
- [Phase Retrieval Under a Generative Prior](https://mlsanity.com/paper/1807.04261/) (2018)
- [One Network to Solve Them All --- Solving Linear Inverse Problems using Deep Projection Models](https://mlsanity.com/paper/1703.09912/) (2017)
- [Learned D-AMP: Principled Neural Network based Compressive Image Recovery](https://mlsanity.com/paper/1704.06625/) (2017)
- [Stochastic seismic waveform inversion using generative adversarial networks as a geological prior](https://mlsanity.com/paper/1806.03720/) (2018)
- [Learning-Based Low-Rank Approximations](https://mlsanity.com/paper/1910.13984/) (2019)
- [Blind Image Deconvolution using Deep Generative Priors](https://mlsanity.com/paper/1802.04073/) (2018)
- [Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximation](https://mlsanity.com/paper/2005.03991/) (2020)
- [Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk](https://mlsanity.com/paper/1705.07576/) (2017)
- [Modeling Sparse Deviations for Compressed Sensing using Generative Models](https://mlsanity.com/paper/1807.01442/) (2018)
- [Inverting Deep Generative models, One layer at a time](https://mlsanity.com/paper/1906.07437/) (2019)
- [Robust Compressed Sensing using Generative Models](https://mlsanity.com/paper/2006.09461/) (2020)
- [Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models](https://mlsanity.com/paper/1908.10744/) (2019)
- [Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors](https://mlsanity.com/paper/2002.01697/) (2020)
- [Exact asymptotics for phase retrieval and compressed sensing with random generative priors](https://mlsanity.com/paper/1912.02008/) (2019)
- [Fast and Provable ADMM for Learning with Generative Priors](https://mlsanity.com/paper/1907.03343/) (2019)
- [Task-Aware Compressed Sensing with Generative Adversarial Networks](https://mlsanity.com/paper/1802.01284/) (2018)
- [Inference with Deep Generative Priors in High Dimensions](https://mlsanity.com/paper/1911.03409/) (2019)

## Built on by (most cited first, 30 of 43)

- [Denoising Diffusion Restoration Models](https://mlsanity.com/paper/2201.11793/) (2022)
- [Robust Compressed Sensing MRI with Deep Generative Priors](https://mlsanity.com/paper/2108.01368/) (2021)
- [Solving Linear Inverse Problems Provably via Posterior Sampling with Latent Diffusion Models](https://mlsanity.com/paper/2307.00619/) (2023)
- [Beyond First-Order Tweedie: Solving Inverse Problems using Latent Diffusion](https://mlsanity.com/paper/2312.00852/) (2023)
- [Diffusion Model Based Posterior Sampling for Noisy Linear Inverse Problems](https://mlsanity.com/paper/2211.12343/) (2022)
- [MIMO Channel Estimation using Score-Based Generative Models](https://mlsanity.com/paper/2204.07122/) (2022)
- [Solving Inverse Problems with Score-Based Generative Priors learned from Noisy Data](https://mlsanity.com/paper/2305.01166/) (2023)
- [Fairness for Image Generation with Uncertain Sensitive Attributes](https://mlsanity.com/paper/2106.12182/) (2021)
- [Interpretable by Design: Learning Predictors by Composing Interpretable Queries](https://mlsanity.com/paper/2207.00938/) (2022)
- [What's in a Prior? Learned Proximal Networks for Inverse Problems](https://mlsanity.com/paper/2310.14344/) (2023)
- [Theoretical Perspectives on Deep Learning Methods in Inverse Problems](https://mlsanity.com/paper/2206.14373/) (2022)
- [Quantized Compressed Sensing with Score-based Generative Models](https://mlsanity.com/paper/2211.13006/) (2022)
- [MRI Reconstruction with Side Information using Diffusion Models](https://mlsanity.com/paper/2303.14795/) (2023)
- [Removing Structured Noise with Diffusion Models](https://mlsanity.com/paper/2302.05290/) (2023)
- [Generative Principal Component Analysis](https://mlsanity.com/paper/2203.09693/) (2022)
- [Score-Guided Intermediate Layer Optimization: Fast Langevin Mixing for Inverse Problems](https://mlsanity.com/paper/2206.09104/) (2022)
- [CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions](https://mlsanity.com/paper/2306.00945/) (2023)
- [AmbientFlow: Invertible generative models from incomplete, noisy measurements](https://mlsanity.com/paper/2309.04856/) (2023)
- [Non-Iterative Recovery from Nonlinear Observations using Generative Models](https://mlsanity.com/paper/2205.15749/) (2022)
- [Data Summarization via Bilevel Optimization](https://mlsanity.com/paper/2109.12534/) (2021)
- [Score-Based Generative Models for Robust Channel Estimation](https://mlsanity.com/paper/2111.08177/) (2021)
- [Deep Model-Based Architectures for Inverse Problems under Mismatched Priors](https://mlsanity.com/paper/2207.13200/) (2022)
- [Misspecified Phase Retrieval with Generative Priors](https://mlsanity.com/paper/2210.05571/) (2022)
- [A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing](https://mlsanity.com/paper/2310.03758/) (2023)
- [Projected Gradient Descent Algorithms for Solving Nonlinear Inverse Problems with Generative Priors](https://mlsanity.com/paper/2209.10093/) (2022)
- [A unified framework for learning with nonlinear model classes from arbitrary linear samples](https://mlsanity.com/paper/2311.14886/) (2023)
- [Deep Joint Source-Channel Coding with Iterative Source Error Correction](https://mlsanity.com/paper/2302.09174/) (2023)
- [Generalized Eigenvalue Problems with Generative Priors](https://mlsanity.com/paper/2411.01326/) (2024)
- [Optimizing Sampling Patterns for Compressed Sensing MRI with Diffusion Generative Models](https://mlsanity.com/paper/2306.03284/) (2023)
- [Adversarial Score-Based Generative Models for MMSE-achieving AmBC Channel Estimation](https://mlsanity.com/paper/2309.05776/) (2023)

## 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.