Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

Belief propagation as a dynamical system: the linear case and open problems

Belief propagation as a dynamical system: the linear case and open problems

For access to this article, please select a purchase option:

Buy article PDF
$19.95
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Control Theory & Applications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Systems and control theory have found wide application in the analysis and design of numerical algorithms. The authors present an equivalent discrete-time dynamical system interpretation of an algorithm commonly used in information theory called belief propagation (BP). BP is one instance of the so-called sum–product algorithm and arises, for example, in the context of iterative decoding of low-density parity-check codes. The authors review a few known results from information theory in the language of dynamical systems and show that the typically very high-dimensional, non-linear dynamical system corresponding to BP has interesting structural properties. For the linear case, they completely characterise the behaviour of this dynamical system in terms of its asymptotic input–output map. Finally, the authors state some of the open problems concerning BP in terms of the dynamical system presented.

References

    1. 1)
      • Taga, N., Mase, S.: `Applications of Gibbs measure theory to loopy belief propagation algorithm', Proc. Fifth Mexican Int. Conf. on Artificial Intelligence MICAI 2006: Advances in Artificial Intelligence, 13–17 November 2006, Apizaco, Mexico, p. 197–207, vol. 4293.
    2. 2)
      • Kellett, C.M., Weller, S.R.: `Bifurcations and EXIT charts for the binary erasure channel', Proc. IEEE Int. Symp. on Information Theory, 9–14 July 2006, Seattle, WA, USA, p. 2559–2563.
    3. 3)
      • H.-A. Loeliger , J. Dauwels , J. Hu , S. Korl , L. Ping , F. Kschischang . The factor graph approach to model-based signal processing. Proc. IEEE , 6 , 1295 - 1322
    4. 4)
      • M. Fu . Stochastic analysis of turbo decoding. IEEE Trans. Inf. Theory , 1 , 81 - 100
    5. 5)
      • U. Helmke , J.B. Moore . (1994) Optimization and dynamical systems.
    6. 6)
      • X. Zheng , F.C.M. Lau , C.K. Tse , S.C. Wong . Study of bifurcation behavior of LDPC decoders. Int. J. Bifur. Chaos Appl. Sci. Eng. , 11 , 3435 - 3449
    7. 7)
      • R.E. Kalman . A new approach to linear filtering and prediction problems. Trans. ASME–J. Basic Eng. , 35 - 45
    8. 8)
      • Eckford, A.W.: `The factor graph EM algorithm: applications for LDPC codes', Sixth IEEE Workshop on Signal Processing Advances in Wireless Communications, June 2005, p. 910–914.
    9. 9)
      • M. Embree , R.B. Lehoucq . Dynamical systems and non-Hermitian iterative eigensolvers. SIAM J. Numer. Anal. , 2 , 1445 - 1473
    10. 10)
      • D. Agrawal , A. Vardy . The turbo decoding algorithm and its phase trajectories. IEEE Trans. Inf. Theory , 2 , 699 - 722
    11. 11)
      • A.M. Stuart , A.R. Humphries . (1996) Dynamical systems and numerical analysis.
    12. 12)
      • A. Bhaya , E. Kaszkurewicz . A control-theoretic approach to the design of zero finding numerical methods. IEEE Trans. Autom. Control , 6 , 1014 - 1026
    13. 13)
      • F.R. Kschischang , B.J. Frey , H.A. Loeliger . Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theory , 2 , 498 - 519
    14. 14)
      • A.P. Dempster , N.M. Laird , D.B. Rubin . Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Statist. Soc. Ser. B , 1 , 1 - 38
    15. 15)
      • M.T. Chu . Linear algebra algorithms as dynamical systems. Acta Numer. , 1 - 86
    16. 16)
      • Ihler, A.: `Accuracy bounds for belief propagation', Proc. 23th Conf. on Uncertainty in Artificial Intelligence UAI 2007, 19–22 July 2007, Vancouver, BC, Canada.
    17. 17)
      • K. Kashima , Y. Yamamoto . System theory for numerical analysis. Automatica , 7 , 1156 - 1164
    18. 18)
      • H.-A. Loeliger . An introduction to factor graphs. IEEE Signal Process. Mag. , 1 , 28 - 41
    19. 19)
      • S.C. Tatikonda , M.I. Jordan , A. Darwiche , N. Friedman . (2002) Loopy belief propagation and Gibbs measures’, Uncertainty in artificial intelligence.
    20. 20)
      • C.M. Kellett , S.R. Weller . Bifurcations in iterative decoding and root locus plots. IET Control Theory Appl. , 12 , 1086 - 1093
    21. 21)
      • A.T. Ihler , J.W. Fisher , A.S. Willsky . Loopy belief propagation: Convergence and effects of message errors. J. Mach. Learning Res. , 905 - 936
    22. 22)
      • R.W. Brockett . Dynamical systems that sort lists, diagonalize matrices and solve linear programming problems. Linear Algebra Appl. , 79 - 91
    23. 23)
      • Y. Weiss , W.T. Freeman . On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs. IEEE Trans. Inf. Theory , 2 , 736 - 744
    24. 24)
      • A. Bhaya , E. Kaszkurewicz . (2006) Control perspectives on numerical algorithms and matrix problems.
    25. 25)
      • J.S. Yedidia , W.T. Freeman , Y. Weiss . Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Trans. Inf. Theory , 7 , 2282 - 2312
    26. 26)
      • R. Otnes , M. Tüchler . Iterative channel estimation for turbo equalization of time-varying frequency-selective channels. IEEE Trans. Wirel. Commun. , 6 , 1918 - 1923
    27. 27)
      • International ISBN Agency: ‘ISBN users' manual international edition, 2005’. Available at: http://www.isbninternational.org/.
    28. 28)
      • J.M. Mooij , H.J. Kappen . Sufficient conditions for convergence of the sum-product algorithm. IEEE Trans. Inf. Theory , 12 , 4422 - 4437
    29. 29)
      • T. Richardson , R. Urbanke . (2008) Modern coding theory.
    30. 30)
      • Signal Processing Microelectronics. http://sigpromu.org/systemanalysis/.
    31. 31)
      • T. Heskes . On the uniqueness of loopy belief propagation fixed points. Neural Comput. , 11 , 2379 - 2413
    32. 32)
      • Dauwels, J., Korl, S., Loeliger, H.-A.: `Expectation maximization as message passing', Proc. IEEE Int. Symp. on Information Theory ISIT, September 2005, p. 583–586.
    33. 33)
      • L. Kocarev , F. Lehmann , G.M. Maggio , B. Scanavino , Z. Tasev , A. Vardy . Nonlinear dynamics of iterative decoding systems: analysis and applications. IEEE Trans. Inf. Theory , 4 , 1366 - 1384
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cta.2009.0233
Loading

Related content

content/journals/10.1049/iet-cta.2009.0233
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address