A Research About Low-Complexity Message-Passing Algorithms For Dispersed Computation

Efficient Message-Passing Algorithms for Statistical Inference Problems in Dispersed Computation

Abstract

Central to many statistical inference problems is the computation ofsome quantities defined over variables that can be fruitfully modeled in termsof graphs. Examples of such quantities include marginal distributions overgraphical models and empirical average of observations over sensor networks.For practical purposes, distributed message-passing algorithms are well suitedto deal with such problems. In particular, the computation is broken down intopieces and distributed among different nodes. Following some localcomputations, the intermediate results are shared among neighboring nodes viathe so called messages. The process is repeated until the desired quantity is obtained. Thesedistributed inference algorithms have two primary aspects: statisticalproperties, in which characterize how mathematically sound an algorithm is, andcomputational complexity that describes the efficiency of a particularalgorithm. In this thesis, we propose low-complexity (efficient),message-passing algorithms as alternatives to some well-known inferenceproblems while providing rigorous mathematical analysis of their performances.These problems include the computation of the marginal distribution via beliefpropagation for discrete as well as continuous random variables, and thecomputation of the average of distributed observations in a noisy sensornetwork via gossip-type algorithms.