Double-Edge Factor Graphs: Definition, Properties, and Examples
arXiv:1706.00752 · doi:10.1109/ITW.2017.8277985
Abstract
Some of the most interesting quantities associated with a factor graph are its marginals and its partition sum. For factor graphs \emph{without cycles} and moderate message update complexities, the sum-product algorithm (SPA) can be used to efficiently compute these quantities exactly. Moreover, for various classes of factor graphs \emph{with cycles}, the SPA has been successfully applied to efficiently compute good approximations to these quantities. Note that in the case of factor graphs with cycles, the local functions are usually non-negative real-valued functions. In this paper we introduce a class of factor graphs, called double-edge factor graphs (DE-FGs), which allow local functions to be complex-valued and only require them, in some suitable sense, to be positive semi-definite. We discuss various properties of the SPA when running it on DE-FGs and we show promising numerical results for various example DE-FGs, some of which have connections to quantum information processing.
arXiv commentSubmitted
References in corpus (5)
- Quantum Graphical Models and Belief Propagation
- The Bethe Permanent of a Non-Negative Matrix
- Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function
- A Factor-Graph Representation of Probabilities in Quantum Mechanics
- Estimating the Information Rate of a Channel with Classical Input and Output and a Quantum State (Extended Version)