# Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models

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

## Key facts

- Cited by 25 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 28 Aug 2019.

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

- [Robust Compressed Sensing MRI with Deep Generative Priors](https://mlsanity.com/paper/2108.01368/) (2021)
- [Intermediate Layer Optimization for Inverse Problems using Deep Generative Models](https://mlsanity.com/paper/2102.07364/) (2021)
- [Instance-Optimal Compressed Sensing via Posterior Sampling](https://mlsanity.com/paper/2106.11438/) (2021)
- [Theoretical Perspectives on Deep Learning Methods in Inverse Problems](https://mlsanity.com/paper/2206.14373/) (2022)
- [Provable Compressed Sensing with Generative Priors via Langevin Dynamics](https://mlsanity.com/paper/2102.12643/) (2021)
- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [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)
- [Non-Iterative Recovery from Nonlinear Observations using Generative Models](https://mlsanity.com/paper/2205.15749/) (2022)
- [A coherence parameter characterizing generative compressed sensing with Fourier measurements](https://mlsanity.com/paper/2207.09340/) (2022)
- [Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors](https://mlsanity.com/paper/2108.03570/) (2021)
- [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)
- [Integrating Intermediate Layer Optimization and Projected Gradient Descent for Solving Inverse Problems with Diffusion Models](https://mlsanity.com/paper/2505.20789/) (2025)
- [Projected Gradient Descent Algorithms for Solving Nonlinear Inverse Problems with Generative Priors](https://mlsanity.com/paper/2209.10093/) (2022)
- [Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension](https://mlsanity.com/paper/2111.14486/) (2021)
- [Generalization analysis of an unfolding network for analysis-based Compressed Sensing](https://mlsanity.com/paper/2303.05582/) (2023)
- [Learning Single Index Models with Diffusion Priors](https://mlsanity.com/paper/2505.21135/) (2025)
- [Image Restoration via Diffusion Models with Dynamic Resolution](https://mlsanity.com/paper/2605.14267/) (2026)
- [Learning Generative Prior with Latent Space Sparsity Constraints](https://mlsanity.com/paper/2105.11956/) (2021)
- [On the Fine-Grained Hardness of Inverting Generative Models](https://mlsanity.com/paper/2309.05795/) (2023)
- [Diffusion Model Based Signal Recovery Under 1-Bit Quantization](https://mlsanity.com/paper/2511.12471/) (2025)
- [MrSARP: A Hierarchical Deep Generative Prior for SAR Image Super-resolution](https://mlsanity.com/paper/2212.00069/) (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)

It has recently been shown that for compressive sensing, significantly fewer measurements may be required if the sparsity assumption is replaced by the assumption the unknown vector lies near the range of a suitably-chosen generative model. In particular, in (Bora em et al., 2017) it was shown roughly O(klog L) random Gaussian measurements suffice for accurate recovery when the generative model is an L-Lipschitz function with bounded k-dimensional inputs, and O(kd log w) measurements suffice when the generative model is a k-input ReLU network with depth d and width w. In this paper, we establish corresponding algorithm-independent lower bounds on the sample complexity using tools from minimax statistical analysis. In accordance with the above upper bounds, our results are summarized as follows: (i) We construct an L-Lipschitz generative model capable of generating group-sparse signals, and show that the resulting necessary number of measurements is Omega(k log L); (ii) Using similar ideas, we construct ReLU networks with high depth and/or high depth for which the necessary number of measurements scales as Omegabig( kd fraclog wlog nbig) (with output dimension n), and in some cases Omega(kd log w). As a result, we establish that the scaling laws derived in (Bora em et al., 2017) are optimal or near-optimal in the absence of further assumptions.