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)