Moderate Deviations Asymptotics for Streaming Compression of Correlated Sources

Lin Zhou, Vincent Y. F. Tan, Mehul Motani

Abstract

This paper investigates the theoretical limits of streaming compression for correlated data sources, known as streaming Slepian-Wolf coding, within the moderate deviations regime. The study demonstrates that by permitting a decoding delay of $T$ blocks, the system's reliability—quantified by the moderate deviations constant—can be improved by a factor of at least $T$ relative to traditional non-streaming block coding. The authors establish this result through a novel encoding and decoding framework involving truncated memory and suffix entropy analysis.

Introduction

In modern communication systems, such as multi-view video coding or distributed sensor networks, data is often generated sequentially and exhibits high spatial correlation. Traditional Slepian-Wolf (SW) coding theory provides the fundamental limits for compressing such correlated sources independently, but it typically assumes data is processed in isolated, fixed-length blocks. This paper extends these concepts to a streaming setup, where encoders process data incrementally and the decoder reconstructs the stream with a fixed delay of $T$ blocks.

The analysis is conducted in the moderate deviations regime, which serves as a bridge between the large deviations (error exponent) regime and the central limit (second-order) regime. In this regime, the transmission rate approaches the Shannon limit more slowly than $1/\sqrt{n}$, resulting in a sub-exponential decay of the error probability. The primary objective is to determine how a block delay $T$ influences the sub-exponential decay rate, or the moderate deviations constant, in a multi-terminal streaming environment.

System Model

The streaming Slepian-Wolf setup involves two correlated sources, $\mathbf{X}$ and $\mathbf{Y}$, that produce sequences of data blocks over time. As shown in Figure 1, encoders $f_i$ and $g_i$ generate codewords based on the current and previous source blocks. The decoder $\phi_j$ then attempts to estimate the $j$-th source blocks $(\hat{\mathbf{X}}_j, \hat{\mathbf{Y}}_j)$ after observing codewords up to time $j+T$.

System model for streaming Slepian-Wolf coding with a decoding delay of $T$ blocks.

This delay $T$ is a critical parameter, representing the latency the system can tolerate to improve reconstruction accuracy.

Methodology

To derive achievable bounds for the moderate deviations constant, the authors introduce a specialized coding scheme characterized by two main components:

  1. Truncated Memory Encoding: Standard streaming tree codes often require encoders to maintain an infinite memory of past blocks. However, in multi-terminal settings, this can lead to unbounded error accumulation. The authors implement a sliding buffer (truncated history) between a minimum $\Omega$ and maximum $\Psi$ blocks. This truncation ensures that the mathematical upper bound on error probability remains finite and manageable.
  2. Minimum Weighted Empirical Suffix Entropy Decoding: The decoding rule is based on the empirical entropy of the suffixes of the received sequences. By adapting this rule for block-wise moderate deviations, the authors can effectively identify and mitigate dominant error events.

The proof involves random binning techniques and a Taylor expansion of the error exponents near the first-order fundamental rate limits.

Key Insights and Results

The central finding of the research is the multiplicative power of delay. A decoding delay of $T$ blocks provides a reliability boost of at least $T$ times the moderate deviations constant of a standard block-coding setup.

The Slepian-Wolf rate region and various approach directions to the boundary.

Furthermore, the performance gain is sensitive to the direction of approach to the Slepian-Wolf rate region boundary. As illustrated in Figure 2, the rate region is defined by the joint and conditional entropies of the sources. The authors prove that for any correlated source, there exists a set of directions (slopes) in the $(R_X, R_Y)$ plane for which the $T$-fold reliability gain is guaranteed.

Key results include:

  • Main Theorem: Establishing the achievable moderate deviations constant for streaming Slepian-Wolf coding and proving the $\ge T$ multiplicative gain.
  • Point-to-Point Specialization: Showing that the same reliability enhancement applies to standard lossless source coding with or without side information.
  • Asymmetric Delays: In scenarios where sources have different delay requirements ($T_1, T_2$), the reliability gain is limited by the stricter requirement, resulting in a multiplier of $\min(T_1, T_2)$.

Conclusion

This work provides a rigorous theoretical foundation for understanding the benefits of delay in streaming multi-terminal source coding. While the paper successfully establishes an achievability result, the derivation of a matching converse remains an open challenge. Future research may explore extending this framework to lossy compression and more complex network topologies.

Summary updated

BibTeX
@article{zhou2018moderate,
  author = {Lin Zhou and Vincent Y. F. Tan and Mehul Motani},
  title = {{Moderate Deviations Asymptotics for Streaming Compression of Correlated Sources}},
  journal = {IEEE Trans. Information Theory},
  year = {2018},
  url = {https://openreview.net/forum?id=zeL_e5ra9P},
}
Figure