2012/02/27 by Nicholas Ruozzi, Ruozzi, Nicholas · 2 citations
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Advanced Wireless Communication Techniques #Combinatorics (math.CO) #Cooperative Communication and Network Coding #Discrete Mathematics (cs.DM) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #cs.DM #math-ph #math.CO #math.MP
paper · pdf · doi:10.48550/arxiv.1202.6035
Typo, bug fixes, and improved exposition
openalex publication_date 2012/02/27 · arxiv created 2012/04/16 · arxiv updated 2012/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Sudderth, Wainwright, and Willsky have conjectured that the Bethe approximation corresponding to any fixed point of the belief propagation algorithm over an attractive, pairwise binary graphical model provides a lower bound on the true partition function. In this work, we resolve this conjecture in the affirmative by demonstrating that, for any graphical model with binary variables whose potential functions (not necessarily pairwise) are all log-supermodular, the Bethe partition function always lower bounds the true partition function. The proof of this result follows from a new variant of the "four functions" theorem that may be of independent interest.