Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

   

2008 Research Summary

Convergence Analysis of Reweighted Sum-Product Algorithms

View Current Project Information

Tanya Gazelle Roosta, Martin Wainwright and S. Shankar Sastry

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 research project 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 [1]. For homogeneous models, 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 have derived a set of sufficient conditions that ensure convergence, and provide bounds on convergence rates [2].

Figure 1
Figure 1: Empirical rates of convergence of the reweighted sum-product algorithm as compared to the rate predicted by the symmetric and asymmetric bounds from the theoretical analysis

[1]
M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky, "A New Class of Upper Bounds on the Log Partition Function," IEEE Trans. Info. Theory, Vol. 51, No. 7, July 2005, pp. 2313-2335.
[2]
T. Roosta, M. Wainwright, and S. Sastry, "Convergence Analysis of Reweighted Sum-Product Algorithms," IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2007.