Stochastic Belief Propagation-SBP

University of California System: University of California, Berkeley
posted on 12/05/2011

• request more info 
•   
•  LICENSE ONLINE

The sum-product or belief propagation (BP) algorithm is a widely-used iterative method for performing data inference in a broad range of fields—among them computer vision, signal and image processing, bioinformatics, coding and communication theory.  However, the high complexity of the current BP algorithm limits its applications due to low efficiency, high running-time and makes for a system of limited robustness. To address this challenge, investigators at University of California at Berkeley have developed stochastic belief propagation, SBP, a low-complexity alternative to BP. The SBP innovation is an adaptively randomized version of the usual BP updates. The most important feature of the SBP algorithm is its significant reduction in computational and communication complexities. This provides improved efficiency and reduced running-time.  As a result, SBP delivers substantial power savings. Stochastic belief propagation is simple to implement, requiring only random number generation and the usual distributed updates of a message-passing algorithm. SBP provides a number of theoretical guarantees, including convergence for any tree-structured problem, as well as for general graphs for which the ordinary BP update satisfies a suitable contraction condition. In addition, SBP provides non-asymptotic upper bounds on the SBP error, both in expectation and in high probability.

• energy monitoring
• computer vision disparity estimation
• corrupted image restoration
• tracking problems in sensor networks
• vehicle localization and also geotagging images

• saves power
• improves efficiency
• reduces running-time
• simple to implement