Optimal estimation with limited measurements

O.c. Imer, Tamer BaşarInternational Journal of Systems Control and Communications 2010 · DOI

TL;DR

This paper tackles the challenge of estimating a dynamic system's state when an "observer" can only transmit a limited number of measurements to an "estimator." They develop a framework for jointly optimizing the observer's transmission strategy and the estimator's state estimation policy to minimize average error, offering significant improvements over scenarios with no observation constraints.

What Problem Does This Paper Address?

Imagine a team of two agents trying to understand a changing environment (a stochastic process). One agent (the observer) can see the environment directly, but can only send a limited number of "snapshots" (measurements) to the other agent (the estimator). The estimator's job is to guess the environment's state at each moment, but it only has access to the limited snapshots sent by the observer. The core problem is: how should the observer decide when to send a snapshot, and how should the estimator use these snapshots to make the best possible guess about the environment's state, given that the observer's transmissions are restricted? This is crucial in applications like wireless sensor networks where power or bandwidth limitations restrict how often sensors can communicate.

Methods

The paper frames this problem within a communication system context, where the observer acts as an encoder and the estimator as a decoder. They use dynamic programming to derive optimal policies. For the estimator, the optimal strategy is to compute the conditional expectation of the state given the available information (for mean-square error) or the maximum a posteriori probability (MAP) estimate (for probability of error).

The real novelty lies in optimizing the observer's strategy. They show that the observer's decision to transmit depends on the current measurement and the remaining transmission opportunities. For the mean-square error, they derive a recursive formula for the optimal estimation error and restrict the observer's transmission decision to symmetric intervals. For the probability of error, they find that the optimal strategy is to transmit all outcomes except the most likely one. They also extend the analysis to Gauss-Markov processes and noisy measurements.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and illustrative examples rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Observer-Estimator Trade-off: The paper highlights that the observer's limited transmission capability creates a fundamental trade-off. The observer must strategically choose which measurements to send to maximize the estimator's performance, rather than simply sending everything possible.
  • Information is Key: Even when the observer doesn't transmit a measurement (e.g., by sending a "no transmission" signal), this itself can be valuable information for the estimator, especially if the observer can convey a 1-bit signal indicating whether a transmission occurred.
  • Dynamic Programming is Powerful: The problem is naturally solved using dynamic programming, breaking down the N-stage problem into smaller, sequential decisions.
  • Interval-Based Decisions for MSE: For mean-square error, restricting the observer's decision to transmit or not transmit based on whether the measurement falls within a symmetric interval around the expected value proves to be an effective strategy.
  • Transmitting the "Unlikely": For probability of error, the optimal strategy is counter-intuitive: transmit all outcomes except the most probable one. This suggests that the observer should focus on providing information about the "surprising" events.

Key Results

  • The paper provides a formal framework for optimal estimation with limited measurements, defining the problem and deriving optimal estimator policies.
  • For the mean-square error criterion, they derive a recursive formula for the optimal estimation error and propose an optimal transmission policy based on symmetric intervals.
  • For the probability of error criterion, they identify an optimal policy that involves transmitting all but the most likely outcomes.
  • Illustrative examples show significant improvements: in one case, a 48% improvement in estimation error is achieved by using an optimal observer. In another, a cumulative estimation error of 20 can be achieved with 34 transmissions, a 58% improvement over a scenario with no observer.

Limitations and Future Work

  • Computational Complexity: The derived recursions for optimal policies are offline computations and can become computationally intensive for large horizons (N) and transmission limits (M).
  • Specific Interval Restriction: The restriction to symmetric intervals for the mean-square error case is a simplification; the true optimal interval might not always be symmetric.
  • Future Work: The authors suggest exploring the Gauss-Markov case with noisy measurements and extending the framework to more general communication constraints and performance criteria. The paper also hints at the potential for more complex observer-estimator interactions and the impact of channel noise.

Summary updated

Abstract

This paper introduces a sequential estimation problem with two decision makers, or agents, who work as members of a team. One of the agents sits at an observation post, and makes sequential observations about the state of an underlying stochastic process for a fixed period of time. The observer agent upon observing the process makes a decision as to whether or not to disclose some information about the process to the other agent who acts as an estimator. The estimator agent sequentially estimates the state of the process. The agents have the common objective of minimising a performance criterion with the constraint that the observer agent may only act a limited number of times.
BibTeX
@article{imer2010optimal,
  author = {O.C. Imer and Tamer Başar},
  title = {{Optimal estimation with limited measurements}},
  journal = {International Journal of Systems Control and Communications},
  year = {2010},
  doi = {10.1504/ijscc.2010.031156},
}
Figure