Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/931744
- Belief propagation as a dynamical system: the linear case and open problems
Rüeffer, Bjöern S.;
Kellett, Christopher M.;
Dower, Peter M.;
Weller, Steven R.
- The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
- 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.
- IET Control Theory and Applications Vol. 4, Issue 7, p. 1188-1200
- Publisher Link
- Institution of Engineering and Technology
large-scale discrete-time systems;
- Resource Type
- journal article