  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.
