The Bethe Free Energy Allows to Compute the Conditional Entropy of Graphical Code Instances: A Proof From the Polymer Expansion
From MaRDI portal
Publication:2976707
DOI10.1109/TIT.2016.2555843zbMATH Open1359.94340arXiv1310.1294MaRDI QIDQ2976707FDOQ2976707
Authors: M. Vuffray, Nicolas Macris 
Publication date: 28 April 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: The main objective of this paper is to explore the precise relationship between the Bethe free energy (or entropy) and the Shannon conditional entropy of graphical error correcting codes. The main result shows that the Bethe free energy associated with a low-density parity-check code used over a binary symmetric channel in a large noise regime is, with high probability, asymptotically exact as the block length grows. To arrive at this result we develop new techniques for rather general graphical models based on the loop sum as a starting point and the polymer expansion from statistical mechanics. The true free energy is computed as a series expansion containing the Bethe free energy as its zero-th order term plus a series of corrections. It is easily seen that convergence criteria for such expansions are satisfied for general high-temperature models. We apply these general results to ensembles of low-density generator-matrix and parity-check codes. While the application to generator-matrix codes follows standard "high temperature" methods, the case of parity-check codes requires non-trivial new ideas because the hard constraints correspond to a zero-temperature regime. Nevertheless one can combine the polymer expansion with expander and counting arguments to show that the difference between the true and Bethe free energies vanishes with high probability in the large block
Full work available at URL: https://arxiv.org/abs/1310.1294
Cited In (1)
This page was built for publication: The Bethe Free Energy Allows to Compute the Conditional Entropy of Graphical Code Instances: A Proof From the Polymer Expansion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976707)
