论文标题
从线性样品的混合物中恢复稀疏信号
Recovery of Sparse Signals from a Mixture of Linear Samples
论文作者
论文摘要
线性回归的混合物是一种流行的学习理论模型，可广泛用来代表异质数据。以最简单的形式，该模型假设标签是从两个不同的线性模型中的任何一个生成并混合在一起的。 Yin等人的最新作品。和Krishnamurthy等人，2019年，重点介绍了该问题模型恢复的实验设计设置。假定可以设计和查询这些功能以获取其标签。查询时，Oracle随机选择了两个不同的稀疏线性模型之一，并相应地生成标签。需要多少此类甲骨文查询才能同时恢复两个模型？这个问题也可以被认为是众所周知的压缩传感问题的概括（Candès和Tao，2005； Donoho，2006年）。在这项工作中，我们解决了此查询复杂性问题，并提供有效的算法，从而改善了以前最著名的结果。
Mixture of linear regressions is a popular learning theoretic model that is used widely to represent heterogeneous data. In the simplest form, this model assumes that the labels are generated from either of two different linear models and mixed together. Recent works of Yin et al. and Krishnamurthy et al., 2019, focus on an experimental design setting of model recovery for this problem. It is assumed that the features can be designed and queried with to obtain their label. When queried, an oracle randomly selects one of the two different sparse linear models and generates a label accordingly. How many such oracle queries are needed to recover both of the models simultaneously? This question can also be thought of as a generalization of the well-known compressed sensing problem (Candès and Tao, 2005, Donoho, 2006). In this work, we address this query complexity problem and provide efficient algorithms that improves on the previously best known results.
