Sample-Measurement Tradeoff in Support Recovery Under a Subgaussian Prior

Data samples from R-d with common support of size kappa are accessed through m linear projections per sample. In the measurement-starved regime of m < kappa, how many samples are needed to recover the common support? We answer this question for a generative model with independent samples drawn from a subgaussian prior. We show that n = Theta((kappa(2)/m(2)) log(kappa(d - kappa))) samples are necessary and sufficient to exactly recover the support. Our proposed sample-optimal estimator has a closed-form expression and has computational complexity of O(dnm).