Learning Mixtures of Sparse Linear Regressions Using Sparse Graph Codes

摘要: In this paper, we consider the mixture of sparse linear regressions model. Let $\boldsymbol {\beta }^{(1)},\ldots, \boldsymbol }^{(L)}\in \mathbb {C} ^{n}$ be $L $ unknown parameter vectors with a total $K non-zero elements. Noisy measurements are obtained in form $y_{i} = {x}_{i} ^{\mathrm{ H}} }^{(\ell _{i})} + w_{i}$ , each which is generated randomly from one label $\ell _{i} unknown. The goal to estimate efficiently low sample and computational costs. This problem presents significant challenges as needs simultaneously solve demixing recovering labels well estimation }^{(\ell)} . Our solution leverages connection between modern coding theory statistical inference. We introduce new algorithm, Mixed-Coloring samples strategically using query constructed based on ideas graph codes. novel code design allows for both efficient estimation. To find $K$ elements, it clear that need at least $\Theta (K)$ measurements, thus time complexity noiseless setting, constant number vectors, our algorithm achieves order-optimal complexities presence Gaussian noise, 1 two (i.e., 2$ ), show Robust near-optimal (K \mathop {\mathrm {polylog}}\nolimits (n))$ complexities. When \mathcal {O}(n^{\alpha })$ some $\alpha \in (0,1)$ sublinear $n$ can achieve ambient dimension. experiments, recover dimension $n 500$ sparsity 50$ more than 300 times faster EM about third its cost. proposed works even when noise non-Gaussian nature, but guarantees difficult obtain.