The Embedded Triangles Algorithm for Distributed Estimation in Sensor Networks
Baraniuk, Richard G.
Hidden Markov Models; distributed estimation; block Jacobi; graphical models
We propose a new iterative distributed estimation algorithm for Gaussian hidden Markov graphical models with loops. We decompose a loopy graph into a number of linked <i>embedded triangles</i> and then apply a parallel block-Jacobi iteration comprising local linear minimum mean-square-error estimation on each triangle (involving a simple 3 × 3 matrix inverse computation) followed by an information exchange between neighboring nodes and triangles. A simulation study demonstrates that the algorithm converges extremely rapidly, outperforming a number of existing algorithms. Embedded triangles are simple, local, scalable, fault-tolerant, and energy-efficient, and thus ideally suited for wireless sensor networks.