2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | G.1.3 | ||
| Paper Title | Characterizing the Bethe Partition Function of Double-Edge Factor Graphs via Graph Covers | ||
| Authors | Yuwen Huang, Pascal O Vontobel, The Chinese University of Hong Kong, China | ||
| Session | G.1: Graph Analytics | ||
| Presentation | Lecture | ||
| Track | Graphs, Games, Sparsity, and Signal Processing | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | For standard factor graphs (S-FGs), i.e., factor graphs with local functions taking on non-negative real values, Vontobel gave a characterization of the Bethe approximation to the partition function in terms of the partition function of finite graph covers. The proof of that statement heavily relied on the method of types. In this paper we give a similar characterization for so-called double-edge factor graphs (DE-FGs), which are a class of factor graphs where local functions take on complex values and have to satisfy some positive semi-definiteness constraints. Such factor graphs are of interest in quantum information processing. In general, approximating the partition function of DE-FGs is more challenging than for S-FGs because the partition function is a sum of complex values and not just a sum of non-negative real values. In particular, for proving the above-mentioned characterization of the Bethe approximation in terms of finite graph covers, one cannot use the method of types anymore. We overcome this challenge by applying the loop-calculus transform by Chertkov and Chernyak, along with using the symmetric-subspace transform, a novel technique for factor graphs that should be of interest beyond proving the main result of this paper. Currently, the characterization of the Bethe approximation of the partition function of DE-FGs is for DE-FGs satisfying an (easily checkable) condition. However, based on numerical results, we suspect that the characterization holds more broadly. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
