File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Convergence Analysis of the Variance in Gaussian Belief Propagation

TitleConvergence Analysis of the Variance in Gaussian Belief Propagation
Authors
Issue Date2014
Citation
IEEE Transactions on Signal Processing, 2014, v. 62, p. 5119-5131 How to Cite?
AbstractIt is known that Gaussian belief propagation (BP) is a low-complexity algorithm for (approximately) computing the marginal distribution of a high dimensional Gaussian distribu- tion. However, in loopy factor graph, it is important to determine whether Gaussian BP converges. In general, the convergence conditions for Gaussian BP variances and means are not nec- essarily the same, and this paper focuses on the convergence condition of Gaussian BP variances. In particular, by describing the message-passing process of Gaussian BP as a set of updating functions, the necessary and sufficient convergence conditions of Gaussian BP variances are derived under both synchronous and asynchronous schedulings, with the converged variances proved to be independent of the initialization as long as it is chosen from the proposed set. The necessary and sufficient convergence condition is further expressed in the form of a semi-definite programming (SDP) optimization problem, thus can be verified more efficiently compared to the existing convergence condition based on compu- tation tree. The relationship between the proposed convergence condition and the existing one based on computation tree is also established analytically. Numerical examples are presented to corroborate the established theories.
Persistent Identifierhttp://hdl.handle.net/10722/214162

 

DC FieldValueLanguage
dc.contributor.authorSU, Q-
dc.contributor.authorWu, YC-
dc.date.accessioned2015-08-21T10:51:05Z-
dc.date.available2015-08-21T10:51:05Z-
dc.date.issued2014-
dc.identifier.citationIEEE Transactions on Signal Processing, 2014, v. 62, p. 5119-5131-
dc.identifier.urihttp://hdl.handle.net/10722/214162-
dc.description.abstractIt is known that Gaussian belief propagation (BP) is a low-complexity algorithm for (approximately) computing the marginal distribution of a high dimensional Gaussian distribu- tion. However, in loopy factor graph, it is important to determine whether Gaussian BP converges. In general, the convergence conditions for Gaussian BP variances and means are not nec- essarily the same, and this paper focuses on the convergence condition of Gaussian BP variances. In particular, by describing the message-passing process of Gaussian BP as a set of updating functions, the necessary and sufficient convergence conditions of Gaussian BP variances are derived under both synchronous and asynchronous schedulings, with the converged variances proved to be independent of the initialization as long as it is chosen from the proposed set. The necessary and sufficient convergence condition is further expressed in the form of a semi-definite programming (SDP) optimization problem, thus can be verified more efficiently compared to the existing convergence condition based on compu- tation tree. The relationship between the proposed convergence condition and the existing one based on computation tree is also established analytically. Numerical examples are presented to corroborate the established theories.-
dc.languageeng-
dc.relation.ispartofIEEE Transactions on Signal Processing-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rights©2014 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.titleConvergence Analysis of the Variance in Gaussian Belief Propagation-
dc.typeArticle-
dc.identifier.emailWu, YC: ycwu@eee.hku.hk-
dc.identifier.authorityWu, YC=rp00195-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1109/TSP.2014.2345635-
dc.identifier.hkuros248923-
dc.identifier.volume62-
dc.identifier.spage5119-
dc.identifier.epage5131-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats