Loop Calculus in Statistical Physics and Information Science

Abstract

Considering a discrete and finite statistical model of a general position we introduce an exact expression for the partition function in terms of a finite series. The leading term in the series is the Bethe-Peierls (Belief Propagation)-BP contribution, the rest are expressed as loop-contributions on the factor graph and calculated directly using the BP solution. The series unveils a small parameter that often makes the BP approximation so successful. Applications of the loop calculus in statistical physics and information science are discussed.

4 pages, submitted to Phys.Rev.Lett. Changes: More general model, Simpler derivation

Cited by in corpus (51)

• Loop series for discrete statistical models on graphs
• Message passing on networks with loops
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Normal Factor Graphs and Holographic Transformations
• Belief propagation for networks with loops
• Message passing methods on complex networks
• Loop Calculus Helps to Improve Belief Propagation and Linear Programming Decodings of Low-Density-Parity-Check Codes
• Partition function loop series for a general graphical model: free energy corrections and message-passing equations
• Mathematical Programming Decoding of Binary Linear Codes: Theory and Algorithms
• Finite size corrections to disordered Ising models on Random Regular Graphs
• Loop expansion around the Bethe approximation through the $M$-layer construction
• Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix
• Approximating the Permanent with Fractional Belief Propagation
• Belief Propagation and Beyond for Particle Tracking
• Exactness of Belief Propagation for Some Graphical Models with Loops
• Replica Cluster Variational Method: the Replica Symmetric solution for the 2D random bond Ising model
• Belief Propagation and Loop Series on Planar Graphs
• A mean field method with correlations determined by linear response
• On Cavity Approximations for Graphical Models
• Replica methods for loopy sparse random graphs
• Zero temperature solutions of the Edwards-Anderson model in random Husimi Lattices
• Simulating quantum dynamics in two-dimensional lattices with tensor network influence functional belief propagation
• Improving convergence of Belief Propagation decoding
• Discrete geometric analysis of message passing algorithm on graphs
• Loop Series Expansions for Tensor Networks
• Loop series expansion with propagation diagrams
• New Understanding of the Bethe Approximation and the Replica Method
• Belief propagation on networks with cliques and chordless cycles
• Fermions and Loops on Graphs. I. Loop Calculus for Determinant
• Sums over geometries and improvements on the mean field approximation
• Belief propagation with multipoint correlations and its application to Inverse problem
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses
• Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach
• Fermions and Loops on Graphs. II. Monomer-Dimer Model as Series of Determinants
• Planar Graphical Models which are Easy
• New Generalizations of the Bethe Approximation via Asymptotic Expansion
• Susceptibility Propagation for Constraint Satisfaction Problems
• Random cluster model on regular graphs
• Quantum Cluster Variational Method and Message Passing Algorithms Revisited
• Loopy annealing belief propagation for vertex cover and matching: convergence, LP relaxation, correctness and Bethe approximation
• Loop Calculus and Bootstrap-Belief Propagation for Perfect Matchings on Arbitrary Graphs
• Anomalous finite size corrections in random field models
• Codes on Graphs: Observability, Controllability and Local Reducibility
• Graph polynomials and approximation of partition functions with Loopy Belief Propagation
• Statistical physics of loopy interactions: Independent-loop approximation and beyond
• Correcting beliefs in the mean-field and Bethe approximations using linear response
• Improving variational methods via pairwise linear response identities
• New graph polynomials from the Bethe approximation of the Ising partition function
• Tensor Network Loop Cluster Expansions for Quantum Many-Body Problems
• Forest expansion of two-body partition functions for sparse interaction graphs
• Gauging Variational Inference