Inference and mutual information on random factor graphs
From MaRDI portal
Publication:6345129
DOI10.4230/LIPICS.STACS.2021.24arXiv2007.07494MaRDI QIDQ6345129FDOQ6345129
Amin Coja-Oghlan, Max Hahn-Klimroth, Matija Pasch, Philipp Loick, Noela Müller, Konstantinos Panagiotou
Publication date: 15 July 2020
Abstract: Random factor graphs provide a powerful framework for the study of inference problems such as decoding problems or the stochastic block model. Information-theoretically the key quantity of interest is the mutual information between the observed factor graph and the underlying ground truth around which the factor graph was created; in the stochastic block model, this would be the planted partition. The mutual information gauges whether and how well the ground truth can be inferred from the observable data. For a very general model of random factor graphs we verify a formula for the mutual information predicted by physics techniques. As an application we prove a conjecture about low-density generator matrix codes from [Montanari: IEEE Transactions on Information Theory 2005]. Further applications include phase transitions of the stochastic block model and the mixed -spin model from physics.
Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
This page was built for publication: Inference and mutual information on random factor graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345129)
