Improved message passing for inference in densely connected systems

Abstract

An improved inference method for densely connected systems is presented. The approach is based on passing condensed messages between variables, representing macroscopic averages of microscopic messages. We extend previous work that showed promising results in cases where the solution space is contiguous to cases where fragmentation occurs. We apply the method to the signal detection problem of Code Division Multiple Access (CDMA) for demonstrating its potential. A highly efficient practical algorithm is also derived on the basis of insight gained from the analysis.

References in corpus (1)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm

Cited by in corpus (22)

• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Learning by message-passing in networks of discrete synapses
• Low-Complexity Detection/Equalization in Large-Dimension MIMO-ISI Channels Using Graphical Models
• Generalized Approximate Message Passing for Estimation with Random Linear Mixing
• Gaussian Belief Propagation Based Multiuser Detection
• Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels
• Sparsely-spread CDMA - a statistical mechanics based analysis
• Entropy landscape of solutions in the binary perceptron problem
• Perceptron capacity revisited: classification ability for correlated patterns
• Message Passing Algorithms for Compressed Sensing: I. Motivation and Construction
• Estimation with Random Linear Mixing, Belief Propagation and Compressed Sensing
• Stochastic optimization by message passing
• Statistical mechanical analysis of the Kronecker channel model for MIMO wireless communication
• The Noise-Sensitivity Phase Transition in Compressed Sensing
• Survey propagation at finite temperature: application to a Sourlas code as a toy model
• Efficient Bayesian Inference for Learning in the Ising Linear Perceptron and Signal Detection in CDMA
• Capacity Optimality of AMP in Coded Systems
• Inference by replication in densely connected systems
• Replication-based Inference Algorithms for Hard Computational Problems
• Typical case behaviour of spin systems in random graph and composite ensembles
• MIMO Detection for High-Order QAM Based on a Gaussian Tree Approximation
• Dynamical replica theoretic analysis of CDMA detection dynamics