# Support Recovery of Sparse Signals from a Mixture of Linear Measurements

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 49 references that are in the map.
- First posted on arXiv 10 Jun 2021.

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

- [Introduction to Tensor Decompositions and their Applications in Machine Learning](https://mlsanity.com/paper/1711.10781/) (2017)
- [Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization](https://mlsanity.com/paper/1608.05749/) (2016)
- [Spectral Experts for Estimating Mixtures of Linear Regressions](https://mlsanity.com/paper/1306.3729/) (2013)
- [Iterative Least Trimmed Squares for Mixed Linear Regression](https://mlsanity.com/paper/1902.03653/) (2019)
- [Learning Mixtures of Low-Rank Models](https://mlsanity.com/paper/2009.11282/) (2020)
- [Learning Mixtures of Linear Classifiers](https://mlsanity.com/paper/1311.2547/) (2013)
- [Sample Complexity of Learning Mixtures of Sparse Linear Regressions](https://mlsanity.com/paper/1910.14106/) (2019)
- [Recovery of Sparse Signals from a Mixture of Linear Samples](https://mlsanity.com/paper/2006.16406/) (2020)
- [Recovery of sparse linear classifiers from mixture of responses](https://mlsanity.com/paper/2010.12087/) (2020)
- [Superset Technique for Approximate Recovery in One-Bit Compressed Sensing](https://mlsanity.com/paper/1910.13971/) (2019)
- [Convergence of Parameter Estimates for Regularized Mixed Linear Regression Models](https://mlsanity.com/paper/1903.09235/) (2019)

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

- [On Learning Mixture of Linear Regressions in the Non-Realizable Setting](https://mlsanity.com/paper/2205.13166/) (2022)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [Support Recovery in Mixture Models with Sparse Parameters](https://mlsanity.com/paper/2202.11940/) (2022)
- [Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms](https://mlsanity.com/paper/2406.01149/) (2024)
- [Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements](https://mlsanity.com/paper/2609.32176/) (2026)

## Abstract (arXiv)

Recovery of support of a sparse vector from simple measurements is a widely-studied problem, considered under the frameworks of compressed sensing, 1-bit compressed sensing, and more general single index models. We consider generalizations of this problem: mixtures of linear regressions, and mixtures of linear classifiers, where the goal is to recover supports of multiple sparse vectors using only a small number of possibly noisy linear, and 1-bit measurements respectively. The key challenge is that the measurements from different vectors are randomly mixed. Both of these problems have also received attention recently. In mixtures of linear classifiers, the observations correspond to the side of queried hyperplane a random unknown vector lies in, whereas in mixtures of linear regressions we observe the projection of a random unknown vector on the queried hyperplane. The primary step in recovering the unknown vectors from the mixture is to first identify the support of all the individual component vectors. In this work, we study the number of measurements sufficient for recovering the supports of all the component vectors in a mixture in both these models. We provide algorithms that use a number of measurements polynomial in k, log n and quasi-polynomial in ℓ, to recover the support of all the ℓ unknown vectors in the mixture with high probability when each individual component is a k-sparse n-dimensional vector.