Frank R. Kschischang, Brendan J. Frey and Hans-Andrea Loeliger 2001.
Factor graphs and the sum-product algorithm.
IEEE Transactions on Information Theory 47:2, February,
498-519.
A factor graph is a bipartite graph that expresses
how a "global" function of many variables factors into a product
of "local" functions.
Factor graphs subsume many other graphical models including
Bayesian networks, Markov random fields, and Tanner graphs.
Following one simple computational rule,
the sum-product algorithm operates in factor graphs to compute - either
exactly or approximately - various marginal functions
by distributed message-passing in the graph.
A wide variety of algorithms developed in artificial intelligence,
signal processing, and digital communications can be derived as
specific instances of the sum-product algorithm,
including the forward/backward algorithm, the Viterbi
algorithm, the iterative "turbo" decoding algorithm,
Pearl's belief propagation algorithm for Bayesian networks,
the Kalman filter, and certain fast Fourier transform algorithms.
Compressed postscript (.ps.Z),
uncompressed postscript (.ps),
portable document format (.pdf).
Back to Brendan Frey's home page.