Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval

Jianqing Fan, Han Liu, Zhaoran Wang +1

We study the fundamental tradeoffs between statistical accuracy and computational tractability in the analysis of high dimensional heterogeneous data. As examples, we study sparse…