Bayesian inference in densely connected networks applied to CDMA
Juan Pablo Neirotti, David Saad · Aston Publications Explorer (Aston University) · 2005
Graphical models provide a powerful framework for modelling statistical dependencies between variables [1]. Message passing techniques are typically used for inference in graphical models that can be represented by a sparse graph. Iterative message passing is guaranteed to converge to the globally correct estimate when the system is tree-like; there are no such guarantees for systems with loops. Two inherent limitations seem to prevent the use of message passing techniques in densely connected systems: 1) Their high connectivity implies an exponentially growing computational cost. 2) The existence of an exponential number of loops that render the method inconsistent. However, a new approach was suggested [2] for extending Belief Propagation (BP) techniques to densely connected systems. In this approach, messages are grouped together, giving rise to macroscopic random variables drawn from a different Gaussian distribution of varying mean and variance for each of the nodes. In a separate development [3], BP was extended to Survey Propagation (SP). This new algorithm has succeeded in solving hard computational problems [3], far beyond other existing approaches. Inspired by the extension of BP to SP we have extended the approach of [2], designed for inference in densely connected systems, in a similar manner by including an average over multiple pure states. However, for highlighting the advantages with respect to the original method [2], we apply it to the problem of signal detection in CDMA. Code Division Multiple Access [4] is based on spreading the signal by using K individual random binary spreading codes of spreading factor N. We consider the large-system limit N → ∞, K → ∞ with β = K/N ∼ O(1). The received aggregated, modulated and corrupted signal is of the form: yµ = 1