On Graphical Models for
Communications and Machine Learning:
Algorithms, Bounds, and Analog Implementation
PhD. Thesis, Justin Dauwels
Final draft PDF file, 4.859 kB.
Slides of the defense PDF file, 4.212kB.
Abstract
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 general methods are
message-passing 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:
1. Which physical mechanisms are responsible for phase noise? How can phase noise be modeled?
2. How can carrier-phase estimation algorithms systematically be derived?
3. What are the
ultimate limits for communication over channels with phase noise?
In particular:
a. How much does the information rate of a communications channel decrease due to phase noise?
b. 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 offsets into account
between the received carrier and the local carrier in the receiver, but
disregard timing offsets. 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 on a suitable factor graph. We elaborate on the
computation of kernels in the light of message passing on factor graphs.
We demonstrate how
message-passing algorithms for inference (in particular,
PN-synchronization) 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.
A numerical algorithm is proposed 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
average-power 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ér-Rao-type
bounds. Cramér-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ér-Rao-type bounds open the
door to exciting applications of information geometry, such as (1)
natural-gradient-based algorithms; (2) the computation of Fisher
kernels.
Defense
Thursday 1st of December 2005
Time: 2pm
Place: ETZ E81
Slides of the
defense. PDF file, 4.212kB.
Examiners
Prof. Dr. Hans-Andrea Loeliger (ETH Zurich, Institute for Signal and Information Processing)
Prof. Dr. Shun-ichi Amari (RIKEN, Brain Science Institute, Wako-shi, Japan)
Prof. Dr. Marc Moeneclaey (Digital Communications Lab, Gent University, Gent, Belgium)
Dr. Jonathan Yedidia (Mitsubishi Electrics Research Lab, Cambridge, MA, US)