  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{BDJP17}
  has instead considered structure to come from a generative model
  $G: \R^k \to \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} \to \R^n$ with $O(1)$ layers
  and $O(kn)$ activations per layer, such that the range of $G$
  contains all $k$-sparse vectors.
 In compressed sensing, one would like to learn a structured signal x ∈ R n from a limited number of linear measurements y ≈ Ax. This is motivated by two observations: first, there are many situations where linear measurements are easy, in settings as varied as streaming algorithms, single-pixel cameras, genetic testing, and MRIs. Second, the unknown signals x being observed are structured or "compressible": although x lies in R n , it would take far fewer than n words to describe x. In such a situation, one can hope to estimate x well from a number of linear measurements that is closer to the size of the compressed representation of x than to its ambient dimension n. In order to do compressed sensing, you need a formal notion of how signals are expected to be structured. The classic answer is to use sparsity. Given linear measurements 1 y = Ax of an arbitrary vector x ∈ R n , one can hope to recover an estimate x * of x satisfying for some constant C and norm · . In this paper, we will focus on the 2 norm and achieving the guarantee with 3/4 probability. Thus, if x is well-approximated by a k-sparse vector x , it should be accurately recovered. Classic results such as [CRT06] show that (1) is achievable when A consists of m = O(k log n k ) independent Gaussian linear measurements. This bound is tight, and in fact no distribution of matrices with fewer rows can achieve this guarantee in either 1 or 2 [DIPW10] . Although compressed sensing has had success, sparsity is a limited notion of structure. Can we learn a richer model of signal structure from data, and use this to perform recovery? In recent years, deep convolutional neural networks have had great success in producing rich models for representing the manifold of images, notably with generative adversarial networks (GANs) [GPAM + 14] and variational autoencoders (VAEs) [KW14] . These methods produce generative models G : R k → R n that allow approximate sampling from the distribution of images. So a natural question is whether these generative models can be used for compressed sensing. In [BJPD17] it was shown how to use generative models to achieve a guarantee analogous to (1): for any L-Lipschitz G : R k → R n , one can achieve where r, δ > 0 are parameters, B k (r) denotes the radius-r 2 ball in R k and Lipschitzness is defined with respect to the 2 -norms, using only m = O(k log Lr δ ) measurements. Thus, the recovered vector is almost as good as the nearest point in the range of the generative model, rather than in the set of k-sparse vectors. We will refer to the problem of achieving the guarantee in (2) as "functionsparse recovery". Our main theorem is that the [BJPD17] result is tight: for any setting of parameters n, k, L, r, δ, there exists an L-Lipschitz function G : R k → R n such that any algorithm achieving (2) with 3/4 probability must have Ω(min(k log Lr δ , n)) linear measurements. Notably, the additive error δ that was unnecessary in sparse recovery is necessary for general Lipschitz generative model recovery. A concurrent paper [LS19] proves a lower bound for a restricted version of (2). They show a lower bound when the vector that x lies in the image of G and for a particular value of δ. Our results, in comparison, apply to the most general version of the problem and are proven using a simpler communication complexity technique. The second result in this paper is to directly relate the two notions of structure: sparsity and generative models. We produce a simple Lipschitz neural network G sp : R 2k → R n , with ReLU activations, 2 hidden layers, and maximum width O(kn), so that the range of G contains all k-sparse vectors. A second result of [BJPD17] is that for ReLU-based neural networks, one can avoid the additive δ term and achieve a different result from (2): using O(kd log W ) measurements, if d is the depth and W is the maximum number of activations per layer. Applying this result to our sparsity-producing network G sp implies, with O(k log n) measurements, recovery achieving the standard sparsity guarantee (1). So the generative-model representation of structure really is more powerful than sparsity.
Lower bound for compressed sensing w/ generative models that matches known upper bounds
{"src": "scitldr-AIC_train", "paper_id": "BkxP2mnq8S"}