Information-theoretic thresholds from the cavity method
Information-theoretic thresholds from the cavity method
复制标题
DOI：
10.1145/3055399.3055420
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
A. Coja-Oghlan;Florent Krzakala;Will Perkins;L. Zdeborová
中科院分区：
文献类型：
--
作者：
A. Coja-Oghlan;Florent Krzakala;Will Perkins;L. Zdeborová
为了证明一种复杂但不严格的物理方法--腔方法的正确性，我们建立了随机图统计推断问题中互信息的计算公式。这一一般结果暗示了对离散随机块模型中信息论阈值的猜想[Decelle等人：E（2011）]，并允许我们在随机约束满足问题（如随机图着色）中精确定位凝聚相变，从而证明来自[Krzakala等人：PNAS（2007）]。作为进一步的应用，我们建立了低密度生成矩阵码中的互信息公式，如[Montanari：IEEE Transactions on Information Theory（2005）]中所述。的证明提供了一个概念上的支撑副本对称变体的腔方法，我们预计，该方法将找到许多未来的应用。
Vindicating a sophisticated but non-rigorous physics approach called the cavity method, we establish a formula for the mutual information in statistical inference problems induced by random graphs. This general result implies the conjecture on the information-theoretic threshold in the disassortative stochastic block model [Decelle et al.: Phys. Rev. E (2011)] and allows us to pinpoint the exact condensation phase transition in random constraint satisfaction problems such as random graph coloring, thereby proving a conjecture from [Krzakala et al.: PNAS (2007)]. As a further application we establish the formula for the mutual information in Low-Density Generator Matrix codes as conjectured in [Montanari: IEEE Transactions on Information Theory (2005)]. The proofs provide a conceptual underpinning of the replica symmetric variant of the cavity method, and we expect that the approach will find many future applications.