Multiple Support Recovery Using Very Few Measurements Per Sample
  In the problem of multiple support recovery, we are given access to linear
measurements of multiple sparse samples in $\mathbb{R}^{d}$. These samples can
be partitioned into $\ell$ groups, with samples having the same support
belonging to the same group. For a given budget of $m$ measurements per sample,
the goal is to recover the $\ell$ underlying supports, in the absence of the
knowledge of group labels. We study this problem with a focus on the
measurement-constrained regime where $m$ is smaller than the support size $k$
of each sample. We design a two-step procedure that estimates the union of the
underlying supports first, and then uses a spectral algorithm to estimate the
individual supports. Our proposed estimator can recover the supports with $m<k$
measurements per sample, from $\tilde{O}(k^{4}\ell^{4}/m^{4})$ samples. Our
guarantees hold for a general, generative model assumption on the samples and
measurement matrices. We also provide results from experiments conducted on
synthetic data and on the MNIST dataset.
