Series in Signal and Information Processing, Vol. 19
edited by Hans-Andrea Loeliger

Junli Hu
On Gaussian Approximations in Message
Passing Algorithms with Application to Equalization

1. Auflage/1^st edition 2008, VIII, 104 Seiten/pages, € 64,00.
ISBN 3-86628-212-5, 978-3-86628-212-4

Data estimation appears in many areas of the signal processing: digital communication, data extraction in biomedical applications, parameter estimation and tracking in control systems, and data save and read on magnetic storage devices. Depending on the system model and estimation criteria, we use different algorithms or their combinations for this challenging task.

Based on a graphical model, the factor graphs, we initiate the discussionby addressing the data estimation in digital communication, which is also known as equalization. We generalize the discrete-time system model, used in the communication to other applications by recognizing that we can often describe a data source by a sequence of discrete valued, e.g. binary, random variable. This sequence is sent through a discretetime channel model and at the channel output, we get a sequence of observations which is corrupted by an additive white Gaussian noise process. The equalization means, given the observation and the system model, including the knowledge on the stochastic processes of the input source and the noise at the output, we estimate the input sequence.

In the factor graph notation, we describe two well-known algorithms: the BCJR and the Kalman filtering or LMMSE (linear minimum mean squared error) algorithms. The BCJR algorithm delivers the maximum a-posteriori (MAP) estimation, which is the optimum for the above system setting. However, its exponential computational complexity is prohibitive for many applications, when the alphabet size of the discrete input source and/or the channel order is large. The LMMSE algorithm does not give the exact MAP estimation for the discrete data input. The equalization result, expressed in the error percentage of the estimated symbol, has usually a huge gap to that by the BCJR algorithm. The complexity of the LMMSE estimation is cubic in the channel order. Therefore, it is widely used in many applications.

As one of the main contributions, we propose a Gaussian approximation for a discrete random variable. This is inspired by the assumed density filtering (ADF) and the expectation propagation (EP), both discussed by Th. Minka in his thesis. We apply this new Gaussian approximation to the Kalman filtering and get an iterative scheme. We can show that this iterative Kalman filter delivers a much better result than the pure LMMSE solution, when the input data sequence is uncoded. The complexity remains the cubic in the channel order. In some uncoded cases, it almost close the gap of the result to the one by the BCJR algorithm. For coded input data, this new approximation method does not seem to help much. Therefore, it is suitable to some applications, e.g., some biomedical applications, where we have only prior knowledge over the input stochastic process. To applications in the communication, where the input data are mostly coded, this new approximation is not very interesting.

In another contribution, we study the multiplier (scalar product) node in a factor graph. We propose two Gaussian approximations: one for the forward message of the scalar output variable, the other for the backward message of one of the input vectors. The approximation of the backward message is compared with the sum-product message and the traditional expectation maximization (EM) approximation. The Gaussian approximation of the forward message is compared with the true distribution of the output random variable experimentally.

Keywords: Gaussian Approximation, Message Passing Algorithm, Equalization, Kalman Filtering.

Direkt bestellen bei / to order directly from: Hartung.Gorre@t-online.de

Reihe "Series in Signal and Information Processing" im Hartung-Gorre Verlag