Abstract
In the problem of multiple support recovery, we are given access to linear measurements of multiple sparse samples in 鈩漗d. These samples can be partitioned into 鈩 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 鈩 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 脮(k^4鈩揯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.