Sample-Measurement Tradeoff in Support Recovery Under a Subgaussian Prior

Data samples from 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)) . 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, and therefore k(2)/m overall measurements are necessary.