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

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

  • On 15 September 2022, we are excited to partner with and to bring you a webinar and roundtable,…
  • The SPS Webinar Series continues on Monday, 22 August when Dr. Yu-Huan Wu and Dr. Shanghua Gao present “Towards Des…
  • CALL FOR PAPERS: The IEEE/ACM Transactions on Audio, Speech, and Language Processing is now accepting submissions f…
  • DEADLINE EXTENDED: The IEEE Journal of Selected Topics in Signal Processing is now accepting submissions for a Spec…
  • Our Information Forensics and Security Webinar Series continues on Tuesday, 23 August when Dr. Anderson Rocha prese…

SPS Videos

Signal Processing in Home Assistants


Multimedia Forensics

Careers in Signal Processing             


Under the Radar