Normal Factor Graphs and Holographic Transformations

Abstract

This paper stands at the intersection of two distinct lines of research. One line is "holographic algorithms," a powerful approach introduced by Valiant for solving various counting problems in computer science; the other is "normal factor graphs," an elegant framework proposed by Forney for representing codes defined on graphs. We introduce the notion of holographic transformations for normal factor graphs, and establish a very general theorem, called the generalized Holant theorem, which relates a normal factor graph to its holographic transformation. We show that the generalized Holant theorem on the one hand underlies the principle of holographic algorithms, and on the other hand reduces to a general duality theorem for normal factor graphs, a special case of which was first proved by Forney. In the course of our development, we formalize a new semantics for normal factor graphs, which highlights various linear algebraic properties that potentially enable the use of normal factor graphs as a linear algebraic tool.

To appear IEEE Trans. Inform. Theory

References in corpus (5)

• Loop series for discrete statistical models on graphs
• Loop Calculus in Statistical Physics and Information Science
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
• On A Diagrammatic Proof of the Cayley-Hamilton Theorem
• Codes on graphs: Duality and MacWilliams identities

Cited by in corpus (18)

• Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function
• Tensor Networks contraction and the Belief Propagation algorithm
• On the MacWilliams Identity for Classical and Quantum Convolutional Codes
• A Factor-Graph Representation of Probabilities in Quantum Mechanics
• Codes on graphs: Models for elementary algebraic topology and statistical physics
• New Understanding of the Bethe Approximation and the Replica Method
• Normal Factor Graphs: A Diagrammatic Approach to Linear Algebra
• An Importance Sampling Scheme for Models in a Strong External Field
• An Importance Sampling Scheme on Dual Factor Graphs. I. Models in a Strong External Field
• A Semiclassical Proof of Duality Between the Classical BSC and the Quantum PSC
• Holographic Transformation, Belief Propagation and Loop Calculus for Generalized Probabilistic Theories
• On Stochastic Estimation of Partition Function
• Codes on Graphs: Observability, Controllability and Local Reducibility
• Local Irreducibility of Tail-Biting Trellises
• Normal Factor Graphs as Probabilistic Models
• A Factor-Graph Approach to Algebraic Topology, With Applications to Kramers--Wannier Duality
• Bitwise MAP Algorithm for Group Testing based on Holographic Transformation
• Holographic Transformation for Quantum Factor Graphs