Research problem:

    Gaussian Belief Propagation: convergence analysis and applications


Brief Description:

Gaussian Belief Propagation (BP) is a message-passing method for computing the marginal density function from a high dimensional joint Gaussian distribution.  It finds many applications ranging from distributed downlink beamforming design, distributed power state estimation in smart grid, low-complexity matrix inverse, to peer-to-peer rating in social networks.  While Gaussian BP suits very well in distributed settings, one of the main challenges it faces is the convergence issue.  Previously, there are several well-known sufficient convergence conditions for scalar Gaussian BP, such as diagonal dominance, walk-summability, and convex decomposition.  While these conditions provide pioneering guidelines for determining the convergence, there is still a research gap on finding the necessary convergence condition for Gaussian BP.  In this regard, we provide the necessary and sufficient condition for scalar Gaussian BP, and connects various existing convergence conditions in a unified framework.

After guaranteeing convergence, then it comes to the question of accuracy of Gaussian BP.  It is known that when Gaussian BP converges, the mean calculated by Gaussian BP is the exact mean of the marginal probability density function, while the accuracy of the variance is in general poor and unpredictable.  Inspired by the Feedback Message Passing algorithm, and making use of the analysis from computation tree, we propose a distributed way of improving the accuracy of variance estimated by Gaussian BP.

Apart from theoretical analysis, we also applied Gaussian BP to network synchronization.  In particular, since the parameters involved are vectors rather than scalars, we employed the vector-form Gaussian BP, and the convergence of the algorithm has to be re-established.  Currently, for vector-form Gaussian BP, we have the result that convergence is guaranteed for synchronization application. Generalization of this result to other applications, which may have different graph structures from synchronization, would be interesting but challenging. Another extension is on high-order connected graphs, which finds applications in joint signal detection and distributed beamforming. In general, the analysis on high-order Gaussian BP is more difficult than that in pairwise graphs, and we found that the convergence behaviour of high-order Gaussian BP is also quite different from that of pairwise graphs.  

Related Publications:

Necessary and sufficient convergence condition, connections among existing results:

1. Bin Li, Qinliang Su and Yik-Chung Wu, ``Fixed Points of Gaussian Belief Propagation and Relation to Convergence," IEEE Trans. on Signal Processing, Vol. 67, no. 23, pp. 6025-6038, Dec 2019.

2. Bin Li, and Yik-Chung Wu, "Convergence of Gaussian Belief Propagation Under General Pairwise Factorization: Connecting Gaussian MRF with Pairwise Linear Gaussian Model," Journal of Machine Learning Research, 20(144):1−30, 2019.

3. Qinliang Su and Yik-Chung Wu, ``On Convergence Conditions of Gaussian Belief Propagation,'' IEEE Trans. on Signal Processing, Vol. 63, no. 5, pp. 1144-1155, Mar. 2015.

4. Qinliang Su and Yik-Chung Wu, ``Convergence Analysis of the Variance in Gaussian Belief Propagation,'' IEEE Trans. on Signal Processing, Vol. 62, no. 19, pp. 5119-5131, Oct. 2014.

Variance accuracy improvement:

5. Qinliang Su and Yik-Chung Wu, ``Distributed Estimation of Variance in Gaussian Graphical Model via Belief Propagation: Accuracy Analysis and Improvement,'' IEEE Trans. on Signal Processing, Vol. 63, no. 23, pp. 6258-6271, Dec 2015.

Network synchronization using Gaussian BP:

6. Jian Du and Yik-Chung Wu, ``Network-Wide Distributed Carrier Frequency Offsets Estimation and Compensation via Belief Propagation," IEEE Trans. on Signal Processing, Vol. 68, no. 23, pp. 5868-5877, Dec. 2013.

7. Jian Du, and Yik-Chung Wu, ``Distributed Clock Skew and Offset Estimation in Wireless Sensor Networks: Asynchronous Algorithm and Convergence Analysis," IEEE Trans. on Wireless Communications, Vol. 12, no. 11, pp. 5908-5917, Nov. 2013.

8. Mei Leng and Yik-Chung Wu, ``Distributed Clock Synchronization for Wireless Sensor Networks using Belief Propagation," IEEE Trans. on Signal Processing, Vol. 59, no. 11, pp. 5404-5414, Nov 2011.

High-order Gaussian BP:

9. Bin Li, and Yik-Chung Wu, ``Convergence Analysis of Gaussian Belief Propagation Under High-Order Factorization and Asynchronous Scheduling," IEEE Trans. on Signal Processing, Vol. 67, no. 11, pp. 2884-2897, Jun 2019.

10. Jian Du, Shaodan Ma, Yik-Chung Wu, Soummya Kar, Jose M. F. Moura, ``Convergence Analysis of Distributed Inference with Vector-Valued Gaussian Belief Propagation," Journal of Machine Learning Research, 18(172):1−38, 2018.

Gaussian BP applied to cooperative localization:

11. Bin Li, Nan Wu, Yik-Chung Wu, and Yonghui Li, ``Convergence-Guaranteed Parametric Bayesian Distributed Cooperative Localization," IEEE Trans. on Wireless Communications, vol. 21, no. 10, pp. 8179-8192, Oct 2022.