The Role of Mixing in Message Passing Algorithms

Wed., Apr. 12

2:10-3:00PM

400 Cory (Hughes Room)

2:10-3:00PM

400 Cory (Hughes Room)

The problem of computing marginal statistics of probability distributions defined over graphs with cycles occurs in many fields: error-correction coding, machine learning, communication theory, computer vision, and statistical physics. Because exact computations are often difficult approximate algorithms based on local message passing have been developed. One such message passing algorithm is the sum-product (loopy belief propagation) algorithm. In this talk we present a framework based on infinite Gibbs measures for analyzing the sum-product algorithm. We discuss the role spatial mixing and topology have on the performance of the algorithm.