Estimation with Random Linear Mixing, Belief Propagation and Compressed Sensing

Abstract

We apply Guo and Wang's relaxed belief propagation (BP) method to the estimation of a random vector from linear measurements followed by a componentwise probabilistic measurement channel. Relaxed BP uses a Gaussian approximation in standard BP to obtain significant computational savings for dense measurement matrices. The main contribution of this paper is to extend the relaxed BP method and analysis to general (non-AWGN) output channels. Specifically, we present detailed equations for implementing relaxed BP for general channels and show that relaxed BP has an identical asymptotic large sparse limit behavior as standard BP, as predicted by the Guo and Wang's state evolution (SE) equations. Applications are presented to compressed sensing and estimation with bounded noise.

24 pages, 7 figures

References in corpus (1)

• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing

Cited by in corpus (16)

• Statistical physics of inference: Thresholds and algorithms
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Generalized Approximate Message Passing for Estimation with Random Linear Mixing
• Approximate Message Passing with Consistent Parameter Estimation and Applications to Sparse Learning
• Performance Regions in Compressed Sensing from Noisy Measurements
• An equivalence between high dimensional Bayes optimal inference and M-estimation
• Recovery from Linear Measurements with Complexity-Matching Universal Signal Estimation
• Bayesian Quantized Network Coding via Belief Propagation
• Detection-Directed Sparse Estimation using Bayesian Hypothesis Test and Belief Propagation
• Wiener Filters in Gaussian Mixture Signal Estimation with Infinity-Norm Error
• Belief Propagation Methods for Intercell Interference Coordination
• Belief-propagation-based joint channel estimation and decoding for spectrally efficient communication over unknown sparse channels
• Signal reconstruction in linear mixing systems with different error metrics
• The Sampling Rate-Distortion Tradeoff for Sparsity Pattern Recovery in Compressed Sensing
• Mixture Gaussian Signal Estimation with L_infty Error Metric