Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function

DOI10.1109/TIT.2013.2264715zbMATH Open1364.94632arXiv1012.0065OpenAlexW3106495992MaRDI QIDQ5346344FDOQ5346344

Authors: Pascal O. Vontobel 

Publication date: 8 June 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We present a combinatorial characterization of the Bethe entropy function of a factor graph, such a characterization being in contrast to the original, analytical, definition of this function. We achieve this combinatorial characterization by counting valid configurations in finite graph covers of the factor graph. Analogously, we give a combinatorial characterization of the Bethe partition function, whose original definition was also of an analytical nature. As we point out, our approach has similarities to the replica method, but also stark differences. The above findings are a natural backdrop for introducing a decoder for graph-based codes that we will call symbolwise graph-cover decoding, a decoder that extends our earlier work on blockwise graph-cover decoding. Both graph-cover decoders are theoretical tools that help towards a better understanding of message-passing iterative decoding, namely blockwise graph-cover decoding links max-product (min-sum) algorithm decoding with linear programming decoding, and symbolwise graph-cover decoding links sum-product algorithm decoding with Bethe free energy function minimization at temperature one. In contrast to the Gibbs entropy function, which is a concave function, the Bethe entropy function is in general not concave everywhere. In particular, we show that every code picked from an ensemble of regular low-density parity-check codes with minimum Hamming distance growing (with high probability) linearly with the block length has a Bethe entropy function that is convex in certain regions of its domain.

Full work available at URL: https://arxiv.org/abs/1012.0065

Recommendations

• The entropy of random-free graphons and properties
• A probabilistic counting Lemma for complete graphs
• A probabilistic counting lemma for complete graphs
• An entropy argument for counting matroids
• Counting some finite-fold coverings of a graph
• On graph entropy measures based on the number of independent sets and matchings
• Hypergraphs, entropy, and inequalities
• scientific article; zbMATH DE number 861307
• On the von Neumann entropy of graphs
• On total covers of graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Linear codes (general theory) (94B05)

Cited In (7)

• Loop expansion around the Bethe approximation through the \(M\)-layer construction
• A short survey on stable polynomials, orientations and matchings
• Phase transitions for the uniform distribution in the pattern maximum likelihood problem and its Bethe approximation
• Gauges, loops, and polynomials for partition functions of graphical models
• Statistical Matching Theory
• Covers, orientations and factors
• Metastability of the Potts ferromagnet on random regular graphs

This page was built for publication: Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346344)