Constant-Expansion Suffices for Compressed Sensing with Generative
  Priors
  Generative neural networks have been empirically found very promising in
providing effective structural priors for compressed sensing, since they can be
trained to span low-dimensional data manifolds in high-dimensional signal
spaces. Despite the non-convexity of the resulting optimization problem, it has
also been shown theoretically that, for neural networks with random Gaussian
weights, a signal in the range of the network can be efficiently, approximately
recovered from a few noisy measurements. However, a major bottleneck of these
theoretical guarantees is a network expansivity condition: that each layer of
the neural network must be larger than the previous by a logarithmic factor.
Our main contribution is to break this strong expansivity assumption, showing
that constant expansivity suffices to get efficient recovery algorithms,
besides it also being information-theoretically necessary. To overcome the
theoretical bottleneck in existing approaches we prove a novel uniform
concentration theorem for random functions that might not be Lipschitz but
satisfy a relaxed notion which we call "pseudo-Lipschitzness." Using this
theorem we can show that a matrix concentration inequality known as the Weight
Distribution Condition (WDC), which was previously only known to hold for
Gaussian matrices with logarithmic aspect ratio, in fact holds for constant
aspect ratios too. Since the WDC is a fundamental matrix concentration
inequality in the heart of all existing theoretical guarantees on this problem,
our tighter bound immediately yields improvements in all known results in the
literature on compressed sensing with deep generative priors, including one-bit
recovery, phase retrieval, low-rank matrix recovery, and more.
