Convergence Analysis of Gaussian Belief Propagation Under High-Order Factorization and Asynchronous Scheduling

You are here

Top Reasons to Join SPS Today!

1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.

Convergence Analysis of Gaussian Belief Propagation Under High-Order Factorization and Asynchronous Scheduling

By: 
Bin Li; Yik-Chung Wu

It is well known that the convergence of Gaussian belief propagation (BP) is not guaranteed in loopy graphs. The classical convergence conditions, including diagonal dominance, walk-summability, and convex decomposition, are derived under pairwise factorizations of the joint Gaussian distribution. However, many applications run Gaussian BP under high-order factorizations, making the classical results not applicable. In this paper, the convergence of Gaussian BP under high-order factorization and asynchronous scheduling is investigated. In particular, three classes of asynchronous scheduling are considered. The first one is the totally asynchronous scheduling, and a sufficient convergence condition is derived. Since the totally asynchronous scheduling represents a broad class of asynchronous scheduling, the derived convergence condition might not be tight for a particular asynchronous schedule. Consequently, the second class of asynchronous scheduling, called quasi-asynchronous scheduling, is considered. Being a subclass of the totally asynchronous scheduling, quasi-asynchronous scheduling possesses a simpler structure, which facilitates the derivation of the necessary and sufficient convergence condition. To get a deeper insight into the quasi-asynchronous scheduling, a third class of asynchronous scheduling, named independent and identically distributed (i.i.d.) quasi-asynchronous scheduling, is further proposed, and the convergence is analyzed in the probabilistic sense. Compared to the synchronous scheduling, it is found that Gaussian BP under the i.i.d. quasi-asynchronous scheduling demonstrates better convergence. Numerical examples and applications are presented to corroborate the newly established theoretical results.

SPS on Twitter

SPS Videos


Signal Processing in Home Assistants

 


Multimedia Forensics


Careers in Signal Processing             

 


Under the Radar