Generalized Approximate Message Passing for Estimation with Random Linear Mixing

Abstract

We consider the estimation of an i.i.d.\ random vector observed through a linear transform followed by a componentwise, probabilistic (possibly nonlinear) measurement channel. A novel algorithm, called generalized approximate message passing (GAMP), is presented that provides computationally efficient approximate implementations of max-sum and sum-problem loopy belief propagation for such problems. The algorithm extends earlier approximate message passing methods to incorporate arbitrary distributions on both the input and output of the transform and can be applied to a wide range of problems in nonlinear compressed sensing and learning. Extending an analysis by Bayati and Montanari, we argue that the asymptotic componentwise behavior of the GAMP method under large, i.i.d. Gaussian transforms is described by a simple set of state evolution (SE) equations. From the SE equations, one can \emph{exactly} predict the asymptotic value of virtually any componentwise performance metric including mean-squared error or detection accuracy. Moreover, the analysis is valid for arbitrary input and output distributions, even when the corresponding optimization problems are non-convex. The results match predictions by Guo and Wang for relaxed belief propagation on large sparse matrices and, in certain instances, also agree with the optimal performance predicted by the replica method. The GAMP methodology thus provides a computationally efficient methodology, applicable to a large class of non-Gaussian estimation problems with precise asymptotic performance guarantees.

22 pages, 5 figures

References in corpus (5)

• Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior
• Message-Passing Estimation from Quantized Samples
• A Message-Passing Receiver for BICM-OFDM over Unknown Clustered-Sparse Channels
• On-Off Random Access Channels: A Compressed Sensing Framework
• Belief Propagation Methods for Intercell Interference Coordination

Cited by in corpus (25)

• Turbo Compressed Sensing with Partial DFT Sensing Matrix
• Blind Estimation of Sparse Broadband Massive MIMO Channels with Ideal and One-bit ADCs
• On the Performance of Turbo Signal Recovery with Partial DFT Sensing Matrices
• Multi-Layer Bilinear Generalized Approximate Message Passing
• Optimal Data Detection in Large MIMO
• Approximate Message Passing with Consistent Parameter Estimation and Applications to Sparse Learning
• Statistical mechanical analysis of sparse linear regression as a variable selection problem
• A comment on the "A unified Bayesian inference framework for generalized linear models"
• Two-Part Reconstruction with Noisy-Sudocodes
• Performance Regions in Compressed Sensing from Noisy Measurements
• Inference for Generalized Linear Models via Alternating Directions and Bethe Free Energy Minimization
• Optimal Data Detection and Signal Estimation in Systems with Input Noise
• Joint User Identification, Channel Estimation, and Signal Detection for Grant-Free NOMA
• Vector Approximate Message Passing Algorithm for Structured Perturbed Sensing Matrix
• Estimation for High-Dimensional Multi-Layer Generalized Linear Model -- Part I: The Exact MMSE Estimator
• Optimization of the Belief-Propagation Algorithm for Distributed Detection by Linear Data-Fusion Techniques
• The Sampling Rate-Distortion Tradeoff for Sparsity Pattern Recovery in Compressed Sensing
• Mixture Gaussian Signal Estimation with L_infty Error Metric
• Signal reconstruction in linear mixing systems with different error metrics
• An Analysis of State Evolution for Approximate Message Passing with Side Information
• Symbol Detection for Massive MIMO AF Relays Using Approximate Bayesian Inference
• Rigorous State Evolution Analysis for Approximate Message Passing with Side Information
• A Two-stage Approach to Estimate CFO and Channel with One-bit ADCs
• A Bayesian approach to sparse channel estimation in OFDM systems
• Belief-propagation-based joint channel estimation and decoding for spectrally efficient communication over unknown sparse channels