Sufficient conditions for convergence of the Sum-Product Algorithm

HE Sum-Product Algorithm [2], also known as Loopy Belief Propagation, which we will henceforth abbreviate as LBP, is a popular algorithm for approximate inference on graphical models. Applications can be found in diverse areas such as error correcting codes (iterative channel decoding algorithms for Turbo Codes and Low Density Parity Check Codes [3]), combinatorial optimization (satisfiability problems such as 3-SAT and graph coloring [4]) and computer vision (stereo matching [5] and image restoration [6]). LBP can be regarded as the most elementary one in a family of related algorithms, consisting of double-loop algorithms [7], GBP [8], EP [9], EC [10], the Max-Product Algorithm [11], the Survey Propagation Algorithm [4], [12] and Fractional BP [13]. A good understanding of LBP may therefore be beneficial to understanding these other algorithms as well. In practice, there are two major obstacles in the application of LBP to concrete problems: (i) if LBP converges, it is not clear whether the results are a good approximation of the exact marginals; (ii) LBP does not always converge, and in these cases gives no approximations at all. These two issues might actually be interrelated: the "folklore" is that failure of LBP to converge often indicates low quality of the Bethe approximation on which it is based. This would mean that if one has to "force" LBP to converge (e.g. by using damping or double-loop approaches), one may expect the results to be of low quality. Although LBP is an old algorithm that has been reinvented in many fields, a thorough theoretical understanding of the two aforementioned issues and their relation is still lacking. Significant progress has been made in recent years regarding the question under what conditions LBP converges (e.g.