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

  • now accepting submissions for special sessions, tutorials, and papers! The conference is set for June 2… https://t.co/sB3o5ItL0j
  • DEADLINE EXTENDED: The IEEE Journal of Selected Topics in Signal Processing is now accepting papers for a Special I… https://t.co/2SJwqj7aDB
  • NEW WEBINAR: Join us on Friday, 14 August at 11:00 AM ET for the 2021 SPS Membership Preview! Society leadership wi… https://t.co/1PLaZIt2VQ
  • CALL FOR PAPERS: The 2020 IEEE Workshop on Spoken Language Technology is now accepting papers for its January 2021… https://t.co/48604jm3zc
  • CALL FOR PAPERS: The 2020 IEEE International Workshop on Information Forensics and Security is now accepting submis… https://t.co/p9q7UvKgmT

SPS Videos


Signal Processing in Home Assistants

 


Multimedia Forensics


Careers in Signal Processing             

 


Under the Radar