Gauss-Markov Source Tracking with Side Information: Lower Bounds

Omri Lev, Anatoly Khina

Abstract: We consider the problem of causal source coding and causal decoding of a Gauss--Markov source, where the decoder has causal access to a side-information signal. We define the information causal rate-distortion function with causal decoder side information and prove that it bounds from below its operational counterpart. We further explain how to adapt the result to the setting of control over communication channels.

Introduction

In the realm of real-time tracking and networked control, the ability to accurately estimate the state of a moving target under communication constraints is paramount. This paper, authored by Omri Lev and Anatoly Khina, addresses the fundamental limits of tracking a Gauss-Markov source when the receiver (decoder) has access to its own local sensor data, known as side information (SI). The core contribution is the derivation of a new, tighter lower bound for the "causal rate-distortion function" (CRDF), which characterizes the minimum bit rate required to achieve a specific tracking accuracy.

The Problem of Causal Side Information

Imagine a drone (the source) being tracked by a ground station (the decoder). The ground station receives compressed updates over a limited wireless link, but it also possesses a local radar that provides noisy, real-time measurements of the drone's position. In information theory, determining the absolute minimum number of bits the drone must transmit to maintain a certain tracking accuracy is defined by the Rate-Distortion Function.

System model for tracking a Gauss-Markov source with causal side information at the encoder and decoder.

The primary challenge in this scenario is causality. In real-time tracking, both the encoder and decoder can only utilize information from the past and present. Previous theoretical frameworks often relied on the "Wyner-Ziv" model, which assumes the decoder has non-causal access to the entire future of the side information. Applying these non-causal assumptions to causal tracking leads to overly optimistic bounds that are physically unattainable in real-time systems. This work aims to close that mathematical gap by accounting for the "causality tax."

Methodology and Theoretical Framework

To derive more realistic limits, the authors employ several advanced tools from information theory:

  • Directed Information (DI): Unlike standard Mutual Information, DI specifically accounts for the temporal flow of information, making it the appropriate metric for causal systems.
  • Information CRDF ($R_c^{dec}(D)$): The authors define a new optimization problem that characterizes the minimum rate specifically for cases where side information is available causally at the decoder.
  • Genie-Aided Analysis: To extend these results to control systems—where the tracker's output influences the source's future state—the authors utilize a theoretical "genie" to provide the encoder with additional information, simplifying the proof while maintaining a valid lower bound.
  • Test Channel Evaluation: The study compares standard Gaussian test channels against modulo-based (lattice-based) test channels to identify which strategies approach the theoretical limits more closely.

Key Insights and Results

The research yields several critical insights for communication engineering. Most importantly, it proves that causality is costly. Because the encoder does not know exactly what the decoder's local sensor is observing at any given moment, it cannot perfectly pre-subtract redundancy, making causal side information fundamentally less helpful than its non-causal counterpart.

Rate-distortion performance for different tracking scenarios and source parameters (λ=0 and λ=0.9).

Numerical simulations of synthetic Gauss-Markov processes validate these findings. As shown in the figures above, the new bound ($R_c^{dec}$) is mathematically proven to be strictly higher (tighter) than previous state-of-the-art bounds whenever the tracking rate is greater than zero. Specifically:

  1. Tighter Bounds: The gap between the new causal bound and the old Wyner-Ziv-style bounds (labeled "Two-Sided SI" in the plots) is significant, providing a more realistic "speed limit" for engineers.
  2. Modulo Superiority: The simulations demonstrate that modulo-based mapping strategies outperform the standard "Time-Sharing Gaussian" approach, particularly as the source becomes more predictable (higher $\lambda$).
  3. Settling Conjectures: The authors successfully settle a standing conjecture in the field, proving that previous bounds were strictly loose due to their failure to account for the fundamental constraints of causality.

Limitations and Future Directions

While this work provides a more accurate theoretical foundation, several challenges remain. Calculating the exact value of the new bound for any specific system involves a difficult non-convex optimization problem. Furthermore, the current analysis focuses on scalar (one-dimensional) sources, whereas real-world tracking typically involves multi-dimensional vectors (e.g., position, velocity, and acceleration). Future research will focus on extending these bounds to vector sources and designing practical coding algorithms that can reach these newly defined limits.

Summary updated

Abstract

We consider the problem of causal source coding and causal decoding of a Gauss--Markov source, where the decoder has causal access to a side-information signal. We define the information causal rate-distortion function with causal decoder side information and prove that it bounds from below its operational counterpart. We further explain how to adapt the result to the setting of control over communication channels.
BibTeX
@inproceedings{lev2020gauss,
  author = {Omri Lev and Anatoly Khina},
  title = {{Gauss-Markov Source Tracking with Side Information: Lower Bounds}},
  booktitle = {International Symposium on Information Theory and its Applications},
  year = {2020},
}
Figure