Support Recovery of Sparse Signals from a Mixture of Linear Measurements
  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 $\ell$, to
recover the support of all the $\ell$ unknown vectors in the mixture with high
probability when each individual component is a $k$-sparse $n$-dimensional
vector.
