On the Sub-optimality of Single-Letter Coding over Networks

Farhad Shirani Chaharsooghi, S. Sandeep PradhanIEEE Trans. Information Theory 2017 · OpenReview

TL;DR

This paper introduces a new theoretical framework to analyze the correlation between outputs of coding functions, particularly in network communication scenarios. It reveals that standard "single-letter" coding schemes, while optimal in simple point-to-point settings, are surprisingly sub-optimal in more complex network scenarios due to their inability to preserve correlation effectively.

What Problem Does This Paper Address?

The paper tackles a fundamental question in information theory: how to achieve optimal communication over networks where multiple sources or users are involved. Traditionally, in point-to-point communication (like sending a file from one computer to another), longer block lengths (processing more data at once) lead to better compression and error correction. This is often achieved using "single-letter" coding schemes, which are designed based on the properties of individual symbols.

However, the authors observe that in multi-terminal communication (e.g., multiple sensors sending data to a central processor, or multiple devices communicating with each other), simply making block lengths very long doesn't guarantee optimal performance. The challenge is that in networks, the correlation between the outputs of different encoders is often crucial for cooperation and efficient information sharing. The paper investigates why these standard single-letter coding schemes, which are asymptotically optimal in point-to-point settings, fail to preserve this essential correlation in network scenarios, leading to sub-optimality.

Methods

The core of the paper's contribution lies in developing a new mathematical framework to analyze Boolean functions (which are fundamental building blocks in coding) and their correlation properties.

  • Effective-Length and Dependency Spectrum: They introduce the concept of "effective-length" for Boolean functions, which quantifies how many input elements are truly necessary to determine an output. For more general functions, they develop a "dependency spectrum," a generalization of effective-length, which captures how different subsets of inputs influence the output.
  • Real Transformations and Decomposition: Boolean functions are transformed into real-valued functions in a Hilbert space. This allows them to use powerful tools from functional analysis. They decompose these real-valued functions into additive components, each associated with a specific "letter" or block size.
  • Correlation Bounds: The paper derives new upper bounds on the correlation between the outputs of two Boolean functions. These bounds are expressed in terms of the dependency spectrum of the functions.
  • Analysis of Single-Letter Coding Ensembles (SLCEs): They identify a class of coding ensembles, termed SLCEs, that are commonly used in various multi-terminal communication schemes (like Shannon's source coding, Berger-Tung, etc.). They show that these SLCEs tend to produce encoding functions with high effective-lengths or variance concentrated on single-letter components, which are inefficient at preserving correlation.
  • Discontinuity in Performance: A key finding is that the correlation-preserving capabilities of SLCEs exhibit a discontinuity with respect to input distribution. This discontinuity is shown to be the root cause of their sub-optimality in certain network communication problems.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on mathematical properties of coding functions and information theoretic concepts, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Effective-Length Matters More Than Block-Length in Networks: While long block-lengths are good for point-to-point communication, the effective-length of coding functions (how many inputs influence an output) is critical for correlation in networks.
  • Single-Letter Schemes Struggle with Correlation: Standard single-letter coding schemes, by their nature, tend to produce outputs that are less correlated than expected, especially when dealing with highly correlated inputs. This is a fundamental limitation.
  • Discontinuity is the Culprit: The sub-optimality of SLCEs in network settings isn't a gradual performance degradation; it's a sharp discontinuity in their ability to preserve correlation, stemming from their construction.
  • New Mathematical Tools for Boolean Functions: The development of the "dependency spectrum" and the real-valued decomposition of Boolean functions provides a powerful new lens for analyzing their properties.

Key Results

  • A new upper bound on the correlation between outputs of arbitrary Boolean functions, dependent on their "dependency spectrum."
  • Characterization of Single-Letter Coding Ensembles (SLCEs) and proof that they produce encoding functions inefficient at preserving correlation.
  • Demonstration that SLCEs lead to sub-optimal performance in specific multi-terminal communication problems, such as transmission of correlated sources over interference and multiple access channels.
  • Theoretical results showing that for optimal correlation preservation in certain network settings, encoding functions must have bounded effective-lengths, not asymptotically large ones.

Limitations and Future Work

  • Focus on Binary: While the paper mentions generalization, the core analysis and examples often focus on binary inputs and outputs.
  • Theoretical Framework: The paper provides a theoretical framework and bounds. Applying these to specific practical systems might require further work.
  • New Applications: The authors suggest that the derived bounds and analytical tools could find applications in security, control, and information theory beyond the scope of this paper.
  • Understanding the Discontinuity: Further exploration of the nature and implications of the identified discontinuity in correlation preservation could lead to new coding strategies.

Summary updated

Abstract

In this paper, we establish a new bound tying together the effective length and the maximum correlation between the outputs of an arbitrary pair of Boolean functions which operate on two sequences of correlated random variables. We derive a new upper bound on the correlation between the outputs of these functions. The upper bound may find applications in problems in many areas which deal with common information. We build upon Witsenhausen's result on maximum correlation. The present upper bound takes into account the effective length of the Boolean functions in characterizing the correlation. We use the new bound to characterize the communication-cooperation tradeoff in multi-terminal communications. We investigate binary block-codes (BBC). A BBC is defined as a vector of Boolean functions. We consider an ensemble of BBCs which is randomly generated using single-letter distributions. We characterize the vector of dependency spectrums of these BBCs. We use this vector to bound the correlation between the outputs of two distributed BBCs. Finally, the upper bound is used to show that the large blocklength single-letter coding schemes studied in the literature are sub-optimal in various multi-terminal communication settings.
BibTeX
@article{chaharsooghi2017sub,
  author = {Farhad Shirani Chaharsooghi and S. Sandeep Pradhan},
  title = {{On the Sub-optimality of Single-Letter Coding over Networks}},
  journal = {IEEE Trans. Information Theory},
  year = {2017},
  url = {https://openreview.net/forum?id=K31pglI3AY},
}
Figure