Survey propagation at finite temperature: application to a Sourlas code as a toy model

Abstract

In this paper we investigate a finite temperature generalization of survey propagation, by applying it to the problem of finite temperature decoding of a biased finite connectivity Sourlas code for temperatures lower than the Nishimori temperature. We observe that the result is a shift of the location of the dynamical critical channel noise to larger values than the corresponding dynamical transition for belief propagation, as suggested recently by Migliorini and Saad for LDPC codes. We show how the finite temperature 1-RSB SP gives accurate results in the regime where competing approaches fail to converge or fail to recover the retrieval state.

References in corpus (17)

• The Bethe lattice spin glass revisited
• The structural glass transition and the entropy of the metastable states
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Survey propagation: an algorithm for satisfiability
• Cluster Variation Method in Statistical Physics and Probabilistic Graphical Models
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Exact solutions for diluted spin glasses and optimization problems
• The Dynamic Phase Transition for Decoding Algorithms
• Finite-connectivity systems as error-correcting codes
• Improved message passing for inference in densely connected systems
• Higher-order QED corrections to single-W production in electron-positron collisions
• Propagating beliefs in spin glass models
• Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
• Minimizing energy below the glass thresholds
• Replicated Bethe Free Energy: A Variational Principle behind Survey Propagation
• Survey propagation at finite temperature: application to a Sourlas code as a toy model

Cited by in corpus (6)

• Gallager error correcting codes for binary asymmetric channels
• Cavity approach to the Sourlas code system
• Survey propagation at finite temperature: application to a Sourlas code as a toy model
• Message passing algorithms for the Hopfield network reconstruction: threshold behavior and limitation
• Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes
• Survey propagation for the cascading Sourlas code