File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/TSP.2019.2908943
- Scopus: eid_2-s2.0-85065046692
- WOS: WOS:000466554400007
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Convergence Analysis of Gaussian Belief Propagation Under High-Order Factorization and Asynchronous Scheduling
Title | Convergence Analysis of Gaussian Belief Propagation Under High-Order Factorization and Asynchronous Scheduling |
---|---|
Authors | |
Keywords | Gaussian belief propagation convergence analysis high-order factorization asynchronous scheduling loopy graph |
Issue Date | 2019 |
Publisher | IEEE. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=78 |
Citation | IEEE Transactions on Signal Processing, 2019, v. 67 n. 11, p. 2884-2897 How to Cite? |
Abstract | 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. |
Persistent Identifier | http://hdl.handle.net/10722/273879 |
ISSN | 2023 Impact Factor: 4.6 2023 SCImago Journal Rankings: 2.520 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Li, B | - |
dc.contributor.author | Wu, YC | - |
dc.date.accessioned | 2019-08-18T14:50:29Z | - |
dc.date.available | 2019-08-18T14:50:29Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | IEEE Transactions on Signal Processing, 2019, v. 67 n. 11, p. 2884-2897 | - |
dc.identifier.issn | 1053-587X | - |
dc.identifier.uri | http://hdl.handle.net/10722/273879 | - |
dc.description.abstract | 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. | - |
dc.language | eng | - |
dc.publisher | IEEE. The Journal's web site is located at http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=78 | - |
dc.relation.ispartof | IEEE Transactions on Signal Processing | - |
dc.rights | IEEE Transactions on Signal Processing. Copyright © IEEE. | - |
dc.rights | ©20xx IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | - |
dc.subject | Gaussian belief propagation | - |
dc.subject | convergence analysis | - |
dc.subject | high-order factorization | - |
dc.subject | asynchronous scheduling | - |
dc.subject | loopy graph | - |
dc.title | Convergence Analysis of Gaussian Belief Propagation Under High-Order Factorization and Asynchronous Scheduling | - |
dc.type | Article | - |
dc.identifier.email | Wu, YC: ycwu@eee.hku.hk | - |
dc.identifier.authority | Wu, YC=rp00195 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1109/TSP.2019.2908943 | - |
dc.identifier.scopus | eid_2-s2.0-85065046692 | - |
dc.identifier.hkuros | 302293 | - |
dc.identifier.volume | 67 | - |
dc.identifier.issue | 11 | - |
dc.identifier.spage | 2884 | - |
dc.identifier.epage | 2897 | - |
dc.identifier.isi | WOS:000466554400007 | - |
dc.publisher.place | United States | - |
dc.identifier.issnl | 1053-587X | - |