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 (12)

• Finding community structure in networks using the eigenvectors of matrices
• User-friendly tail bounds for sums of random matrices
• Spectral clustering and the high-dimensional stochastic blockmodel
• Support union recovery in high-dimensional multivariate regression
• Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
• Subspace Methods for Joint Sparse Recovery
• Information theoretic bounds for Compressed Sensing
• Recursive Recovery of Sparse Signal Sequences from Compressive Measurements: A Review
• Distributed Private Heavy Hitters
• Semidefinite Programs for Exact Recovery of a Hidden Community
• Sample Complexity of Learning Mixtures of Sparse Linear Regressions
• Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments