In this paper, we consider the mixture of sparse linear regressions model.
Let ${\beta}^{(1)},\ldots,{\beta}^{(L)}\in\mathbb{C}^n$ be $ L $ unknown sparse
parameter vectors with a total of $ K $ non-zero coefficients. Noisy linear
measurements are obtained in the form $y_i={x}_i^H {\beta}^{(\ell_i)} + w_i$,
each of which is generated randomly from one of the sparse vectors with the
label $ \ell_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 $ \ell_i $ as well as the estimation problem
of recovering the sparse vectors $ {\beta}^{(\ell)} $.
Our solution to the problem leverages the connection between modern coding
theory and statistical inference. We introduce a new algorithm, Mixed-Coloring,
which samples the mixture strategically using query vectors $ {x}_i $
constructed based on ideas from sparse graph codes. Our novel code design
allows for both efficient demixing and parameter estimation. In the noiseless
setting, for a constant number of sparse parameter vectors, our algorithm
achieves the order-optimal sample and time complexities of $\Theta(K)$. In the
presence of Gaussian noise, for the problem with two parameter vectors (i.e.,
$L=2$), we show that the Robust Mixed-Coloring algorithm achieves near-optimal
$\Theta(K polylog(n))$ sample and time complexities. When $K=O(n^{\alpha})$ for
some constant $\alpha\in(0,1)$ (i.e., $K$ is sublinear in $n$), we can achieve
sample and time complexities both sublinear in the ambient dimension. In one of
our experiments, to recover a mixture of two regressions with dimension $n=500$
and sparsity $K=50$, our algorithm is more than $300$ times faster than EM
algorithm, with about one third of its sample cost.

本文研究稀疏线性回归的混合模型，提出了基于混合着色、编码理论和统计推断的新算法，实现了低样本和计算成本下的参数向量估计。

使用稀疏图代码学习稀疏线性回归混合模型

Learning Mixtures of Sparse Linear Regressions Using Sparse Graph Codes

Demixing refers to the challenge of identifying two structured signals given
only the sum of the two signals and prior information about their structures.
Examples include the problem of separating a signal that is sparse with respect
to one basis from a signal that is sparse with respect to a second basis, and
the problem of decomposing an observed matrix into a low-rank matrix plus a
sparse matrix. This paper describes and analyzes a framework, based on convex
optimization, for solving these demixing problems, and many others. This work
introduces a randomized signal model which ensures that the two structures are
incoherent, i.e., generically oriented. For an observation from this model,
this approach identifies a summary statistic that reflects the complexity of a
particular signal. The difficulty of separating two structured, incoherent
signals depends only on the total complexity of the two structures. Some
applications include (i) demixing two signals that are sparse in mutually
incoherent bases; (ii) decoding spread-spectrum transmissions in the presence
of impulsive errors; and (iii) removing sparse corruptions from a low-rank
matrix. In each case, the theoretical analysis of the convex demixing method
closely matches its empirical behavior.

本文提出并分析了一种基于凸优化的框架，用于解决混合问题，并介绍了一种随机信号模型，以确保两个结构不互相关，即呈一般性定向。应用包括使用凸混合方法消除低秩矩阵中的稀疏损坏。