Detailed Instructions: In this task, you are given the abstract of a research paper. Your task is to generate a summary of this abstract. Your summary should not be very short, but it's better if it's not more than 30 words.
Q: The goal of compressed sensing is to learn a structured signal $x$
from a limited number of noisy linear measurements $y pprox 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{BDJP17}
has instead considered structure to come from a generative model
$G: \R^k o \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{BDJP17} 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: \R^{2k} o \R^n$ with $O(1)$ layers
and $O(kn)$ activations per layer, such that the range of $G$
contains all $k$-sparse vectors.

A:
Lower bound for compressed sensing w/ generative models that matches known upper bounds