Replicated Bethe Free Energy: A Variational Principle behind Survey Propagation
arXiv:cond-mat/0506311 · doi:10.1143/JPSJ.74.2133
Abstract
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 replica symmetry on stationary points of the replicated Bethe free energy. Belief propagation and generalized SP can also be offered in the identical framework under assumptions of the highest and broken replica symmetries, respectively.
arXiv commentappeared in Journal of the Physical Society of Japan 74, 2133-2136 (2005)
References in corpus (7)
- The Bethe lattice spin glass revisited
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Coloring random graphs
- Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- Propagating beliefs in spin glass models
- A microscopic description of the aging dynamics: fluctuation-dissipation relations, effective temperature and heterogeneities
Cited by in corpus (8)
- Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
- Finite-Connectivity Spin-Glass Phase Diagrams and Low Density Parity Check Codes
- Replica Cluster Variational Method
- A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice
- Belief Propagation Algorithm for Portfolio Optimization Problems
- Survey propagation at finite temperature: application to a Sourlas code as a toy model
- Inference by replication in densely connected systems
- Survey propagation for the cascading Sourlas code