**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