Convergence Analysis of Reweighted Sum-Product Algorithms

Many signal processing applications of graphical models require ef-ficient methods for computing (approximate) marginal probabilities over subsets of nodes in the graph. The intractability of this marginal-ization problem for general graphs with cycles motivates the use of approximate message-passing algorithms, including the sum-product algorithm and variants thereof. This paper studies the convergence and stability properties of the family of reweighted sum-product al-gorithms, a generalization of the standard updates in which messages are adjusted with graph-dependent weights. For homogenous mod-els, we provide a complete characterization of the potential settings and message weightings that guarantee uniqueness of fixed points, and convergence of the updates. For more general inhomogeneous models, we derive a set of sufficient conditions that ensure conver-gence, and provide estimates of rates. These theoretical results are complemented with experimental simulations on various classes of graphs. Index terms: Graphical model; Markov random field; belief prop-agation, sum-product algorithm; message-passing; approximate in-ference. 1