Estimation from Relative Measurements: Electrical Analogy and Large Graphs

Abstract

We examine the problem of estimating vector-valued variables from noisy measurements of the difference between certain pairs of them. This problem, which is naturally posed in terms of a measurement graph, arises in applications such as sensor network localization, time synchronization, and motion consensus. We obtain a characterization on the minimum possible covariance of the estimation error when an arbitrarily large number of measurements are available. This covariance is shown to be equal to a matrix-valued effective resistance in an infinite electrical network. Covariance in large finite graphs converges to this effective resistance as the size of the graphs increases. This convergence result provides the formal justification for regarding large finite graphs as infinite graphs, which can be exploited to determine scaling laws for the estimation error in large finite graphs. Furthermore, these results indicate that in large networks, estimation algorithms that use small subsets of all the available measurements can still obtain accurate estimates.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 12, 2007
Accession Number
ADA473862

Entities

People

  • João P. Hespanha
  • Prabir Barooah

Organizations

  • University of California, Santa Barbara

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Convergence
  • Covariance
  • Detectors
  • Electrical Networks
  • Equations
  • Estimators
  • Hilbert Space
  • Measurement
  • Networks
  • Resistance
  • Scaling Laws
  • Sensor Networks
  • Statistical Algorithms
  • Two Dimensional
  • Vector Spaces

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Neural Network Machine Learning.