Information-Theoretic Lower Bounds for Compressive Sensing with
  Generative Models
  It has recently been shown that for compressive sensing, significantly fewer
measurements may be required if the sparsity assumption is replaced by the
assumption the unknown vector lies near the range of a suitably-chosen
generative model. In particular, in (Bora {\em et al.}, 2017) it was shown
roughly $O(k\log L)$ random Gaussian measurements suffice for accurate recovery
when the generative model is an $L$-Lipschitz function with bounded
$k$-dimensional inputs, and $O(kd \log w)$ measurements suffice when the
generative model is a $k$-input ReLU network with depth $d$ and width $w$. In
this paper, we establish corresponding algorithm-independent lower bounds on
the sample complexity using tools from minimax statistical analysis. In
accordance with the above upper bounds, our results are summarized as follows:
(i) We construct an $L$-Lipschitz generative model capable of generating
group-sparse signals, and show that the resulting necessary number of
measurements is $\Omega(k \log L)$; (ii) Using similar ideas, we construct ReLU
networks with high depth and/or high depth for which the necessary number of
measurements scales as $\Omega\big( kd \frac{\log w}{\log n}\big)$ (with output
dimension $n$), and in some cases $\Omega(kd \log w)$. As a result, we
establish that the scaling laws derived in (Bora {\em et al.}, 2017) are
optimal or near-optimal in the absence of further assumptions.
