The CEO problem with inter-block memory

Victoria Kostina, Babak Hassibi

In the classic "CEO problem," a group of observers (the "agents") watch a source of information through noisy channels and send compressed reports to a central decoder (the "CEO"). The goal is for the CEO to form the best possible estimate of the source given the total bit-rate constraints.

While this problem is a cornerstone of distributed source coding, most existing solutions assume the source is independent and identically distributed (i.i.d.) over time. In this paper, Victoria Kostina and Babak Hassibi tackle a much more realistic and difficult version: The CEO problem with inter-block memory.

TL;DR

This paper extends the distributed source coding "CEO problem" to dynamic settings where encoders and decoders leverage memory of the past to track a source over time. The authors establish new theoretical bounds for achievable rates using directed information and provide an exact solution for Gauss-Markov sources, quantifying the efficiency lost when observers cannot coordinate.

What Problem Does This Paper Address?

In real-world tracking—like a network of sensors monitoring a moving vehicle—the source isn't a sequence of random, unrelated snapshots. It has temporal correlation; where the vehicle is now depends heavily on where it was a moment ago.

Standard information theory tools often struggle with this because they assume "one-shot" or memoryless communication. When you introduce memory, you also introduce causality constraints: encoders must compress data based only on what they’ve seen so far, and the decoder must estimate the current state without looking into the future.

The authors address the gap between classical distributed source coding and causal rate-distortion theory, specifically asking: What is the minimum bit-rate required to achieve a target estimation accuracy when both the source and the observers have memory?

Methods

The authors employ several sophisticated information-theoretic techniques:

  1. Directed Mutual Information: Unlike standard mutual information, directed information is specifically designed to account for the direction of time and causality. The authors use it to characterize the fundamental limits of information flow in this causal system.
  2. Berger-Tung Extensions: They extend the well-known Berger-Tung inner and outer bounds—originally developed for memoryless distributed coding—to the causal setting with inter-block memory.
  3. Stochastic Likelihood Coders (SLC): To prove their "achievability" results (the inner bound), they use SLCs. These are randomized encoders that mimic maximum-likelihood decoding, allowing for sharper non-asymptotic bounds than traditional joint-typicality methods.
  4. Channel Reversal: For the Gaussian case, the authors use a "reversal" trick. They transform the "forward" noisy observation channels into "backward" estimation channels, which makes the Minimum Mean Squared Error (MMSE) math significantly more tractable.

Datasets

Not discussed in the paper. As a theoretical work in information theory, the paper relies on mathematical models (specifically Gauss-Markov processes and Additive White Gaussian Noise channels) rather than empirical datasets.

Key Insights and Ideas

  • Memory is Only Useful if the Source has it: If the source is memoryless (i.i.d.), having memory at the encoders or decoders provides zero benefit. The "inter-block memory" only pays off when the source itself has temporal dynamics.
  • The "Isolation Penalty": There is a fundamental "rate loss" because the observers are isolated and cannot talk to each other. The paper quantifies this loss as being bounded by $(K-1)$ times the difference between the "remote" (where observers can coordinate) and "direct" rate-distortion functions.
  • Tightness in the Gaussian Case: While the Berger-Tung bounds are generally just approximations, the authors prove that for the quadratic Gaussian CEO problem with memory, these bounds are actually tight, meaning they've found the exact optimal sum-rate.
  • Waterfilling Suboptimality: In the memoryless CEO problem, "waterfilling" (allocating more bits to clearer channels) is optimal. Surprisingly, the authors show that with inter-block memory, standard waterfilling is actually suboptimal, though it remains a useful upper bound.

Key Results

  • The Causal Sum-Rate: The authors derived the first explicit formula for the minimum asymptotically achievable sum-rate ($R_{CEO}$) for a Gauss-Markov source observed through $K$ parallel AWGN channels.
  • Asymptotic Penalty: They showed that as the number of observers $K$ goes to infinity, the sum-rate does not converge to the "perfect" direct rate-distortion function. Instead, a persistent penalty remains because the encoders are forced to act independently.
  • General Coding Theorem: The paper provides a new non-asymptotic bound for blockwise-causal distributed lossy source coding, which serves as a foundation for future work in networked control and estimation.

Limitations and Future Work

  • I.I.D. Components: The current model assumes that while there is correlation between blocks, the components within a single block of length $n$ are i.i.d. The authors suggest that future work should explore correlation within the blocks themselves.
  • Vector State-Space Models: The primary solution provided is for scalar Gauss-Markov sources. Generalizing this to full vector state-space models ($X_{i+1} = AX_i + V_i$) is a logical next step for applications in complex robotics or aerospace systems.
  • Full Rate Region: This paper focuses on the sum-rate (the total bits from all encoders). Determining the full rate-distortion region—the specific trade-offs allowed between individual encoders—remains an open theoretical challenge.

Summary updated

Abstract

An $n$-dimensional source with memory is observed by $K$ isolated encoders via parallel channels, who compress their observations to transmit to the decoder via noiseless rate-constrained links while leveraging their memory of the past. At each time instant, the decoder receives $K$ new codewords from the observers, combines them with the past received codewords, and produces a minimum-distortion estimate of the latest block of $n$ source symbols. This scenario extends the classical one-shot CEO problem to multiple rounds of communication with communicators maintaining the memory of the past. We extend the Berger-Tung inner and outer bounds to the scenario with inter-block memory, showing that the minimum asymptotically (as $n \to \infty$) achievable sum rate required to achieve a target distortion is bounded by minimal directed mutual information problems. For the Gauss-Markov source observed via $K$ parallel AWGN channels, we show that the inner bound is tight and solve the corresponding minimal directed mutual information problem, thereby establishing the minimum asymptotically achievable sum rate. Finally, we explicitly bound the rate loss due to a lack of communication among the observers; that bound is attained with equality in the case of identical observation channels. The general coding theorem is proved via a new nonasymptotic bound that uses stochastic likelihood coders and whose asymptotic analysis yields an extension of the Berger-Tung inner bound to the causal setting. The analysis of the Gaussian case is facilitated by reversing the channels of the observers.
BibTeX
@article{kostina2019ceo,
  author = {Victoria Kostina and Babak Hassibi},
  title = {{The CEO problem with inter-block memory}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
}
Figure