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.
翻译:从简单测量中恢复对稀散矢量的支持是一个广泛研究的问题,这个问题在压缩感测、1比位压缩感测和比较一般的单一指数模型的框架内审议。我们考虑这一问题的概括性:线性回归混合物和线性分类器混合物,分别的目标是利用少量可能吵闹的线性测量和1比位测量分别恢复对多种稀散矢量的支持。关键的挑战在于不同矢量的测量是随机混合的。这两个问题最近也引起了注意。在线性分类器的混合物中,观测结果与被询问的超平面随机不明矢量的一侧对应,而在被询问的超平面回归混合物中,我们观察到了对随机未知矢量的预测。从混合物中恢复未知矢量的首要步骤是首先确定所有单个矢量的支持。在这两种模型中,我们研究足以恢复混合物中所有组成矢量的测量数量。我们提供算法,用美元($)的多元度测量数据对应一个随机矢量,而每个矢量则以美元表示的正值/正数为美元,当每个矢量的回收概率为美元时,每个矢量中,每个矢量的度支持是无以美元。