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 <italic>et al.</italic>, 2017) it was shown roughly <inline-formula> <tex-math notation="LaTeX">$O(k\log L)$ </tex-math></inline-formula> random Gaussian measurements suffice for accurate recovery when the generative model is an <inline-formula> <tex-math notation="LaTeX">$L$ </tex-math></inline-formula>-Lipschitz function with bounded <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-dimensional inputs, and <inline-formula> <tex-math notation="LaTeX">$O(kd \log w)$ </tex-math></inline-formula> measurements suffice when the generative model is a <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-input ReLU network with depth <inline-formula> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula> and width <inline-formula> <tex-math notation="LaTeX">$w$ </tex-math></inline-formula>. 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 <inline-formula> <tex-math notation="LaTeX">$L$ </tex-math></inline-formula>-Lipschitz generative model capable of generating group-sparse signals, and show that the resulting necessary number of measurements is <inline-formula> <tex-math notation="LaTeX">$\Omega (k \log L)$ </tex-math></inline-formula>; (ii) Using similar ideas, we construct ReLU networks with high depth and/or high depth for which the necessary number of measurements scales as <inline-formula> <tex-math notation="LaTeX">$\Omega \left({kd \frac {\log w}{\log n}}\right)$ </tex-math></inline-formula> (with output dimension <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>), and in some cases <inline-formula> <tex-math notation="LaTeX">$\Omega (kd \log w)$ </tex-math></inline-formula>. As a result, we establish that the scaling laws derived in (Bora <italic>et al.</italic>, 2017) are optimal or near-optimal in the absence of further assumptions.