On the Power of Compressed Sensing with Generative Models

The goal of compressed sensing is to learn a structured signal x from a limited number of noisy linear measurements y ≈ Ax. In traditional compressed sensing, "structure" is represented by sparsity in some known basis. Inspired by the success of deep learning in modeling images, recent work starting with (Bora et al., 2017) has instead considered structure to come from a generative model G : R k → R n . We present two results establishing the difficulty and strength of this latter task, showing that existing bounds are tight: First, we provide a lower bound matching the (Bora et al., 2017) upper bound for compressed sensing with L-Lipschitz generative models G which holds even for the more relaxed goal of non-uniform recovery. Second, we show that generative models generalize sparsity as a representation of structure by constructing a ReLU-based neural network with 2 hidden layers and O(n) activations per layer whose range is precisely the set of all k-sparse vectors.