Stochastic Belief Propagation: Low-Complexity Message-Passing with Guarantees

Details Stochastic Belief Propagation: Low-Complexity Message-Passing with Guarantees Stochastic Belief Propagation: Low-Complexity Message-Passing with Guarantees

2011-11-04

arxiv.org/abs/1111.1020v1

Computer Science

Information Theory

Portions of the results were initially reported at the Allerton Conference on Communications, Control, and Computing (Septembe

Scientific paper

The sum-product or belief propagation (BP) algorithm is a widely-used message-passing algorithm for computing marginal distributions in graphical models with discrete variables. At the core of the BP updates, when applied to a graphical model with pairwise interactions, lies a matrix-vector product with complexity that is quadratic in the state dimension $d$, and requires transmission of a $(d-1)$-dimensional vector of real numbers (messages) to its neighbors. Since various applications involve very large state dimensions, such computation and communication complexities can be prohibitively complex. In this paper, we propose a low-complexity variant of belief propagation, referred to as stochastic belief propagation (SBP). As suggested by the name, it is an adaptively randomized version of the BP updates in which each node passes randomly chosen information to each of its neighbors. The SBP updates reduce the computational complexity (per iteration) from quadratic to linear in $d$, without assuming any particular structure of the potentials, and also reduce the communication complexity significantly, requiring only $\log d$ bits transmission per edge. Moreover, we establish a number of theoretical guarantees for the performance of SBP, showing that it converges almost surely to the BP fixed point for any tree-structured graph, and for graphical models with cycles satisfying a contractivity condition. In addition, we provide non-asymptotic upper bounds on the convergence rate, showing that it decays no slower than $O(1/\sqrt{t})$ with the number of iterations $t$ on trees and as $O(1/t)$ for general graphs.

Affiliated with

Also associated with

No associations

Rating

Stochastic Belief Propagation: Low-Complexity Message-Passing with Guarantees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Stochastic Belief Propagation: Low-Complexity Message-Passing with Guarantees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stochastic Belief Propagation: Low-Complexity Message-Passing with Guarantees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-100370