Multiple Support Recovery Using Very Few Measurements Per Sample

Abstract

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.

References in corpus (3)

• Finding community structure in networks using the eigenvectors of matrices
• Sample Complexity of Learning Mixtures of Sparse Linear Regressions
• Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments