Sample-Measurement Tradeoff in Support Recovery under a Subgaussian Prior

Abstract

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.

A preliminary version of this paper appeared at IEEE International Symposium on Information Theory 2019