# A Provably Convergent Scheme for Compressive Sensing under Random Generative Priors

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Dec 2018.

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

- [GAN Inversion: A Survey](https://mlsanity.com/paper/2101.05278/) (2021)
- [Unsupervised MRI Reconstruction via Zero-Shot Learned Adversarial Transformers](https://mlsanity.com/paper/2105.08059/) (2021)
- [Solving Inverse Problems by Joint Posterior Maximization with Autoencoding Prior](https://mlsanity.com/paper/2103.01648/) (2021)
- [Theoretical Perspectives on Deep Learning Methods in Inverse Problems](https://mlsanity.com/paper/2206.14373/) (2022)
- [Score-Guided Intermediate Layer Optimization: Fast Langevin Mixing for Inverse Problems](https://mlsanity.com/paper/2206.09104/) (2022)
- [Bayesian Inversion for Nonlinear Imaging Models using Deep Generative Priors](https://mlsanity.com/paper/2203.10078/) (2022)
- [Inverse problem regularization with hierarchical variational autoencoders](https://mlsanity.com/paper/2303.11217/) (2023)
- [Deep ReLU networks -- injectivity capacity upper bounds](https://mlsanity.com/paper/2412.19677/) (2024)
- [Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension](https://mlsanity.com/paper/2111.14486/) (2021)
- [Non-Convex Compressed Sensing with Training Data](https://mlsanity.com/paper/2101.08310/) (2021)
- [Signal Recovery with Non-Expansive Generative Network Priors](https://mlsanity.com/paper/2204.13599/) (2022)
- [On the Fine-Grained Hardness of Inverting Generative Models](https://mlsanity.com/paper/2309.05795/) (2023)
- [Consistent Approximations in Composite Optimization](https://mlsanity.com/paper/2201.05250/) (2022)
- [Learning Trees of ℓ0-Minimization Problems](https://mlsanity.com/paper/2302.02548/) (2023)
- [A Linearly Convergent GAN Inversion-based Algorithm for Reverse Engineering of Deceptions](https://mlsanity.com/paper/2306.04756/) (2023)

## Abstract (arXiv)

Deep generative modeling has led to new and state of the art approaches for enforcing structural priors in a variety of inverse problems. In contrast to priors given by sparsity, deep models can provide direct low-dimensional parameterizations of the manifold of images or signals belonging to a particular natural class, allowing for recovery algorithms to be posed in a low-dimensional space. This dimensionality may even be lower than the sparsity level of the same signals when viewed in a fixed basis. What is not known about these methods is whether there are computationally efficient algorithms whose sample complexity is optimal in the dimensionality of the representation given by the generative model. In this paper, we present such an algorithm and analysis. Under the assumption that the generative model is a neural network that is sufficiently expansive at each layer and has Gaussian weights, we provide a gradient descent scheme and prove that for noisy compressive measurements of a signal in the range of the model, the algorithm converges to that signal, up to the noise level. The scaling of the sample complexity with respect to the input dimensionality of the generative prior is linear, and thus can not be improved except for constants and factors of other variables. To the best of the authors' knowledge, this is the first recovery guarantee for compressive sensing under generative priors by a computationally efficient algorithm.