 Main
LowComplexity MessagePassing Algorithms for Distributed Computation
 Noorshams, Nima
 Advisor(s): Wainwright, Martin J.
Abstract
Central to many statistical inference problems is the computation of
some quantities defined over variables that can be fruitfully modeled
in terms of graphs. Examples of such quantities include marginal
distributions over graphical models and empirical average of
observations over sensor networks. For practical purposes, distributed
messagepassing algorithms are well suited to deal with such
problems. In particular, the computation is broken down into pieces
and distributed among different nodes. Following some local
computations, the intermediate results are shared among neighboring
nodes via the so called messages. The process is repeated until the
desired quantity is obtained. These distributed inference algorithms
have two primary aspects: statistical properties, in which
characterize how mathematically sound an algorithm is, and
computational complexity that describes the efficiency of a particular
algorithm. In this thesis, we propose lowcomplexity (efficient),
messagepassing algorithms as alternatives to some well known
inference problems while providing rigorous mathematical analysis of
their performances. These problems include the computation of the
marginal distribution via belief propagation for discrete as well as
continuous random variables, and the computation of the average of
distributed observations in a noisy sensor network via gossiptype
algorithms.
Main Content
Enter the password to open this PDF file:













