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

Justin Dauwels
On Graphical Models for
Communications and Machine Learning:
Algorithms, Bounds, and Analog Implementation.

1. Auflage/1^st edition 2006, XXVIII, 492 Seiten/pages, € 64,00. ISBN 3-86628-080-7

This dissertation is about a specific problem and about general methods. The specific problem is carrier-phase synchronization, which appears in the context of digital communications. The generalmethods are messagepassing algorithms operating on graphical models, in particular, factor graphs. We consider applications of such algorithms in the context of statistical inference (as in communications, signal processing, and machine learning), statistics, information theory, and the theory of dynamical systems (such as analog electronic circuits).

The primary motivation for this work was (1) to analyze the degradation of digital communications systems due to oscillator non-idealities; (2) the development of synchronization algorithms that minimize this performance degradation. Clocks are ubiquitous in digital communications systems; real-life clocks are noisy, i.e., their signals are not perfectly periodic, which often leads to a significant degradation of the performance of communications systems.

In the early days of communications, this source of degradation was only of secondary concern. Communications systems used to operate far from the ultimate performance bound, i.e., channel capacity. The main concern was therefore to develop error-correcting techniques that could close the gap between the performance of practical communications systems and channel capacity. With the recent advent of iterative decoding techniques, communications systems nowadays most often operate close to the ultimate performance limits; issues such as synchronization, which were earlier only of secondary importance, have now become the mayor (remaining) bottlenecks in the design of communications systems.

In this dissertation, we focus on carrier-phase synchronization, i.e., the alignment of the phase of the local oscillator in the receiver to the phase of the incoming carrier. The questions we address are:

a) Which physical mechanisms are responsible for phase noise? How can phase noise be modeled?

b) How can carrier-phase estimation algorithms systematically be derived?

c) What are the ultimate limits for communication over channels with phase noise? In particular:

i) How much does the information rate of a communications channel decrease due to phase noise?

ii) How well can the (noisy) carrier phase be estimated?

In contrast to earlier and parallel work, our aim is not the design and optimization of fully operating communications systems. In this thesis, various tools are developed that lead (or may lead) to an answer to the above questions (and many other related questions).

We give a detailed analysis of phase noise in free-running clocks and PLLs (Question 1). We propose a simple intuitive model for phase noise in free-running oscillators. We describe two simple models for passband communications channels. The models take phase o_sets into account between the received carrier and the local carrier in the receiver, but disregard timing o_sets. In the first model, the phase is constant, in the second, the phase performs a random walk. We investigate under which conditions the two models are valid. Most methods of this thesis will be illustrated by means of both channel models.

Most methods we propose in this dissertation are based on graphical models, more precisely, factor graphs. Factor graphs are used to visualize the structure of the system at hand. They represent the factorization of multivariate functions. Each edge in the graph corresponds to a variable, each node corresponds to a factor. Factor graphs can represent any function, in particular, probabilistic models, error-correcting codes, block diagrams and other common models in communications, signal processing and beyond.

We show how factor graphs can be used as a tool to develop practical estimation and detection algorithms. Our techniques can be applied to model-based signal processing (e.g., phase estimation) and machine learning. In particular, we formulate several standard signal-processing and machine-learning algorithms as message passing on factor graphs, e.g., particle methods, gradient methods, decision-based methods, and expectation maximization. In all those algorithms, local rules are applied at the nodes in a factor graph. In other words, the (global) estimation and detection problem is tackled by a divide-and-conquer strategy: the global computation is carried out by multiple (simple) local computations.

The local message-update rules may be used as building blocks for novel estimation and detection algorithms. By listing the possible update rules at each node in the factor graph, one can systematically explore novel algorithms. We demonstrate this idea by deriving phase estimation algorithms for the constant-phase model and the random-walk phase model (Question 2). We also show how the back-propagation algorithm for the training of feed-forward neural networks follows by applying generic message-passing rules. We elaborate on the computation of kernels in the light of message passing on factor graphs.

We demonstrate how message-passing algorithms for inference can be implemented as dynamical systems, in particular, as clock-free analog electronic circuits. Those systems operate in continuous time, and do not require a digital clock; therefore, they circumvent the problem of timing synchronization.

We present a numerical algorithm to compute the information rate of continuous channels with memory (Question 3.a). The algorithm is an extension of the methods proposed earlier for discrete channels with memory. Also here, factor graphs and the summary-propagation algorithm are key ingredients. We apply the method to the random-walk phase model. The algorithms we propose for computing Cram´er-Raotype bounds open the door to exciting applications of information geometry, such as (1) natural-gradient-based algorithms; (2) the computation of Fisher kernels.

We propose a numerical algorithm for computing the capacity (or lower bounds on capacity) of continuous memoryless channels (Question 3.a). We present numerical results for the Gaussian channel with averagepower and/or peak-power constraints. We outline how the algorithm can be extended to continuous channels with memory (e.g., channels with phase noise) by means of message-passing techniques. We propose message-passing algorithms to compute Cram´er-Rao-type bounds. Cram´er-Rao-type bounds are lower bounds on the minimum mean square estimation error; the bounds may be used to asses the performance of practical (message-passing) estimation algorithms, in particular, our phase-estimation algorithms (Question 3.b). The algorithms we propose for computing Cram´er-Rao-type bounds open the door to exciting applications of information geometry, such as (1) natural-gradientbased algorithms; (2) the computation of Fisher kernels.

Keywords: graphical models, summary-propagation, belief propagation, message passing, expectation maximization, EM, steepest descent, particle filter, MCMC, particle methods, Gibbs sampling, importance sampling, decision-based estimation, iterative conditional modes, ICM, carrier phase estimation, phase noise, clock jitter, synchronization, Blahut-Arimoto algorithm, information rate, channel capacity, Cram´er-Rao bound, informationmatrix, kernel methods, Fisher kernel, product kernel, probabilistic kernel, neural networks, back-propagation algorithm, analog electrical circuits, linear feedback shift register, LFSR.

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

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