Convergence analysis of reweighted sum-product algorithms

被引:20
|
作者
Roosta, Tanya G. [1 ]
Wainwright, Martin J. [1 ,2 ]
Sastry, Shankar S. [1 ]
机构
[1] Univ Calif Berkeley, Dept Elect & Comp Engn, Berkeley, CA 94720 USA
[2] Univ Calif Berkeley, Dept Stat, Berkeley, CA 94720 USA
关键词
approximate marginalization; belief propagation; convergence analysis; graphical models; Markov random fields; sum-product algorithm;
D O I
10.1109/TSP.2008.924136
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
Markov random fields are designed to represent structured dependencies among large collections of random variables, and are well-suited to capture the structure of real-world signals. Many fundamental tasks in signal processing (e.g., smoothing, denoising, segmentation etc.) require efficient methods for computing (approximate) marginal probabilities over subsets of nodes in the graph. The marginalization problem, though solvable in linear time for graphs without cycles, is computationally intractable for general graphs with cycles. This intractability motivates the use of approximate "message-passing" algorithms. This paper studies the convergence and stability properties of the family of reweighted sum-product algorithms, a generalization of the widely used sum-product or belief propagation algorithm, in which messages are adjusted with graph-dependent weights. For pairwise Markov random fields, we derive various conditions that are sufficient to ensure convergence, and also provide bounds on the geometric convergence rates. When specialized to the ordinary sum-product algorithm, these results provide strengthening of previous analyses. We prove that some of our conditions are necessary and sufficient for subclasses of homogeneous models, but not for general models. The experimental simulations on various classes of graphs validate our theoretical results.
引用
收藏
页码:4293 / 4305
页数:13
相关论文
共 50 条
  • [1] Convergence analysis of reweighted sum-product algorithms
    Roosta, Tanya
    Wainwright, Martin J.
    Sastry, Shankar
    2007 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING, VOL II, PTS 1-3, 2007, : 541 - 544
  • [2] Sufficient conditions for convergence of the sum-product algorithm
    Mooij, Joris M.
    Kappen, Hilbert J.
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2007, 53 (12) : 4422 - 4437
  • [3] Factor graphs and the sum-product algorithm
    Kschischang, FR
    Frey, BJ
    Loeliger, HA
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2001, 47 (02) : 498 - 519
  • [4] Sequential Uniformly Reweighted Sum-Product Algorithm for Cooperative Localization in Wireless Networks
    Li, Wei
    Yang, Zhen
    Hu, Haifeng
    INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS, 2014,
  • [5] The Sum-Product Algorithm on Small Graphs
    O'Sullivan, M. E.
    Brevik, J.
    Wolski, R.
    ADVANCES IN CODING THEORY AND CRYPTOGRAPHY, 2007, 3 : 160 - +
  • [6] Cooperative Localization and Multitarget Tracking in Agent Networks with the Sum-Product Algorithm
    Brambilla, Mattia
    Gaglione, Domenico
    Soldi, Giovanni
    Mendrzik, Rico
    Ferri, Gabriele
    LePage, Kevin D.
    Nicoli, Monica
    Willett, Peter
    Braca, Paolo
    Win, Moe Z.
    IEEE OPEN JOURNAL OF SIGNAL PROCESSING, 2022, 3 : 169 - 195
  • [7] Approximately Counting the Number of Constrained Arrays via the Sum-Product Algorithm
    Parvaresh, Farzad
    Vontobel, Pascal O.
    2012 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY PROCEEDINGS (ISIT), 2012, : 279 - 283
  • [8] THE SUM-PRODUCT ALGORITHM: ALGEBRAIC INDEPENDENCE AND COMPUTATIONAL ASPECTS
    Malvestuto, Francesco M.
    KYBERNETIKA, 2013, 49 (01) : 4 - 22
  • [9] An improved implementation of sum-product algorithm for LDPC decoder
    Wang, Zhou
    Wu, Bin
    Ye, Tianchun
    IEICE ELECTRONICS EXPRESS, 2019, 16 (04) : 1 - 8
  • [10] Simulation of the Sum-Product Algorithm Using Stratified Sampling
    Brevik, John
    O'Sullivan, Michael E.
    Umlauf, Anya
    Wolski, Rich
    APPLIED ALGEBRA, ALGEBRAIC ALGORITHMS, AND ERROR-CORRECTING CODES, 2009, 5527 : 65 - +