A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 7 Issue 3
Apr.  2020

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2020  >  7(3): 668-673
Zhaorong Zhang and Minyue Fu, "Convergence Rate Analysis of Gaussian Belief Propagation for Markov Networks," IEEE/CAA J. Autom. Sinica, vol. 7, no. 3, pp. 668-673, May 2020. doi: 10.1109/JAS.2020.1003105
Citation: Zhaorong Zhang and Minyue Fu, "Convergence Rate Analysis of Gaussian Belief Propagation for Markov Networks," IEEE/CAA J. Autom. Sinica, vol. 7, no. 3, pp. 668-673, May 2020. doi: 10.1109/JAS.2020.1003105
shu

Convergence Rate Analysis of Gaussian Belief Propagation for Markov Networks

doi: 10.1109/JAS.2020.1003105
  • 1.

    School of Electrical Engineering and Computer Science, The University of Newcastle. University Drive, NSW 2308, Australia

  • 2.

    School of Automation, Guangdong University of Technology, and Guangdong Key Laboratory of Intelligent Decision and Cooperative Control, Guangzhou 510006, China

Funds:  This work was supported by the National Natural Science Foundation of China (61633014, 61803101, U1701264)
More Information
    Abstract
  • Gaussian belief propagation algorithm (GaBP) is one of the most important distributed algorithms in signal processing and statistical learning involving Markov networks. It is well known that the algorithm correctly computes marginal density functions from a high dimensional joint density function over a Markov network in a finite number of iterations when the underlying Gaussian graph is acyclic. It is also known more recently that the algorithm produces correct marginal means asymptotically for cyclic Gaussian graphs under the condition of walk summability (or generalised diagonal dominance). This paper extends this convergence result further by showing that the convergence is exponential under the generalised diagonal dominance condition, and provides a simple bound for the convergence rate. Our results are derived by combining the known walk summability approach for asymptotic convergence analysis with the control systems approach for stability analysis.

     

    • FullText(HTML)
  • loading
    • References(18)
  • [1]
    J. Pearl, Probabilistic Reasoning in Intelligent Systems. Morgan Kaufman, 1988.
    [2]
    Y. Weiss and W. T. Freeman, “Correctness of belief propagation in Gaussian graphical models of arbitrary topology,” Neural Computation, vol. 13, no. 10, pp. 2173–2200, 2001. doi: 10.1162/089976601750541769
    [3]
    D. M. Malioutov, J. K. Johnson, and A. S. Willsky, “Walk-sums and belief propagation in Gaussian graphical models,” J. Machine Learning Research, vol. 7, pp. 2031–2064, 2006.
    [4]
    D. Marelli and M. Fu, “Distributed weighted least-squares estimation with fast convergence for large-scale systems,” Automatica, vol. 51, pp. 27–39, 2015. doi: 10.1016/j.automatica.2014.10.077
    [5]
    C. C. Moallemi and B. Van Roy, “Convergence of min-sum message-passing for quadratic optimization,” IEEE Trans. Inf. Theory, vol. 55, no. 5, pp. 2413–2423, 2009. doi: 10.1109/TIT.2009.2016055
    [6]
    C. C. Moallemi and B. Van Roy, “Convergence of min-sum message-passing for convex optimization,” IEEE Trans. Inf. Theory, vol. 56, no. 4, pp. 2041–2050, 2010. doi: 10.1109/TIT.2010.2040863
    [7]
    Q. Su and Y-C. Wu, “Convergence analysis of the variance in Gaussian belief propagation,” IEEE Trans. Signal Processing, vol. 62, no. 19, pp. 5119–5131, 2014. doi: 10.1109/TSP.2014.2345635
    [8]
    Q. Su and Y-C. Wu, “On convergence conditions of Gaussian belief propagation,” IEEE Trans. Signal Processing, vol. 63, no. 5, pp. 1144–1155, 2015. doi: 10.1109/TSP.2015.2389755
    [9]
    O. Shental, P. H. Siegel, J. K. Wolf, D. Bickson, and D. Dolev, “Gaussian belief propagation solver for systems of linear equations,” in Proc. IEEE Int. Symp. Information Theory, vol. 4, pp. 1863–1867, 2008, Toronto, Canada.
    [10]
    X.-M. Zhang, Q.-L. Han, X. H. Ge, D. R. Ding, L. Ding, D. Yue, and C. Peng, “Networked control systems: a survey of trends and techniques,” IEEE/CAA J. Autom. Sinica, vol. 7, no. 1, pp. 1–17, Jan. 2020. doi: 10.1109/JAS.2019.1911861
    [11]
    H. F. Niu, A. Sahoo, C. Bhowmick, and S. Jagannathan, “An optimal hybrid learning approach for attack detection in linear networked control systems,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 6, pp. 1404–1416, Nov. 2019.
    [12]
    B. Xia, W. H. Yuan, N. Xie, and C. H. Li, “A novel statistical manifold algorithm for position estimation,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 6, pp. 1513–1518, Nov. 2019.
    [13]
    X. Tan and J. Li, “Computationally efficient sparse Bayesian learning via belief propagation,” IEEE Trans. Signal Process., vol. 58, no. 4, pp. 2010–2021, Apr. 2010. doi: 10.1109/TSP.2010.2040683
    [14]
    N. Ruozzi and S. Tatikonda, “Message-passing algorithms for quadratic minimization,” J. Machine Learning Research, vol. 14, pp. 2287–2314, Aug. 2013.
    [15]
    N. Ruozzi and S. Tatikonda, “A new approach to Laplacian solvers and flow problems,” J. Machine Learning Research, vol. 20, pp. 1–37, Feb. 2019.
    [16]
    B. Cseke and T. M. Heskes, “Bounds on the Bethe free energy for Gaussian networks.” in Proc. 24th Conf. Uncertainty in Artificial Intelligence, 2008, pp. 97–104.
    [17]
    E. G. Boman, D. Chen, O. Parekh, and S. Toledo, “On factor width and symmetric H-matrices,” Linear Algebra and its Applications, vol. 405, pp. 239–248, 2005. doi: 10.1016/j.laa.2005.03.029
    [18]
    Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003.
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(6)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1289) PDF downloads(75) Cited by()

    Highlights

    • A new bound on the convergence rate of the algorithm under the generalised diagonal dominance condition.
    • Theoretical development is done by combining the known walk summability approach for asymptotic convergence analysis with the control systems approach for stability analysis.
    • The work allows more application of the Gaussian Belief Propagation algorithm in distributed estimation and distributed optimisation.

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return