Fermions and loops on graphs: I. Loop calculus for determinants

Vladimir Y. Chernyak, Michael Chertkov

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

This paper is the first in a series devoted to evaluation of the partition function in statistical models on graphs with loops in terms of the Berezin/fermion integrals. The paper focuses on a representation of the determinant of a square matrix in terms of a finite series, where each term corresponds to a loop on the graph. The representation is based on a fermion version of the loop calculus, previously introduced by the authors for graphical models with finite alphabets. Our construction contains two levels. First, we represent the determinant in terms of an integral over anti-commuting Grassmann variables, with some reparametrization/gauge freedom hidden in the formulation. Second, we show that a special choice of the gauge, called the BP (Bethe-Peierls or belief propagation) gauge, yields the desired loop representation. The set of gauge fixing BP conditions is equivalent to the Gaussian BP equations, discussed in the past as efficient (linear scaling) heuristics for estimating the covariance of a sparse positive matrix.

Original languageEnglish
Article numberP12011
JournalJournal of Statistical Mechanics: Theory and Experiment
Volume2008
Issue number12
DOIs
Publication statusPublished - 2008
Externally publishedYes

Keywords

  • Gauge theories
  • Message-passing algorithms
  • Rigorous results in statistical mechanics

Fingerprint

Dive into the research topics of 'Fermions and loops on graphs: I. Loop calculus for determinants'. Together they form a unique fingerprint.

Cite this