## 2015 |

Santos, Irene; Murillo-Fuentes, Juan Jose; Olmos, Pablo M Block Expectation Propagation Equalization for ISI Channels Inproceedings 2015 23rd European Signal Processing Conference (EUSIPCO), pp. 379–383, IEEE, Nice, 2015, ISBN: 978-0-9928-6263-3. Abstract | Links | BibTeX | Tags: Approximation algorithms, Approximation methods, BCJR algorithm, channel equalization, Complexity theory, Decoding, Equalizers, expectation propagation, ISI, low complexity, Signal processing algorithms @inproceedings{Santos2015, title = {Block Expectation Propagation Equalization for ISI Channels}, author = {Irene Santos and Juan Jose Murillo-Fuentes and Pablo M Olmos}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7362409}, doi = {10.1109/EUSIPCO.2015.7362409}, isbn = {978-0-9928-6263-3}, year = {2015}, date = {2015-08-01}, booktitle = {2015 23rd European Signal Processing Conference (EUSIPCO)}, pages = {379--383}, publisher = {IEEE}, address = {Nice}, abstract = {Actual communications systems use high-order modulations and channels with memory. However, as the memory of the channels and the order of the constellations grow, optimal equalization such as BCJR algorithm is computationally intractable, as their complexity increases exponentially with the number of taps and size of modulation. In this paper, we propose a novel low-complexity hard and soft output equalizer based on the Expectation Propagation (EP) algorithm that provides high-accuracy posterior probability estimations at the input of the channel decoder with similar computational complexity than the linear MMSE. We experimentally show that this quasi-optimal solution outperforms classical solutions reducing the bit error probability with low complexity when LDPC channel decoding is used, avoiding the curse of dimensionality with channel memory and constellation size.}, keywords = {Approximation algorithms, Approximation methods, BCJR algorithm, channel equalization, Complexity theory, Decoding, Equalizers, expectation propagation, ISI, low complexity, Signal processing algorithms}, pubstate = {published}, tppubtype = {inproceedings} } Actual communications systems use high-order modulations and channels with memory. However, as the memory of the channels and the order of the constellations grow, optimal equalization such as BCJR algorithm is computationally intractable, as their complexity increases exponentially with the number of taps and size of modulation. In this paper, we propose a novel low-complexity hard and soft output equalizer based on the Expectation Propagation (EP) algorithm that provides high-accuracy posterior probability estimations at the input of the channel decoder with similar computational complexity than the linear MMSE. We experimentally show that this quasi-optimal solution outperforms classical solutions reducing the bit error probability with low complexity when LDPC channel decoding is used, avoiding the curse of dimensionality with channel memory and constellation size. |

Fernandez-Bes, Jesus; Elvira, Victor; Vaerenbergh, Steven Van A Probabilistic Least-Mean-Squares Filter Inproceedings 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2199–2203, IEEE, Brisbane, 2015, ISBN: 978-1-4673-6997-8. Abstract | Links | BibTeX | Tags: adaptable step size LMS algorithm, Adaptation models, adaptive filtering, Approximation algorithms, Bayesian machine learning techniques, efficient approximation algorithm, filtering theory, Least squares approximations, least-mean-squares, probabilistic least mean squares filter, Probabilistic logic, probabilisticmodels, Probability, Signal processing algorithms, Standards, state-space models @inproceedings{Fernandez-Bes2015, title = {A Probabilistic Least-Mean-Squares Filter}, author = {Jesus Fernandez-Bes and Victor Elvira and Steven Van Vaerenbergh}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=7178361 http://www.tsc.uc3m.es/~velvira/papers/ICASSP2015_bes.pdf}, doi = {10.1109/ICASSP.2015.7178361}, isbn = {978-1-4673-6997-8}, year = {2015}, date = {2015-04-01}, booktitle = {2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)}, pages = {2199--2203}, publisher = {IEEE}, address = {Brisbane}, abstract = {We introduce a probabilistic approach to the LMS filter. By means of an efficient approximation, this approach provides an adaptable step-size LMS algorithm together with a measure of uncertainty about the estimation. In addition, the proposed approximation preserves the linear complexity of the standard LMS. Numerical results show the improved performance of the algorithm with respect to standard LMS and state-of-the-art algorithms with similar complexity. The goal of this work, therefore, is to open the door to bring somemore Bayesian machine learning techniques to adaptive filtering.}, keywords = {adaptable step size LMS algorithm, Adaptation models, adaptive filtering, Approximation algorithms, Bayesian machine learning techniques, efficient approximation algorithm, filtering theory, Least squares approximations, least-mean-squares, probabilistic least mean squares filter, Probabilistic logic, probabilisticmodels, Probability, Signal processing algorithms, Standards, state-space models}, pubstate = {published}, tppubtype = {inproceedings} } We introduce a probabilistic approach to the LMS filter. By means of an efficient approximation, this approach provides an adaptable step-size LMS algorithm together with a measure of uncertainty about the estimation. In addition, the proposed approximation preserves the linear complexity of the standard LMS. Numerical results show the improved performance of the algorithm with respect to standard LMS and state-of-the-art algorithms with similar complexity. The goal of this work, therefore, is to open the door to bring somemore Bayesian machine learning techniques to adaptive filtering. |

## 2014 |

Miguez, Joaquin On the uniform asymptotic convergence of a distributed particle filter Inproceedings 2014 IEEE 8th Sensor Array and Multichannel Signal Processing Workshop (SAM), pp. 241–244, IEEE, A Coruña, 2014, ISBN: 978-1-4799-1481-4. Abstract | Links | BibTeX | Tags: ad hoc networks, Approximation algorithms, approximation errors, Approximation methods, classical convergence theorems, Convergence, convergence of numerical methods, distributed particle filter scheme, distributed signal processing algorithms, Monte Carlo methods, parallel computing systems, particle filtering (numerical methods), Signal processing, Signal processing algorithms, stability assumptions, uniform asymptotic convergence, Wireless Sensor Networks, WSNs @inproceedings{Miguez2014, title = {On the uniform asymptotic convergence of a distributed particle filter}, author = {Joaquin Miguez}, url = {http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=6882385}, doi = {10.1109/SAM.2014.6882385}, isbn = {978-1-4799-1481-4}, year = {2014}, date = {2014-06-01}, booktitle = {2014 IEEE 8th Sensor Array and Multichannel Signal Processing Workshop (SAM)}, pages = {241--244}, publisher = {IEEE}, address = {A Coruña}, abstract = {Distributed signal processing algorithms suitable for their implementation over wireless sensor networks (WSNs) and ad hoc networks with communications and computing capabilities have become a hot topic during the past years. One class of algorithms that have received special attention are particles filters. However, most distributed versions of this type of methods involve various heuristic or simplifying approximations and, as a consequence, classical convergence theorems for standard particle filters do not hold for their distributed counterparts. In this paper, we look into a distributed particle filter scheme that has been proposed for implementation in both parallel computing systems and WSNs, and prove that, under certain stability assumptions regarding the physical system of interest, its asymptotic convergence is guaranteed. Moreover, we show that convergence is attained uniformly over time. This means that approximation errors can be kept bounded for an arbitrarily long period of time without having to progressively increase the computational effort.}, keywords = {ad hoc networks, Approximation algorithms, approximation errors, Approximation methods, classical convergence theorems, Convergence, convergence of numerical methods, distributed particle filter scheme, distributed signal processing algorithms, Monte Carlo methods, parallel computing systems, particle filtering (numerical methods), Signal processing, Signal processing algorithms, stability assumptions, uniform asymptotic convergence, Wireless Sensor Networks, WSNs}, pubstate = {published}, tppubtype = {inproceedings} } Distributed signal processing algorithms suitable for their implementation over wireless sensor networks (WSNs) and ad hoc networks with communications and computing capabilities have become a hot topic during the past years. One class of algorithms that have received special attention are particles filters. However, most distributed versions of this type of methods involve various heuristic or simplifying approximations and, as a consequence, classical convergence theorems for standard particle filters do not hold for their distributed counterparts. In this paper, we look into a distributed particle filter scheme that has been proposed for implementation in both parallel computing systems and WSNs, and prove that, under certain stability assumptions regarding the physical system of interest, its asymptotic convergence is guaranteed. Moreover, we show that convergence is attained uniformly over time. This means that approximation errors can be kept bounded for an arbitrarily long period of time without having to progressively increase the computational effort. |

Cespedes, Javier; Olmos, Pablo M; Sanchez-Fernandez, Matilde; Perez-Cruz, Fernando Improved Performance of LDPC-Coded MIMO Systems with EP-based Soft-Decisions Inproceedings 2014 IEEE International Symposium on Information Theory, pp. 1997–2001, IEEE, Honolulu, 2014, ISBN: 978-1-4799-5186-4. Abstract | Links | BibTeX | Tags: Approximation algorithms, Approximation methods, approximation theory, Channel Coding, channel decoder, communication complexity, complexity, Complexity theory, Detectors, encoding scheme, EP soft bit probability, EP-based soft decision, error statistics, expectation propagation, expectation-maximisation algorithm, expectation-propagation algorithm, Gaussian approximation, Gaussian channels, LDPC, LDPC coded MIMO system, Low Complexity receiver, MIMO, MIMO communication, MIMO communication systems, MIMO receiver, modern communication system, multiple input multiple output, parity check codes, per-antenna soft bit probability, posterior marginalization problem, posterior probability computation, QAM constellation, Quadrature amplitude modulation, radio receivers, signaling, spectral analysis, spectral efficiency maximization, symbol detection, telecommunication signalling, Vectors @inproceedings{Cespedes2014b, title = {Improved Performance of LDPC-Coded MIMO Systems with EP-based Soft-Decisions}, author = {Javier Cespedes and Pablo M Olmos and Matilde Sanchez-Fernandez and Fernando Perez-Cruz}, url = {http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=6875183}, isbn = {978-1-4799-5186-4}, year = {2014}, date = {2014-01-01}, booktitle = {2014 IEEE International Symposium on Information Theory}, pages = {1997--2001}, publisher = {IEEE}, address = {Honolulu}, abstract = {Modern communications systems use efficient encoding schemes, multiple-input multiple-output (MIMO) and high-order QAM constellations for maximizing spectral efficiency. However, as the dimensions of the system grow, the design of efficient and low-complexity MIMO receivers possesses technical challenges. Symbol detection can no longer rely on conventional approaches for posterior probability computation due to complexity. Marginalization of this posterior to obtain per-antenna soft-bit probabilities to be fed to a channel decoder is computationally challenging when realistic signaling is used. In this work, we propose to use Expectation Propagation (EP) algorithm to provide an accurate low-complexity Gaussian approximation to the posterior, easily solving the posterior marginalization problem. EP soft-bit probabilities are used in an LDPC-coded MIMO system, achieving outstanding performance improvement compared to similar approaches in the literature for low-complexity LDPC MIMO decoding.}, keywords = {Approximation algorithms, Approximation methods, approximation theory, Channel Coding, channel decoder, communication complexity, complexity, Complexity theory, Detectors, encoding scheme, EP soft bit probability, EP-based soft decision, error statistics, expectation propagation, expectation-maximisation algorithm, expectation-propagation algorithm, Gaussian approximation, Gaussian channels, LDPC, LDPC coded MIMO system, Low Complexity receiver, MIMO, MIMO communication, MIMO communication systems, MIMO receiver, modern communication system, multiple input multiple output, parity check codes, per-antenna soft bit probability, posterior marginalization problem, posterior probability computation, QAM constellation, Quadrature amplitude modulation, radio receivers, signaling, spectral analysis, spectral efficiency maximization, symbol detection, telecommunication signalling, Vectors}, pubstate = {published}, tppubtype = {inproceedings} } Modern communications systems use efficient encoding schemes, multiple-input multiple-output (MIMO) and high-order QAM constellations for maximizing spectral efficiency. However, as the dimensions of the system grow, the design of efficient and low-complexity MIMO receivers possesses technical challenges. Symbol detection can no longer rely on conventional approaches for posterior probability computation due to complexity. Marginalization of this posterior to obtain per-antenna soft-bit probabilities to be fed to a channel decoder is computationally challenging when realistic signaling is used. In this work, we propose to use Expectation Propagation (EP) algorithm to provide an accurate low-complexity Gaussian approximation to the posterior, easily solving the posterior marginalization problem. EP soft-bit probabilities are used in an LDPC-coded MIMO system, achieving outstanding performance improvement compared to similar approaches in the literature for low-complexity LDPC MIMO decoding. |

## 2013 |

Salamanca, Luis; Murillo-Fuentes, Juan Jose; Olmos, Pablo M; Perez-Cruz, Fernando Improving the BP Estimate over the AWGN Channel Using Tree-Structured Expectation Propagation Inproceedings 2013 IEEE International Symposium on Information Theory, pp. 2990–2994, IEEE, Istanbul, 2013, ISSN: 2157-8095. Abstract | Links | BibTeX | Tags: Approximation algorithms, Approximation methods, AWGN channels, BEC, belief propagation decoding, BI-AWGN channel, binary additive white Gaussian noise channel, binary erasure channel, BP estimation, Channel Coding, Complexity theory, error rate reduction, error statistics, Expectation, finite-length codes, Iterative decoding, LDPC codes, LDPC decoding, low-density parity-check decoding, Maximum likelihood decoding, parity check codes, posterior distribution, Propagation, TEP algorithm, tree-structured expectation propagation algorithm, trees (mathematics) @inproceedings{Salamanca2013, title = {Improving the BP Estimate over the AWGN Channel Using Tree-Structured Expectation Propagation}, author = {Luis Salamanca and Juan Jose Murillo-Fuentes and Pablo M Olmos and Fernando Perez-Cruz}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6620774}, issn = {2157-8095}, year = {2013}, date = {2013-01-01}, booktitle = {2013 IEEE International Symposium on Information Theory}, pages = {2990--2994}, publisher = {IEEE}, address = {Istanbul}, abstract = {In this paper, we propose the tree-structured expectation propagation (TEP) algorithm for low-density parity-check (LDPC) decoding over the binary additive white Gaussian noise (BI-AWGN) channel. By approximating the posterior distribution by a tree-structure factorization, the TEP has been proven to improve belief propagation (BP) decoding over the binary erasure channel (BEC). We show for the AWGN channel how the TEP decoder is also able to capture additional information disregarded by the BP solution, which leads to a noticeable reduction of the error rate for finite-length codes. We show that for the range of codes of interest, the TEP gain is obtained with a slight increase in complexity over that of the BP algorithm. An efficient way of constructing the tree-like structure is also described.}, keywords = {Approximation algorithms, Approximation methods, AWGN channels, BEC, belief propagation decoding, BI-AWGN channel, binary additive white Gaussian noise channel, binary erasure channel, BP estimation, Channel Coding, Complexity theory, error rate reduction, error statistics, Expectation, finite-length codes, Iterative decoding, LDPC codes, LDPC decoding, low-density parity-check decoding, Maximum likelihood decoding, parity check codes, posterior distribution, Propagation, TEP algorithm, tree-structured expectation propagation algorithm, trees (mathematics)}, pubstate = {published}, tppubtype = {inproceedings} } In this paper, we propose the tree-structured expectation propagation (TEP) algorithm for low-density parity-check (LDPC) decoding over the binary additive white Gaussian noise (BI-AWGN) channel. By approximating the posterior distribution by a tree-structure factorization, the TEP has been proven to improve belief propagation (BP) decoding over the binary erasure channel (BEC). We show for the AWGN channel how the TEP decoder is also able to capture additional information disregarded by the BP solution, which leads to a noticeable reduction of the error rate for finite-length codes. We show that for the range of codes of interest, the TEP gain is obtained with a slight increase in complexity over that of the BP algorithm. An efficient way of constructing the tree-like structure is also described. |

Olmos, Pablo M; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando Tree-Structure Expectation Propagation for LDPC Decoding Over the BEC Journal Article IEEE Transactions on Information Theory, 59 (6), pp. 3354–3377, 2013, ISSN: 0018-9448. Abstract | Links | BibTeX | Tags: Algorithm design and analysis, Approximation algorithms, Approximation methods, BEC, belief propagation, Belief-propagation (BP), binary erasure channel, Complexity theory, decode low-density parity-check codes, Decoding, discrete memoryless channels, expectation propagation, finite-length analysis, LDPC codes, LDPC decoding, parity check codes, peeling-type algorithm, Probability density function, random graph evolution, Tanner graph, tree-structure expectation propagation @article{Olmos2013b, title = {Tree-Structure Expectation Propagation for LDPC Decoding Over the BEC}, author = {Pablo M Olmos and Juan Jose Murillo-Fuentes and Fernando Perez-Cruz}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6451276}, issn = {0018-9448}, year = {2013}, date = {2013-01-01}, journal = {IEEE Transactions on Information Theory}, volume = {59}, number = {6}, pages = {3354--3377}, abstract = {We present the tree-structure expectation propagation (Tree-EP) algorithm to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). Expectation propagation generalizes belief propagation (BP) in two ways. First, it can be used with any exponential family distribution over the cliques in the graph. Second, it can impose additional constraints on the marginal distributions. We use this second property to impose pairwise marginal constraints over pairs of variables connected to a check node of the LDPC code's Tanner graph. Thanks to these additional constraints, the Tree-EP marginal estimates for each variable in the graph are more accurate than those provided by BP. We also reformulate the Tree-EP algorithm for the binary erasure channel (BEC) as a peeling-type algorithm (TEP) and we show that the algorithm has the same computational complexity as BP and it decodes a higher fraction of errors. We describe the TEP decoding process by a set of differential equations that represents the expected residual graph evolution as a function of the code parameters. The solution of these equations is used to predict the TEP decoder performance in both the asymptotic regime and the finite-length regimes over the BEC. While the asymptotic threshold of the TEP decoder is the same as the BP decoder for regular and optimized codes, we propose a scaling law for finite-length LDPC codes, which accurately approximates the TEP improved performance and facilitates its optimization.}, keywords = {Algorithm design and analysis, Approximation algorithms, Approximation methods, BEC, belief propagation, Belief-propagation (BP), binary erasure channel, Complexity theory, decode low-density parity-check codes, Decoding, discrete memoryless channels, expectation propagation, finite-length analysis, LDPC codes, LDPC decoding, parity check codes, peeling-type algorithm, Probability density function, random graph evolution, Tanner graph, tree-structure expectation propagation}, pubstate = {published}, tppubtype = {article} } We present the tree-structure expectation propagation (Tree-EP) algorithm to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). Expectation propagation generalizes belief propagation (BP) in two ways. First, it can be used with any exponential family distribution over the cliques in the graph. Second, it can impose additional constraints on the marginal distributions. We use this second property to impose pairwise marginal constraints over pairs of variables connected to a check node of the LDPC code's Tanner graph. Thanks to these additional constraints, the Tree-EP marginal estimates for each variable in the graph are more accurate than those provided by BP. We also reformulate the Tree-EP algorithm for the binary erasure channel (BEC) as a peeling-type algorithm (TEP) and we show that the algorithm has the same computational complexity as BP and it decodes a higher fraction of errors. We describe the TEP decoding process by a set of differential equations that represents the expected residual graph evolution as a function of the code parameters. The solution of these equations is used to predict the TEP decoder performance in both the asymptotic regime and the finite-length regimes over the BEC. While the asymptotic threshold of the TEP decoder is the same as the BP decoder for regular and optimized codes, we propose a scaling law for finite-length LDPC codes, which accurately approximates the TEP improved performance and facilitates its optimization. |

Salamanca, Luis; Olmos, Pablo M; Perez-Cruz, Fernando; Murillo-Fuentes, Juan Jose Tree-Structured Expectation Propagation for LDPC Decoding over BMS Channels Journal Article IEEE Transactions on Communications, 61 (10), pp. 4086–4095, 2013, ISSN: 0090-6778. Abstract | Links | BibTeX | Tags: Approximation algorithms, Approximation methods, BEC, belief propagation, binary erasure channel, binary memoryless symmetric channels, BMS channels, Channel Coding, Complexity theory, convolutional codes, convolutional low-density parity-check codes, Decoding, decoding block, expectation propagation, finite-length codes, LDPC decoding, message-passing algorithm, parity check codes, Probability density function, sparse linear codes, TEP algorithm, tree-structured expectation propagation, trees (mathematics), Vegetation @article{Salamanca2013a, title = {Tree-Structured Expectation Propagation for LDPC Decoding over BMS Channels}, author = {Luis Salamanca and Pablo M Olmos and Fernando Perez-Cruz and Juan Jose Murillo-Fuentes}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6587624}, issn = {0090-6778}, year = {2013}, date = {2013-01-01}, journal = {IEEE Transactions on Communications}, volume = {61}, number = {10}, pages = {4086--4095}, abstract = {In this paper, we put forward the tree-structured expectation propagation (TEP) algorithm for decoding block and convolutional low-density parity-check codes over any binary channel. We have already shown that TEP improves belief propagation (BP) over the binary erasure channel (BEC) by imposing marginal constraints over a set of pairs of variables that form a tree or a forest. The TEP decoder is a message-passing algorithm that sequentially builds a tree/forest of erased variables to capture additional information disregarded by the standard BP decoder, which leads to a noticeable reduction of the error rate for finite-length codes. In this paper, we show how the TEP can be extended to any channel, specifically to binary memoryless symmetric (BMS) channels. We particularly focus on how the TEP algorithm can be adapted for any channel model and, more importantly, how to choose the tree/forest to keep the gains observed for block and convolutional LDPC codes over the BEC.}, keywords = {Approximation algorithms, Approximation methods, BEC, belief propagation, binary erasure channel, binary memoryless symmetric channels, BMS channels, Channel Coding, Complexity theory, convolutional codes, convolutional low-density parity-check codes, Decoding, decoding block, expectation propagation, finite-length codes, LDPC decoding, message-passing algorithm, parity check codes, Probability density function, sparse linear codes, TEP algorithm, tree-structured expectation propagation, trees (mathematics), Vegetation}, pubstate = {published}, tppubtype = {article} } In this paper, we put forward the tree-structured expectation propagation (TEP) algorithm for decoding block and convolutional low-density parity-check codes over any binary channel. We have already shown that TEP improves belief propagation (BP) over the binary erasure channel (BEC) by imposing marginal constraints over a set of pairs of variables that form a tree or a forest. The TEP decoder is a message-passing algorithm that sequentially builds a tree/forest of erased variables to capture additional information disregarded by the standard BP decoder, which leads to a noticeable reduction of the error rate for finite-length codes. In this paper, we show how the TEP can be extended to any channel, specifically to binary memoryless symmetric (BMS) channels. We particularly focus on how the TEP algorithm can be adapted for any channel model and, more importantly, how to choose the tree/forest to keep the gains observed for block and convolutional LDPC codes over the BEC. |

Salamanca, Luis; Olmos, Pablo M; Murillo-Fuentes, Juan Jose; Perez-Cruz, Fernando Tree Expectation Propagation for ML Decoding of LDPC Codes over the BEC Journal Article IEEE Transactions on Communications, 61 (2), pp. 465–473, 2013, ISSN: 0090-6778. Abstract | Links | BibTeX | Tags: approximate inference, Approximation algorithms, Approximation methods, BEC, binary codes, binary erasure channel, code graph, Complexity theory, equivalent complexity, Gaussian elimination method, Gaussian processes, generalized tree-structured expectation propagatio, graphical message-passing procedure, graphical models, LDPC codes, Maximum likelihood decoding, maximum likelihood solution, ML decoding, parity check codes, peeling decoder, tree expectation propagation, tree graph, Tree graphs, tree-structured expectation propagation, tree-structured expectation propagation decoder, trees (mathematics) @article{Salamanca2013b, title = {Tree Expectation Propagation for ML Decoding of LDPC Codes over the BEC}, author = {Luis Salamanca and Pablo M Olmos and Juan Jose Murillo-Fuentes and Fernando Perez-Cruz}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6384612}, issn = {0090-6778}, year = {2013}, date = {2013-01-01}, journal = {IEEE Transactions on Communications}, volume = {61}, number = {2}, pages = {465--473}, abstract = {We propose a decoding algorithm for LDPC codes that achieves the maximum likelihood (ML) solution over the binary erasure channel (BEC). In this channel, the tree-structured expectation propagation (TEP) decoder improves the peeling decoder (PD) by processing check nodes of degree one and two. However, it does not achieve the ML solution, as the tree structure of the TEP allows only for approximate inference. In this paper, we provide the procedure to construct the structure needed for exact inference. This algorithm, denoted as generalized tree-structured expectation propagation (GTEP), modifies the code graph by recursively eliminating any check node and merging this information in the remaining graph. The GTEP decoder upon completion either provides the unique ML solution or a tree graph in which the number of parent nodes indicates the multiplicity of the ML solution. We also explain the algorithm as a Gaussian elimination method, relating the GTEP to other ML solutions. Compared to previous approaches, it presents an equivalent complexity, it exhibits a simpler graphical message-passing procedure and, most interesting, the algorithm can be generalized to other channels.}, keywords = {approximate inference, Approximation algorithms, Approximation methods, BEC, binary codes, binary erasure channel, code graph, Complexity theory, equivalent complexity, Gaussian elimination method, Gaussian processes, generalized tree-structured expectation propagatio, graphical message-passing procedure, graphical models, LDPC codes, Maximum likelihood decoding, maximum likelihood solution, ML decoding, parity check codes, peeling decoder, tree expectation propagation, tree graph, Tree graphs, tree-structured expectation propagation, tree-structured expectation propagation decoder, trees (mathematics)}, pubstate = {published}, tppubtype = {article} } We propose a decoding algorithm for LDPC codes that achieves the maximum likelihood (ML) solution over the binary erasure channel (BEC). In this channel, the tree-structured expectation propagation (TEP) decoder improves the peeling decoder (PD) by processing check nodes of degree one and two. However, it does not achieve the ML solution, as the tree structure of the TEP allows only for approximate inference. In this paper, we provide the procedure to construct the structure needed for exact inference. This algorithm, denoted as generalized tree-structured expectation propagation (GTEP), modifies the code graph by recursively eliminating any check node and merging this information in the remaining graph. The GTEP decoder upon completion either provides the unique ML solution or a tree graph in which the number of parent nodes indicates the multiplicity of the ML solution. We also explain the algorithm as a Gaussian elimination method, relating the GTEP to other ML solutions. Compared to previous approaches, it presents an equivalent complexity, it exhibits a simpler graphical message-passing procedure and, most interesting, the algorithm can be generalized to other channels. |

## 2012 |

Salamanca, Luis; Murillo-Fuentes, Juan Jose; Olmos, Pablo M; Perez-Cruz, Fernando Tree-Structured Expectation Propagation for LDPC Decoding over the AWGN Channel Inproceedings 2012 IEEE International Workshop on Machine Learning for Signal Processing, pp. 1–6, IEEE, Santander, 2012, ISSN: 1551-2541. Abstract | Links | BibTeX | Tags: additive white Gaussian noise channel, Approximation algorithms, Approximation methods, approximation theory, AWGN channel, AWGN channels, belief propagation solution, Bit error rate, Decoding, error floor reduction, finite-length regime, Gain, Joints, LDPC decoding, low-density parity-check decoding, pairwise marginal constraint, parity check codes, TEP decoder, tree-like approximation, tree-structured expectation propagation, trees (mathematics) @inproceedings{Salamanca2012, title = {Tree-Structured Expectation Propagation for LDPC Decoding over the AWGN Channel}, author = {Luis Salamanca and Juan Jose Murillo-Fuentes and Pablo M Olmos and Fernando Perez-Cruz}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6349716}, issn = {1551-2541}, year = {2012}, date = {2012-01-01}, booktitle = {2012 IEEE International Workshop on Machine Learning for Signal Processing}, pages = {1--6}, publisher = {IEEE}, address = {Santander}, abstract = {In this paper, we propose the tree-structured expectation propagation (TEP) algorithm for low-density parity-check (LDPC) decoding over the additive white Gaussian noise (AWGN) channel. By imposing a tree-like approximation over the graphical model of the code, this algorithm introduces pairwise marginal constraints over pairs of variables, which provide joint information of the variables related. Thanks to this, the proposed TEP decoder improves the performance of the standard belief propagation (BP) solution. An efficient way of constructing the tree-like structure is also described. The simulation results illustrate the TEP decoder gain in the finite-length regime, compared to the standard BP solution. For code lengths shorter than n = 512, the gain in the waterfall region achieves up to 0.25 dB. We also notice a remarkable reduction of the error floor.}, keywords = {additive white Gaussian noise channel, Approximation algorithms, Approximation methods, approximation theory, AWGN channel, AWGN channels, belief propagation solution, Bit error rate, Decoding, error floor reduction, finite-length regime, Gain, Joints, LDPC decoding, low-density parity-check decoding, pairwise marginal constraint, parity check codes, TEP decoder, tree-like approximation, tree-structured expectation propagation, trees (mathematics)}, pubstate = {published}, tppubtype = {inproceedings} } In this paper, we propose the tree-structured expectation propagation (TEP) algorithm for low-density parity-check (LDPC) decoding over the additive white Gaussian noise (AWGN) channel. By imposing a tree-like approximation over the graphical model of the code, this algorithm introduces pairwise marginal constraints over pairs of variables, which provide joint information of the variables related. Thanks to this, the proposed TEP decoder improves the performance of the standard belief propagation (BP) solution. An efficient way of constructing the tree-like structure is also described. The simulation results illustrate the TEP decoder gain in the finite-length regime, compared to the standard BP solution. For code lengths shorter than n = 512, the gain in the waterfall region achieves up to 0.25 dB. We also notice a remarkable reduction of the error floor. |

## 2011 |

Balasingam, Balakumar; Bolic, Miodrag; Djuric, Petar M; Miguez, Joaquin Efficient Distributed Resampling for Particle Filters Inproceedings 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3772–3775, IEEE, Prague, 2011, ISSN: 1520-6149. Abstract | Links | BibTeX | Tags: Approximation algorithms, Copper, Covariance matrix, distributed resampling, Markov processes, Probability density function, Sequential Monte-Carlo methods, Signal processing, Signal processing algorithms @inproceedings{Balasingam2011, title = {Efficient Distributed Resampling for Particle Filters}, author = {Balakumar Balasingam and Miodrag Bolic and Petar M Djuric and Joaquin Miguez}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5947172}, issn = {1520-6149}, year = {2011}, date = {2011-01-01}, booktitle = {2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)}, pages = {3772--3775}, publisher = {IEEE}, address = {Prague}, abstract = {In particle filtering, resampling is the only step that cannot be fully parallelized. Recently, we have proposed algorithms for distributed resampling implemented on architectures with concurrent processing elements (PEs). The objective of distributed resampling is to reduce the communication among the PEs while not compromising the performance of the particle filter. An additional objective for implementation is to reduce the communication among the PEs. In this paper, we report an improved version of the distributed resampling algorithm that optimally selects the particles for communication between the PEs of the distributed scheme. Computer simulations are provided that demonstrate the improved performance of the proposed algorithm.}, keywords = {Approximation algorithms, Copper, Covariance matrix, distributed resampling, Markov processes, Probability density function, Sequential Monte-Carlo methods, Signal processing, Signal processing algorithms}, pubstate = {published}, tppubtype = {inproceedings} } In particle filtering, resampling is the only step that cannot be fully parallelized. Recently, we have proposed algorithms for distributed resampling implemented on architectures with concurrent processing elements (PEs). The objective of distributed resampling is to reduce the communication among the PEs while not compromising the performance of the particle filter. An additional objective for implementation is to reduce the communication among the PEs. In this paper, we report an improved version of the distributed resampling algorithm that optimally selects the particles for communication between the PEs of the distributed scheme. Computer simulations are provided that demonstrate the improved performance of the proposed algorithm. |

Maiz, Cristina S; Miguez, Joaquin On the Optimization of Transportation Routes with Multiple Destinations in Random Networks Inproceedings 2011 IEEE Statistical Signal Processing Workshop (SSP), pp. 349–352, IEEE, Nice, 2011, ISBN: 978-1-4577-0569-4. Abstract | Links | BibTeX | Tags: Approximation algorithms, communication networks, Estimation, graph theory, Histograms, intelligent transportation, Monte Carlo algorithm, Monte Carlo methods, multiple destinations, optimisation, Optimization, random networks, route optimization, routing, Sequential Monte Carlo, Signal processing algorithms, stochastic graph, Stochastic processes, telecommunication network routing, time-varying graph, transportation routes @inproceedings{Maiz2011, title = {On the Optimization of Transportation Routes with Multiple Destinations in Random Networks}, author = {Cristina S Maiz and Joaquin Miguez}, url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5967701}, isbn = {978-1-4577-0569-4}, year = {2011}, date = {2011-01-01}, booktitle = {2011 IEEE Statistical Signal Processing Workshop (SSP)}, pages = {349--352}, publisher = {IEEE}, address = {Nice}, abstract = {Various practical problems in transportation research and routing in communication networks can be reduced to the computation of the best path that traverses a certain graph and visits a set of D specified destination nodes. Simple versions of this problem have received attention in the literature. Optimal solutions exist for the cases in which (a) D >; 1 and the graph is deterministic or (b) D = 1 and the graph is stochastic (and possibly time-dependent). Here, we address the general problem in which both D >; 1 and the costs of the edges in the graph are stochastic and time-varying. We tackle this complex global optimization problem by first converting it into an equivalent estimation problem and then computing a numerical solution using a sequential Monte Carlo algorithm. The advantage of the proposed technique over some standard methods (devised for graphs with time-invariant statistics) is illustrated by way of computer simulations.}, keywords = {Approximation algorithms, communication networks, Estimation, graph theory, Histograms, intelligent transportation, Monte Carlo algorithm, Monte Carlo methods, multiple destinations, optimisation, Optimization, random networks, route optimization, routing, Sequential Monte Carlo, Signal processing algorithms, stochastic graph, Stochastic processes, telecommunication network routing, time-varying graph, transportation routes}, pubstate = {published}, tppubtype = {inproceedings} } Various practical problems in transportation research and routing in communication networks can be reduced to the computation of the best path that traverses a certain graph and visits a set of D specified destination nodes. Simple versions of this problem have received attention in the literature. Optimal solutions exist for the cases in which (a) D >; 1 and the graph is deterministic or (b) D = 1 and the graph is stochastic (and possibly time-dependent). Here, we address the general problem in which both D >; 1 and the costs of the edges in the graph are stochastic and time-varying. We tackle this complex global optimization problem by first converting it into an equivalent estimation problem and then computing a numerical solution using a sequential Monte Carlo algorithm. The advantage of the proposed technique over some standard methods (devised for graphs with time-invariant statistics) is illustrated by way of computer simulations. |

Achutegui, Katrin; Miguez, Joaquin A Parallel Resampling Scheme and its Application to Distributed Particle Filtering in Wireless Networks Inproceedings 2011 4th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pp. 81–84, IEEE, San Juan, 2011, ISBN: 978-1-4577-2105-2. Abstract | Links | BibTeX | Tags: Approximation algorithms, Approximation methods, Artificial neural networks, distributed resampling, DRNA technique, Markov processes, nonproportional allocation algorithm, parallel resampling scheme, PF, quantization, Signal processing, Vectors, Wireless sensor network, Wireless Sensor Networks, WSN @inproceedings{Achutegui2011, title = {A Parallel Resampling Scheme and its Application to Distributed Particle Filtering in Wireless Networks}, author = {Katrin Achutegui and Joaquin Miguez}, url = {http://ieeexplore.ieee.org/articleDetails.jsp?arnumber=6136051}, isbn = {978-1-4577-2105-2}, year = {2011}, date = {2011-01-01}, booktitle = {2011 4th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)}, pages = {81--84}, publisher = {IEEE}, address = {San Juan}, abstract = {We address the design of a particle filter (PF) that can be implemented in a distributed manner over a network of wireless sensor nodes, each of them collecting their own local data. This is a problem that has received considerable attention lately and several methods based on consensus, the transmission of likelihood information, the truncation and/or the quantization of data have been proposed. However, all existing schemes suffer from limitations related either to the amount of required communications among the nodes or the accuracy of the filter outputs. In this work we propose a novel distributed PF that is built around the distributed resampling with non-proportional allocation (DRNA) algorithm. This scheme guarantees the properness of the particle approximations produced by the filter and has been shown to be both efficient and accurate when compared with centralized PFs. The standard DRNA technique, however, places stringent demands on the communications among nodes that turn out impractical for a typical wireless sensor network (WSN). In this paper we investigate how to reduce this communication load by using (i) a random model for the spread of data over the WSN and (ii) methods that enable the out-of-sequence processing of sensor observations. A simple numerical illustration of the performance of the new algorithm compared with a centralized PF is provided.}, keywords = {Approximation algorithms, Approximation methods, Artificial neural networks, distributed resampling, DRNA technique, Markov processes, nonproportional allocation algorithm, parallel resampling scheme, PF, quantization, Signal processing, Vectors, Wireless sensor network, Wireless Sensor Networks, WSN}, pubstate = {published}, tppubtype = {inproceedings} } We address the design of a particle filter (PF) that can be implemented in a distributed manner over a network of wireless sensor nodes, each of them collecting their own local data. This is a problem that has received considerable attention lately and several methods based on consensus, the transmission of likelihood information, the truncation and/or the quantization of data have been proposed. However, all existing schemes suffer from limitations related either to the amount of required communications among the nodes or the accuracy of the filter outputs. In this work we propose a novel distributed PF that is built around the distributed resampling with non-proportional allocation (DRNA) algorithm. This scheme guarantees the properness of the particle approximations produced by the filter and has been shown to be both efficient and accurate when compared with centralized PFs. The standard DRNA technique, however, places stringent demands on the communications among nodes that turn out impractical for a typical wireless sensor network (WSN). In this paper we investigate how to reduce this communication load by using (i) a random model for the spread of data over the WSN and (ii) methods that enable the out-of-sequence processing of sensor observations. A simple numerical illustration of the performance of the new algorithm compared with a centralized PF is provided. |