# Lower Bounds for Compressed Sensing with Generative Models

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2019.

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

- [Robust Compressed Sensing MRI with Deep Generative Priors](https://mlsanity.com/paper/2108.01368/) (2021)
- [Instance-Optimal Compressed Sensing via Posterior Sampling](https://mlsanity.com/paper/2106.11438/) (2021)
- [Source Localization of Graph Diffusion via Variational Autoencoders for Graph Inverse Problems](https://mlsanity.com/paper/2206.12327/) (2022)
- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [Adaptive Compressed Sensing with Diffusion-Based Posterior Sampling](https://mlsanity.com/paper/2407.08256/) (2024)
- [Score-Guided Intermediate Layer Optimization: Fast Langevin Mixing for Inverse Problems](https://mlsanity.com/paper/2206.09104/) (2022)
- [Chasing Better Deep Image Priors between Over- and Under-parameterization](https://mlsanity.com/paper/2410.24187/) (2024)
- [Active Learning for Conditional Generative Compressed Sensing](https://mlsanity.com/paper/2605.05435/) (2026)

## Abstract (arXiv)

The goal of compressed sensing is to learn a structured signal x from a limited number of noisy linear measurements y ≈ Ax. In traditional compressed sensing, "structure" is represented by sparsity in some known basis. Inspired by the success of deep learning in modeling images, recent work starting with~citeBJPD17 has instead considered structure to come from a generative model G: ℝk → ℝn. We present two results establishing the difficulty of this latter task, showing that existing bounds are tight. First, we provide a lower bound matching the~citeBJPD17 upper bound for compressed sensing from L-Lipschitz generative models G. In particular, there exists such a function that requires roughly Omega(k log L) linear measurements for sparse recovery to be possible. This holds even for the more relaxed goal of nonuniform recovery. Second, we show that generative models generalize sparsity as a representation of structure. In particular, we construct a ReLU-based neural network G: ℝ2k → ℝn with O(1) layers and O(kn) activations per layer, such that the range of G contains all k-sparse vectors.