Hybrid Approximate Message Passing

Abstract

Gaussian and quadratic approximations of message passing algorithms on graphs have attracted considerable recent attention due to their computational simplicity, analytic tractability, and wide applicability in optimization and statistical inference problems. This paper presents a systematic framework for incorporating such approximate message passing (AMP) methods in general graphical models. The key concept is a partition of dependencies of a general graphical model into strong and weak edges, with the weak edges representing interactions through aggregates of small, linearizable couplings of variables. AMP approximations based on the Central Limit Theorem can be readily applied to aggregates of many weak edges and integrated with standard message passing updates on the strong edges. The resulting algorithm, which we call hybrid generalized approximate message passing (HyGAMP), can yield significantly simpler implementations of sum-product and max-sum loopy belief propagation. By varying the partition of strong and weak edges, a performance--complexity trade-off can be achieved. Group sparsity and multinomial logistic regression problems are studied as examples of the proposed methodology.

References in corpus (23)

• The composite absolute penalties family for grouped and hierarchical variable selection
• Expectation-Maximization Gaussian-Mixture Approximate Message Passing
• Bilinear Generalized Approximate Message Passing
• Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing
• Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior
• Universality in polytope phase transitions and message passing algorithms
• Dynamic Compressive Sensing of Time-Varying Signals via Approximate Message Passing
• Efficient High-Dimensional Inference in the Multiple Measurement Vector Problem
• Adaptive Damping and Mean Removal for the Generalized Approximate Message Passing Algorithm
• A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
• A Message-Passing Receiver for BICM-OFDM over Unknown Clustered-Sparse Channels
• A Factor Graph Approach to Joint OFDM Channel Estimation and Decoding in Impulsive Noise Environments
• Belief propagation for joint sparse recovery
• Hybrid Approximate Message Passing
• Parametric Bilinear Generalized Approximate Message Passing
• Random Access in C-RAN for User Activity Detection with Limited-Capacity Fronthaul
• Parameterless Optimal Approximate Message Passing
• Approximate Message Passing with Restricted Boltzmann Machine Priors
• Binary Linear Classification and Feature Selection via Generalized Approximate Message Passing
• Scalable Inference for Neuronal Connectivity from Calcium Imaging
• Sparse Multinomial Logistic Regression via Approximate Message Passing
• Rigorous Dynamics of Expectation-Propagation-Based Signal Recovery from Unitarily Invariant Measurements
• Fixed Points of Generalized Approximate Message Passing with Arbitrary Matrices

Cited by in corpus (22)

• AMP-Inspired Deep Networks for Sparse Linear Inverse Problems
• Capacity-Achieving MIMO-NOMA: Iterative LMMSE Detection
• A Unified Bayesian Inference Framework for Generalized Linear Models
• Hybrid Approximate Message Passing
• Plug-in Estimation in High-Dimensional Linear Inverse Problems: A Rigorous Analysis
• Bilinear Recovery using Adaptive Vector-AMP
• A New Insight into GAMP and AMP
• Performance Analysis of Approximate Message Passing for Distributed Compressed Sensing
• Joint Source-Channel Coding for Semantics-Aware Grant-Free Radio Access in IoT Fog Networks
• Denoising based Vector Approximate Message Passing
• Temporal Parallelization of Inference in Hidden Markov Models
• Inference in Deep Networks in High Dimensions
• Stochastic gradient descent methods for estimation with large data sets
• Expectation-Maximization-Aided Hybrid Generalized Expectation Consistent for Sparse Signal Reconstruction
• Vector Approximate Message Passing Algorithm for Structured Perturbed Sensing Matrix
• Regularization by Denoising: Clarifications and New Interpretations
• An Overview of Multi-Processor Approximate Message Passing
• Bayes-Optimal Convolutional AMP
• Dynamic Message Scheduling With Activity-Aware Residual Belief Propagation for Asynchronous mMTC Systems
• Gridless Variational Bayesian Channel Estimation for Antenna Array Systems with Low Resolution ADCs
• Study of Joint Activity Detection and Channel Estimation Based on Message Passing with RBP Scheduling for MTC
• Replica Analysis for Generalized Linear Regression with IID Row Prior