Overview

Graphical models (GM) are an exiting way of studying and solving problems. In a nutshell, they allow for a visual and systematic representation of variables, that encode some information, and the relation between them. This relation can be represented by an edge between variables (undirected graphs), meaning that they are related, or with a directed edge (directed graphs), meaning which variables influence other ones, or by new elements in the GM denoted as factors, that encode the relation between variables connected to them (factor graphs). GM are specially useful when variables are random and the relation are statistical ones. The structure of the resulting graph can be quite exploited to reduce the computational complexity in, e.g. computing the marginal value for a variable. A wide family of the algorithms for statistical GM work using a message interchange between variables and factors in the graph until convergente. The belief propagation (BP) algorithm is a well known one, that yields the exact solution when no loops are present in the graph.

Factor graphs (FG) are usually applied to digital communications, since it is easy to incorporate the knowledge on the system through factors. Two particular cases are the graph for channel decoding and the channel equalization problems. In channel coding every parity check is represented by a factor. In low-density parity-check (LDPC) codes, as the length of the transmitted frame increases the graph behaves as non-cyclic, and the BP allows for an optimal channel decoding with complexity linear with the frame length. In equalization, graphs are used to represent the systems a chain where at any time the observed variable depends on just a finite number of previous unobserved ones, resulting in a so-called hidden Markov model (HMM). In the case of discrete unobserved variables, the BCJR algorithm yields the symbol maximum a posteriori probabilities.

The BP in channel coding performs near capacity for quite long frames, but it degrades for finite length words, being this the case for a wide range of communications systems. The problem here is that loops become shorter. We have explore solving the graph facing the existence of cycles by approximating the optimal solution using the expectation propagation (EP). This algorithm permits approximating a full graph by another simpler one. Our solutions allows for a trade off between complexity and performance. In the limit, when complexity is increased, we proved that the EP yields the ML decoder.

In other digital communications systems, we found that the information available can be easily included when expectation propagation. In this sense we investigated approximations available for discrete HMM, when the BCJR is unaffordable due to the large number of states. This idea can be extended to many other scenarios with quite dense graphs. In particular we have explored the application to (turbo) equalization.

Involved Members

Juan J. Murillo Fuentes, Fernando Pérez-Cruz, Rafael Boloix Tortosa, Eva Arias de Reyna, Pablo M. Olmos, Luis Salamanca and Irene Santos Velázquez.

Publications

Journals

Conferences and Workshops

  1. M. Havasi, J.M. Hernández-Lobato, J.J. Murillo-Fuentes “Inference in Deep Gaussian Processes using Stochastic Gradient Hamiltonian Monte Carlo“ Neural Information and Processing Systems (NeurIPS), 2018.
  2. E. Arias-de-Reyna , D. Dardari, P. Closas, P. M. Djurić, (2018). “Estimation of Spatial Fields of NLOS/LOS Conditions for Improved Localization in Indoor Environments”, IEEE Statistical Signal Processing Workshop (SSP). Freiburg (Germany), 2018.
  3. I. Santos and P. M. Djurić, (2017) “Crowdsource-based signal strength field estimation by Gaussian processes,”  25th European Signal Processing Conference (EUSIPCO), Kos, 2017, pp. 1215-1219. ieeexplore
  4. I. Santos Velázquez I., Murillo-Fuentes J.J. Djuric P. M. (2017) “Recursive Estimation of Time-Varying RSS Fields Based on Crowdsourcing and Gaussian Processes”. IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing 2017.
  5. R. Boloix-Tortosa, F. J. Payán-Somet, E. Arias-de-Reyna and J. J. Murillo-Fuentes, (2015) “Complex kernels for proper complex-valued signals: A review,” 23rd European Signal Processing Conference (EUSIPCO), Nice, 2015, pp. 2371-2375. ieeexplore
  6. I. Santos, J. J. Murillo-Fuentes and P. M. Olmos,(2015) “Block expectation propagation equalization for ISI channels,” 23rd European Signal Processing Conference (EUSIPCO), Nice, 2015, pp. 379-383. ieeexplore
  7. L. Salamanca, J. J. Murillo-Fuentes, P. M. Olmos and F. Pérez-Cruz, (2013) “Improving the BP estimate over the AWGN channel using Tree-structured expectation propagation,” IEEE International Symposium on Information Theory, Istanbul, 2013, pp. 2990-2994. ieeexplore
  8. Luis Salamanca, Juan José Murillo-Fuentes, Pablo M. Olmos and Fernando Pérez-Cruz, (2012). ”Tree-structured Expectation Propagation for LDPC decoding over the AWGN channel”. IEEE International Workshop On Machine Learning For Signal Processing (MLSP). 23-26 Sep 2012. Santander, Spain.
  9. Pablo M. Olmos, Luis Salamanca, Juan José Murillo-Fuentes and Fernando Pérez-Cruz, (2012). ”Finite-length analysis of the TEP decoder for LDPC ensembles over the BEC”. IEEE International Symposium on Information Theory Proceedings (ISIT). Pp. 2346- 2350. Boston, 1-6 Jul. 2012.
  10. Pablo M. Olmos, J.J. Murillo-Fuentes and Fernando Pérez-Cruz, (2012). ”Capacity achieving LDPC ensembles for the TEP decoder in erasure channels”. IEEE International Symposium on Information Theory Proceedings (ISIT). Pp. 2398-2402. St. Petersburg (Russia), 31 Jul. – 5 August 2011.
  11. Pablo M. Olmos, Luis Salamanca, Juan José Murillo-Fuentes and Fernando Pérez-Cruz, (2011). ”An Application of Tree-Structured Expectation Propagation for Channel Decoding”. Neural Information Processing Systems Foundation (NIPS). Granada (Spain), 12-15 December 2011.
  12. Luis Salamanca, Pablo M. Olmos, Juan José Murillo-Fuentes and Fernando Pérez-Cruz, (2011). ”MAP decoding for LDPC codes over the Binary Erasure Channel”. IEEE Information Theory Workshop (ITW). Pp. 145-149. Paraty (Brazil), October 2011.
  13. L. Salamanca, J.J. Murillo-Fuentes and F. Pérez-Cruz, (2010). ”Bayesian BCJR for Channel Equalization and Decoding”. IEEE Machine Learning for Signal Processing (MLSP). Kittila (Finland), August 2010.
  14. P. M. Olmos, J.J. Murillo-Fuentes and F. Pérez-Cruz, (2010). ”Tree structure Expectation-Propagation for decoding LDPC codes over Binary Erasure Channels”. IEEE International Symposium on Information Theory (ISIT). Pp. 799- 803. Austin (TX), June 2010.
  15. L. Salamanca, J.J. Murillo-Fuentes and F. Pérez-Cruz, (2010). ”Channel Decoding with a Bayesian Equalizer”. IEEE International Symposium on Information Theory (ISIT). Pp. 1998-2002. Austin (TX), June 20120.

Invited Talks

  • J. Murillo-Fuentes, I. Santos, P. M. Olmos, E. Arias de Reyna Domínguez, (2018). “Expectation Propagation applied to Digital Communications Systems with Large Dimensions”. Sesión plenaria en Congreso. 3rd Workshop on Communication Networks and Power Systems. Brasilia, Brasil. 2018.
  • L. Salamanca, P. M. Olmos, J.J. Murillo-Fuentes and F. Pérez-Cruz, (2012). ”Tree-structured expectation propagation for LDPC decoding in AWGN channels”. Information Theory and Applications Workshop (ITA). San Diego (USA), February.

  • L. Salamanca, P. M. Olmos, J.J. Murillo-Fuentes and F. Pérez-Cruz, (2011). ”Reduced Complexity MAP decoder for LDPC codes over the BEC using Tree-Structure Expectation Propagation”. Information Theory and Applications (ITA). San Diego (USA), February.

  • P. M. Olmos, J.J. Murillo-Fuentes and F. Pérez-Cruz, (2010). ”Analyzing the Maxwell Decoder for LDPC Codes in Binary Erasure Channels”. Information Theory and Applications (ITA). San Diego (USA), February.

  • P. M. Olmos, J.J. Murillo-Fuentes and F. Pérez-Cruz, Luis Salamanca (2011).  ”Tree-Structured algorithm applied to LDPC decoding”, Summer Research Institute of I&C (SuRI), EPFL, Lausanne, 7-24 June.

Acknowledgements

These results were possible thanks to public fundings. The Universidad de Sevilla trusted us to carry out this research. The Spanish Government and the European Union (FEDER) also founded this research through the projects MEC.CICYT.TIC 2003-03781, TEC2006-13514-C02-2/TCM, CONSOLIDER CSD2008-00010 and TEC2012-38800-C03-C02. This work was also possible thanks to the fruitful collaboration with prof. Fernando Pérez-Cruz, from Universidad Carlos III de Madrid, member of the group.

USfeder

Copyright Notice

The material above is presented here to ensure dissemination of scholar and technical work by the author. Copyright and all rights are retained by authors and other copyright holders. Accordingly, all persons using this material are expected to adhere to the terms and constraints invoked by each holder’s copyright. Notice that, in most cases, these works may not be reposted without the explicit permission of the copyright holder.