Learning mixtures of sparse linear regressions using sparse graph codes

摘要: In this paper, we consider the mixture of sparse linear regressions model. Let β (1) , . . ., β (L) ∈ ℂ n be L unknown sparse parameter vectors with a total of K non-zero elements. Noisy linear measurements are obtained in the form y i = x i H β(ℓ i ) + wi, each of which is generated randomly from one of the sparse vectors with the label ℓ i unknown. The goal is to estimate the parameter vectors efficiently with low sample and computational costs. This problem presents significant challenges as one needs to simultaneously solve the demixing problem of recovering the labels ℓ i as well as the estimation problem of recovering the sparse vectors β (ℓ) . Our solution to the problem leverages the connection between modern coding theory and statistical inference. We introduce a new algorithm, MixedColoring, which samples the mixture strategically using query vectors x i constructed based on ideas from sparse graph …