Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/931744

OpenURL Link
Title
Belief propagation as a dynamical system: the linear case and open problems
Author/Creator
Rüeffer, Bjöern S.;  Kellett, Christopher M.;  Dower, Peter M.;  Weller, Steven R.
Institution
The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
Description
Systems and control theory have found wide application in the analysis and design of numerical algorithms. We present a discrete-time dynamical system interpretation of an algorithm commonly used in information theory called Belief Propagation. Belief Propagation (BP) is one instance of the so-called Sum-Product Algorithm and arises, e.g., in the context of iterative decoding of Low-Density Parity-Check codes. We review a few known results from information theory in the language of dynamical systems and show that the typically very high dimensional, nonlinear dynamical system corresponding to BP has interesting structural properties. For the linear case we completely characterize the behavior of this dynamical system in terms of its asymptotic input-output map. Finally, we state some of the open problems concerning BP in terms of the dynamical system presented.
Relation
IET Control Theory and Applications Vol. 4, Issue 7, p. 1188-1200
Publisher Link
http://dx.doi.org/10.1049/iet-cta.2009.0233
Date
2010
Publisher
Institution of Engineering and Technology
Keyword(s)
large-scale discrete-time systems;  iterative decoding;  sum-product algorithm;  factor graphs;  convergence
Resource Type
journal article
Identifier
http://hdl.handle.net/1959.13/931744
Identifier
ISSN:1751-8644
Reviewed
Reviewed
17 Visitors 19 Hits 0 Downloads
Save/E-mail Citation
Citation Format
E-mail Address
Subject
"IET Control Theory and Applications"
 
OR