# Multiple Support Recovery Using Very Few Measurements Per Sample

arXiv: https://arxiv.org/abs/2105.09855 · HTML: https://mlsanity.com/paper/2105.09855/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 38 references that are in the map.
- First posted on arXiv 20 May 2021.

## Builds on (most cited first, 6 of 6)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Learning Mixtures of Linear Regressions with Nearly Optimal Complexity](https://mlsanity.com/paper/1802.07895/) (2018)
- [Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments](https://mlsanity.com/paper/1912.07629/) (2019)
- [Sample Complexity of Learning Mixtures of Sparse Linear Regressions](https://mlsanity.com/paper/1910.14106/) (2019)
- [Semidefinite Programs for Exact Recovery of a Hidden Community](https://mlsanity.com/paper/1602.06410/) (2016)
- [High-dimensional Joint Sparsity Random Effects Model for Multi-task Learning](https://mlsanity.com/paper/1309.6814/) (2013)

## Built on by (most cited first, 1 of 1)

- [Do algorithms and barriers for sparse principal component analysis extend to other structured settings?](https://mlsanity.com/paper/2307.13535/) (2023)

## Abstract (arXiv)

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 tildeO(k4ℓ4/m4) 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.