Replication-based Inference Algorithms for Hard Computational Problems
arXiv:1305.2754 · doi:10.1103/PhysRevE.88.013313
Abstract
Inference algorithms based on evolving interactions between replicated solutions are introduced and analyzed on a prototypical NP-hard problem - the capacity of the binary Ising perceptron. The efficiency of the algorithm is examined numerically against that of the parallel tempering algorithm, showing improved performance in terms of the results obtained, computing requirements and simplicity of implementation.
23 pages, 2 figures
References in corpus (7)
- Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform so well over the BEC
- Learning by message-passing in networks of discrete synapses
- Weight space structure and analysis using a finite replica number in the Ising perceptron
- Statistical Mechanics Analysis of LDPC Coding in MIMO Gaussian Channels
- Learning by random walks in the weight space of the Ising perceptron
- Can a student learn optimally from two different teachers?
- Inference by replication in densely connected systems