TY - GEN

T1 - A topological view of estimation from noisy relative measurements

AU - Molavi, Pooya

AU - Jadbabaie, Ali

PY - 2011/9/29

Y1 - 2011/9/29

N2 - In this paper we study the problem of estimating the state of sensors in a sensor network from noisy pairwise relative measurements. The underlying sensor network is typically modeled by a graph whose edges correspond to pairwise relative measurements and nodes represent sensors. Using tools from algebraic topology and cohomology theory, we present a new model in which the higher order relations between measurements are captured as simplicial complexes. This allows us to address the fundamental tension between two conflicting goals: finding estimates that are close to obtained measurements, and at the same time are consistent around any sequence of pairwise measurements that form a cycle. By defining a measure of inconsistency around each cycle, we present a one-parameter family of algorithms that solves the estimation problem by identifying and removing the smallest fraction of measurements that make the estimates globally inconsistent. We demonstrate that the inconsistencies are due to topological obstructions and can be decomposed into local and global components that have interesting geometric interpretations. Furthermore, we show that the proposed algorithm is naturally distributed and will provably result in consistent estimates, and more importantly, recovers two sparse estimation algorithms as special cases.

AB - In this paper we study the problem of estimating the state of sensors in a sensor network from noisy pairwise relative measurements. The underlying sensor network is typically modeled by a graph whose edges correspond to pairwise relative measurements and nodes represent sensors. Using tools from algebraic topology and cohomology theory, we present a new model in which the higher order relations between measurements are captured as simplicial complexes. This allows us to address the fundamental tension between two conflicting goals: finding estimates that are close to obtained measurements, and at the same time are consistent around any sequence of pairwise measurements that form a cycle. By defining a measure of inconsistency around each cycle, we present a one-parameter family of algorithms that solves the estimation problem by identifying and removing the smallest fraction of measurements that make the estimates globally inconsistent. We demonstrate that the inconsistencies are due to topological obstructions and can be decomposed into local and global components that have interesting geometric interpretations. Furthermore, we show that the proposed algorithm is naturally distributed and will provably result in consistent estimates, and more importantly, recovers two sparse estimation algorithms as special cases.

UR - http://www.scopus.com/inward/record.url?scp=80053159559&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80053159559&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:80053159559

SN - 9781457700804

T3 - Proceedings of the American Control Conference

SP - 3615

EP - 3620

BT - Proceedings of the 2011 American Control Conference, ACC 2011

T2 - 2011 American Control Conference, ACC 2011

Y2 - 29 June 2011 through 1 July 2011

ER -