Abstract

Large-scale datasets, other than being high-dimensional, can be highly heterogeneous. Real-world observations, when combined to form large datasets, often incorporate signals from different subpopulations. In this talk we will consider Mixed Sparse Linear Regression, a simple heterogeneous model for high-dimensional inference. This model includes the widely studied linear regression and phase retrieval models as special cases. We provide rigorous evidence for the existence of a fundamental statistical-computational tradeoff in this model, whenever the model parameters are sufficiently symmetric. Outside of this symmetric regime, we prove that an efficient algorithm is sample-optimal. To the best of our knowledge, this is the first thorough study of the interplay between mixture symmetry, signal sparsity, and their joint impact on the computational hardness of mixed sparse linear regression. This is joint work with Ramji Venkataramanan.