Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation

Abstract

This paper considers inference over distributed linear Gaussian models using factor graphs and Gaussian belief propagation (BP). The distributed inference algorithm involves only local computation of the information matrix and of the mean vector, and message passing between neighbors. Under broad conditions, it is shown that the message information matrix converges to a unique positive definite limit matrix for arbitrary positive semidefinite initialization, and it approaches an arbitrarily small neighborhood of this limit matrix at a doubly exponential rate. A necessary and sufficient convergence condition for the belief mean vector to converge to the optimal centralized estimator is provided under the assumption that the message information matrix is initialized as a positive semidefinite matrix. Further, it is shown that Gaussian BP always converges when the underlying factor graph is given by the union of a forest and a single loop. The proposed convergence condition in the setup of distributed linear Gaussian models is shown to be strictly weaker than other existing convergence conditions and requirements, including the Gaussian Markov random field based walk-summability condition, and applicable to a large class of scenarios.

38 pages

References in corpus (6)

• Loopy Belief Propagation for Approximate Inference: An Empirical Study
• Signal Recovery on Graphs: Variation Minimization
• Loop series for discrete statistical models on graphs
• Sufficient conditions for convergence of Loopy Belief Propagation
• Belief Propagation for Continuous State Spaces: Stochastic Message-Passing with Quantitative Guarantees
• Convergence analysis of belief propagation for pairwise linear Gaussian models

Cited by in corpus (12)

• Fast Resampling of 3D Point Clouds via Graphs
• RF-based Energy Harvesting in Decode-and-Forward Relaying Systems: Ergodic and Outage Capacities
• Distributed Convergence Verification for Gaussian Belief Propagation
• Fast Path Localization on Graphs via Multiscale Viterbi Decoding
• Energy Spatio-Temporal Pattern Prediction for Electric Vehicle Networks
• Proactive Doppler Shift Compensation in Vehicular Cyber-Physical Systems
• An Empirical Evaluation of Rule Extraction from Recurrent Neural Networks
• Convergence Analysis of Belief Propagation on Gaussian Graphical Models
• Distributed Multi-User Wireless Charging Power Allocation
• When Renewable Energy Meets Building Thermal Mass: A Real-time Load Management Scheme
• Distributed Frequency Offsets Estimation
• Greening Geographical Power Allocation for Cellular Networks