  We study the problem of recovering the common $k$-sized support of a set of
$n$ samples of dimension $d$, using $m$ noisy linear measurements per sample.
Most prior work has focused on the case when $m$ exceeds $k$, in which case $n$
of the order $(k/m)\log(d/k)$ is both necessary and sufficient. Thus, in this
regime, only the total number of measurements across the samples matter, and
there is not much benefit in getting more than $k$ measurements per sample. In
the measurement-constrained regime where we have access to fewer than $k$
measurements per sample, we show an upper bound of $O((k^{2}/m^{2})\log d)$ on
the sample complexity for successful support recovery when $m\ge 2\log d$.
Along with the lower bound from our previous work, this shows a sharp phase
transition for the sample complexity of this problem around $k/m=1$. In fact,
our proposed algorithm is sample-optimal in both the regimes. It follows that,
in the $m\ll k$ regime, multiple measurements from the same sample are more
valuable than measurements from different samples.
