IC Monday Seminar : Stochastic belief propagation: Low-complexity message-passing with rigorous guarantees
Event details
| Date | 13.12.2011 |
| Hour | 16:15 |
| Speaker | Prof. Martin Wainwright, UC Berkeley, USA - Invited by Prof. Rüdiger Urbanke |
| Location |
INR 219
|
| Category | Conferences - Seminars |
Abstract Graphical models play an important role in many areas, including statistical signal processing, coding and communication theory, computer vision, and sensor networks. The sum-product or belief propagation (BP) algorithm is a widely-used message-passing technique for computing marginal distributions in such models. When applied to a graphical model with pairwise interactions, the complexity of the BP update scales quadratically 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. We propose a low-complexity variant of belief propagation, referred to as stochastic belief propagation (SBP), based on adaptive randomization. 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 per edge. We establish a number of theoretical guarantees for the performance of SBP, showing almost sure convergence to the exact BP fixed point for any tree-structured graph, and for any graphical model with cycles satisfying a contractivity condition, as well as non-asymptotic guarantees on the convergence rate that are inverse-polynomial in iteration number. Based on joint work with Nima Noorshams. Arxiv preprint: http://arxiv.org/abs/1111.1020 Biography
Practical information
- General public
- Free
Contact
- Simone Muller