Characterizing the Bethe Partition Function of Double-Edge Factor Graphs via Graph Covers
| Autor: | Yuwen Huang, Pascal O. Vontobel |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Novel technique
Discrete mathematics Double edge 020206 networking & telecommunications 02 engineering and technology 010501 environmental sciences 01 natural sciences Graph Finite graph 0202 electrical engineering electronic engineering information engineering Quantum information Factor graph 0105 earth and related environmental sciences Mathematics |
| Zdroj: | ISIT |
| DOI: | 10.1109/isit44484.2020.9174508 |
| Popis: | 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 symmetricsubspace 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|