Spin systems on Bethe lattices

The introduction of loopy belief propagation (LBP) revitalized the application of graphical models in many domains. Many recent works present improvements on the basic LBP algorithm in an attempt to overcome convergence and local optima problems. Notable among these are convexified free energy approximations that lead to inference procedures with provable convergence and quality properties. However, empirically LBP still outperforms most of its convex variants in a variety of...

This paper resolves a common complexity issue in the Bethe approximation of statistical physics and the Belief Propagation (BP) algorithm of artificial intelligence. The Bethe approximation and the BP algorithm are heuristic methods for estimating the partition function and marginal probabilities in graphical models, respectively. The computational complexity of the Bethe approximation is decided by the number of operations required to solve a set of non-linear equations, the...

We provide an explicit formula for the limiting free energy density (log-partition function divided by the number of vertices) for ferromagnetic Potts models on uniformly sparse graph sequences converging locally to the d-regular tree for d even, covering all temperature regimes. This formula coincides with the Bethe free energy functional evaluated at a suitable fixed point of the belief propagation recursion on the d-regular tree, the so-called replica symmetric solution. F...

A scheme to provide various mean-field-type approximation algorithms is presented by employing the Bethe free energy formalism to a family of replicated systems in conjunction with analytical continuation with respect to the number of replicas. In the scheme, survey propagation (SP), which is an efficient algorithm developed recently for analyzing the microscopic properties of glassy states for a fixed sample of disordered systems, can be reproduced by assuming the simplest r...

In this note we explain the use of the cavity method directly at zero temperature, in the case of the spin glass on a Bethe lattice. The computation is done explicitly in the formalism equivalent to 'one step replica symmetry breaking'; we compute the energy of the global ground state, as well as the complexity of equilibrium states at a given energy. Full results are presented for a Bethe lattice with connectivity equal to three.

We propose a generalization of the cavity method to quantum spin glasses on fixed connectivity lattices. Our work is motivated by the recent refinements of the classical technique and its potential application to quantum computational problems. We numerically solve for the phase structure of a connectivity $q=3$ transverse field Ising model on a Bethe lattice with $\pm J$ couplings, and investigate the distribution of various classical and quantum observables.

We study the dynamical low temperature behaviour of the Ising spin glass on the Bethe lattice. Starting from Glauber dynamics we propose a cavity like Ansatz that allows for the treatment of the slow (low temperature) part of dynamics. Assuming a continuous phase transitions and ultrametricity with respect to long time scales we approach the problem perturbatively near the critical temperature. The theory is formulated in terms of correlation-response-functions of arbitrary o...

The inverse Ising problem consists in inferring the coupling constants of an Ising model given the correlation matrix. The fastest methods for solving this problem are based on mean-field approximations, but which one performs better in the general case is still not completely clear. In the first part of this work, I summarize the formulas for several mean- field approximations and I derive new analytical expressions for the Bethe approximation, which allow to solve the inver...

We give explicit formulas of the Bethe approximation with multipoint correlations for systems with magnetic field. The obtained formulas include the closed form of the magnetization and the correlations between adjacent degrees of freedom. On the basis of our results, we propose a new iterative algorithm of the improved Bethe approximation. We confirm that the proposed technique is available for the random spin systems and indeed gives more accurate locations of the critical ...

The Bethe approximation, discovered in statistical physics, gives an efficient algorithm called belief propagation (BP) for approximating a partition function. BP empirically gives an accurate approximation for many problems, e.g., low-density parity-check codes, compressed sensing, etc. Recently, Vontobel gives a novel characterization of the Bethe approximation using graph cover. In this paper, a new approximation based on the Bethe approximation is proposed. The new approx...