Loop series for discrete statistical models on graphs

Michael Chertkov, Vladimir Y. Chernyak

Research output: Contribution to journalArticlepeer-review

112 Scopus citations

Abstract

In this paper we present the derivation details, logic, and motivation for the three loop calculus introduced in Chertkov and Chernyak (2006Phys.Rev.E73065102(R)). Generating functions for each of the three interrelated discrete statistical models are expressed in terms of a finite series. The first term in the series corresponds to the Bethe-Peierls belief-propagation (BP) contribution; the other terms are labelled by loops on the factor graph. All loop contributions are simple rational functions of spin correlation functions calculated within the BP approach. We discuss two alternative derivations of the loop series. One approach implements a set of local auxiliary integrations over continuous fields with the BP contribution corresponding to an integrand saddle-point value. The integrals are replaced by sums in the complementary approach, briefly explained in Chertkov and Chernyak(2006Phys.Rev.E73065102(R)). Local gauge symmetry transformations that clarify an important invariant feature of the BP solution are revealed in both approaches. The individual terms change under the gauge transformation while the partition function remains invariant. The requirement for all individual terms to be nonzero only for closed loops in the factor graph (as opposed to paths with loose ends) is equivalent to fixing the first term in the series to be exactly equal to the BP contribution. Further applications of the loop calculus to problems in statistical physics, computer and information sciences are discussed.

Original languageEnglish (US)
Article numberP06009
JournalJournal of Statistical Mechanics: Theory and Experiment
Issue number6
DOIs
StatePublished - Jun 1 2006
Externally publishedYes

Keywords

  • Analysis of algorithms
  • Exact results
  • Message-passing algorithms
  • Rigorous results in statistical mechanics

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint

Dive into the research topics of 'Loop series for discrete statistical models on graphs'. Together they form a unique fingerprint.

Cite this