Hybrid approximate message passing for generalized group sparsity

Alyson K. Fletcher, Sundeep Rangan

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider the problem of estimating a group sparse vector x ε ℝn under a generalized linear measurement model. Group sparsity of x means the activity of different components of the vector occurs in groups - a feature common in estimation problems in image processing, simultaneous sparse approximation and feature selection with grouped variables. Unfortunately, many current group sparse estimation methods require that the groups are non-overlapping. This work considers problems with what we call generalized group sparsity where the activity of the different components of x are modeled as functions of a small number of boolean latent variables. We show that this model can incorporate a large class of overlapping group sparse problems including problems in sparse multivariable polynomial regression and gene expression analysis. To estimate vectors with such group sparse structures, the paper proposes to use a recently-developed hybrid generalized approximate message passing (HyGAMP) method. Approximate message passing (AMP) refers to a class of algorithms based on Gaussian and quadratic approximations of loopy belief propagation for estimation of random vectors under linear measurements. The HyGAMP method extends the AMP framework to incorporate priors on x described by graphical models of which generalized group sparsity is a special case. We show that the HyGAMP algorithm is computationally efficient, general and offers superior performance in certain synthetic data test cases.

Original languageEnglish (US)
Title of host publicationWavelets and Sparsity XV
StatePublished - 2013
EventWavelets and Sparsity XV - San Diego, CA, United States
Duration: Aug 26 2013Aug 29 2013

Publication series

NameProceedings of SPIE - The International Society for Optical Engineering
ISSN (Print)0277-786X
ISSN (Electronic)1996-756X


OtherWavelets and Sparsity XV
Country/TerritoryUnited States
CitySan Diego, CA


  • Approximate message passing
  • Compressed sensing
  • Graphical models
  • Group sparsity
  • Message passing

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering


Dive into the research topics of 'Hybrid approximate message passing for generalized group sparsity'. Together they form a unique fingerprint.

Cite this