Recovery of Sparse Signals from a Mixture of Linear Samples

Soumyabrata Pal, Arya Mazumdar
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:7466-7475, 2020.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-pal20a, title = {Recovery of Sparse Signals from a Mixture of Linear Samples}, author = {Pal, Soumyabrata and Mazumdar, Arya}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {7466--7475}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/pal20a/pal20a.pdf}, url = {https://proceedings.mlr.press/v119/pal20a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Recovery of Sparse Signals from a Mixture of Linear Samples %A Soumyabrata Pal %A Arya Mazumdar %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-pal20a %I PMLR %P 7466--7475 %U https://proceedings.mlr.press/v119/pal20a.html %V 119 %X 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.
APA
Pal, S. & Mazumdar, A.. (2020). Recovery of Sparse Signals from a Mixture of Linear Samples. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:7466-7475 Available from https://proceedings.mlr.press/v119/pal20a.html.

Related Material