Skip to main content
A Max-Product EM Algorithm for Reconstructing Markov-Tree Sparse Signals From Compressive Samples
IEEE Transactions on Signal Processing
  • Zhao Song, Iowa State University
  • Aleksandar Dogandžić, Iowa State University
Document Type
Publication Date
We propose a Bayesian expectation-maximization (EM) algorithm for reconstructing Markov-tree sparse signals via belief propagation. The measurements follow an underdetermined linear model where the regression-coefficient vector is the sum of an unknown approximately sparse signal and a zero-mean white Gaussian noise with an unknown variance. The signal is composed of large- and small-magnitude components identified by binary state variables whose probabilistic dependence structure is described by a Markov tree. Gaussian priors are assigned to the signal coefficients given their state variables and the Jeffreys' noninformative prior is assigned to the noise variance. Our signal reconstruction scheme is based on an EM iteration that aims at maximizing the posterior distribution of the signal and its state variables given the noise variance. We construct the missing data for the EM iteration so that the complete-data posterior distribution corresponds to a hidden Marcov tree (HMT) probabilistic graphical model that contains no loops and implement its maximization (M) step via a max-product algorithm. This EM algorithm estimates the vector of state variables as well as solves iteratively a linear system of equations to obtain the corresponding signal estimate. We select the noise variance so that the corresponding estimated signal and state variables obtained upon convergence of the EM iteration have the largest marginal posterior distribution. We compare the proposed and existing state-of-the-art reconstruction methods via signal and image reconstruction experiments.

This is a post-print of an article from IEEE Transactions on Signal Processing 61 (2013): 5917–5931, doi:10.1109/TSP.2013.2277833. Posted with permission.

© 2013 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Copyright Owner
File Format
Citation Information
Zhao Song and Aleksandar Dogandžić. "A Max-Product EM Algorithm for Reconstructing Markov-Tree Sparse Signals From Compressive Samples" IEEE Transactions on Signal Processing Vol. 61 Iss. 23 (2013) p. 5917 - 5931
Available at: