Lower Bounds for Compressed Sensing with Generative Models

Abstract

The goal of compressed sensing is to learn a structured signal $x$ from a limited number of noisy linear measurements $y\approx 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~\cite{BJPD17} has instead considered structure to come from a generative model $G:{\mathbb{R}}^k\to {\mathbb{R}}^n$. We present two results establishing the difficulty of this latter task, showing that existing bounds are tight. First, we provide a lower bound matching the~\cite{BJPD17} upper bound for compressed sensing from $L$-Lipschitz generative models $G$. In particular, there exists such a function that requires roughly $\Omega (k\log L)$ linear measurements for sparse recovery to be possible. This holds even for the more relaxed goal of \emph{nonuniform} recovery. Second, we show that generative models generalize sparsity as a representation of structure. In particular, we construct a ReLU-based neural network $G:{\mathbb{R}}^{2k}\to {\mathbb{R}}^n$ with $O(1)$ layers and $O(kn)$ activations per layer, such that the range of $G$ contains all $k$-sparse vectors.

References in corpus (2)

• Auto-Encoding Variational Bayes
• Compressed Sensing using Generative Models

Cited by in corpus (4)

• Robust Compressed Sensing MRI with Deep Generative Priors
• Deep Learning Techniques for Inverse Problems in Imaging
• Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors
• Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models