Quantized stochastic belief propagation: Efficient message-passing for continuous state spaces

Belief propagation (BP) is a widely used algorithm for computing the marginal distributions in graphical models. However, in applications involving continuous random variables, the messages themselves are real-valued functions, which leads to significant computational bottlenecks. In this paper, we propose a low complexity method for performing belief propagation for continuous state space problems. Our algorithm, which we refer to as quantized stochastic belief propagation (QSBP), is a randomized variant of BP in which each node only passes stochastically chosen information at each round. The most attractive feature of QSBP is its significant gain in computational and communication efficiencies. In addition, we provide some theoretical guarantees including almost sure convergence and the rate of convergence for the case of tree-structured graphical models.