A Bayesian max-product EM algorithm for reconstructing structured sparse signals

We present a Bayesian expectation-maximization (EM) algorithm for sparse signal reconstruction via belief propagation. The measurements follow an underdetermined linear model where the regression-coefficient vector is the sum of an unknown sparse signal component and a zero-mean white Gaussian component with an unknown variance. We use a hidden Markov tree (HMT) to describe the probabilistic dependence structure of the binary state variables that identify the nonzero signal coefficients and assign a noninformative prior to the nonzero signal coefficients. Our signal reconstruction scheme is based on an EM iteration that aims at maximizing the posterior distribution of the sparse signal component and its state variables given the variance of the random signal component. We employ a max-product algorithm to implement the maximization (M) step of our EM iteration. The variance of the random signal component is a regularization parameter that controls the sparsity of the sparse signal component. We select this tuning parameter by maximizing an unconstrained sparsity selection (USS) objective function. Our numerical examples show that the proposed algorithm achieves a better reconstruction performance compared with the state-of-the-art methods.