  Data samples from $\mathbb{R}^{d}$ with a common support of size $k$ are
accessed through $m$ random linear projections (measurements) per sample. It is
well-known that roughly $k$ measurements from a single sample are sufficient to
recover the support. In the multiple sample setting, do $k$ overall
measurements still suffice when only $m$ measurements per sample are allowed,
with $m<k$? We answer this question in the negative by considering a generative
model setting with independent samples drawn from a subgaussian prior. We show
that $n=\Theta((k^2/m^2)\cdot\log k(d-k))$ samples are necessary and sufficient
to recover the support exactly. In turn, this shows that when $m<k$, $k$
overall measurements are insufficient for support recovery; instead we need
about $m$ measurements each from $k^{2}/m^2$ samples, i.e., $k^{2}/m$ overall
measurements are necessary.
