A Provably Convergent Scheme for Compressive Sensing Under Random Generative Priors

By Wen Huang, Paul Hand, Reinhard Heckel, Vladislav Voroninski. 2018

33 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Physics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Mathematical Physics

In Optimization & Training

Citations in the corpus

GAN Inversion: A Survey (2021, background): “assumptions are required [122] for gradient descent to find”
Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximation (2020, unknown): “, 2014)) and then using the resulting image models to regularize problems such as compressed sensing (Bora et al., 2017; Hand & Voroninski, 2018; Huang et al., 2018), denoising (Heckel et al.”
Inverting Deep Generative models, One layer at a time (2019, methodology): “In this section, we describe our experimental setup and report the performance comparisons of our algorithms with the gradient descent method [15, 12]4.”
When and How Can Deep Generative Models be Inverted? (2020, methodology): “However, since the theory provided here focuses on fully connected models, this setting was chosen for the experimental section, similar to other previous work [14, 17] that study the inversion process.”