Multiterminal source coding with an entropy-based distortion measure

Thomas A. Courtade, Richard D. Wesel

Abstract

This paper addresses the long-standing open problem of lossy multiterminal source coding (MSC) by introducing a novel entropy-based distortion measure. Unlike traditional metrics such as mean squared error, this measure quantifies the "soft information" or remaining uncertainty about a source. The authors provide a complete characterization of the achievable rate-distortion region for two fundamental scenarios: joint distortion and one-sided distortion. The results reveal a fundamental symmetry where bits of allowed distortion can be traded one-for-one with transmission rate, effectively reducing complex lossy problems to well-understood lossless frameworks.

Introduction: The Multiterminal Source Coding Problem

In information theory, Multiterminal Source Coding (MSC) involves multiple encoders that observe correlated data—such as sensors in a distributed network—and transmit compressed information to a central decoder. While the "lossless" case was solved by the Slepian-Wolf theorem in 1973, the "lossy" case, where some distortion is permitted to save bandwidth, has remained a major challenge for over four decades.

Standard multiterminal source coding architecture with two encoders and a joint decoder.

The primary difficulty in solving the lossy MSC problem is that common distortion measures do not interact cleanly with the entropy of the sources. This paper circumvents this issue by proposing a specific distortion measure that makes the problem mathematically tractable.

Methodology: Entropy-Based Distortion

The authors propose an entropy-based distortion measure that quantifies uncertainty rather than physical distance. Specifically, distortion is defined as: $$d(x, \hat{v}) = \log \left( \frac{1}{\hat{v}(x)} \right)$$ where $\hat{v}(x)$ represents the probability the decoder assigns to the source symbol $x$.

A key mathematical lemma established in the paper shows that the minimum expected distortion under this measure is exactly equal to the conditional entropy. This allows "distortion" to be treated as a budget of bits. By leveraging standard information-theoretic techniques like random binning and time-sharing, the authors map these lossy problems onto established lossless frameworks. As a theoretical work, these results are derived for any discrete memoryless source distribution $p(x, y)$ without the need for empirical datasets.

Key Results: Characterizing Rate-Distortion Regions

The paper provides a full characterization of the achievable rate-distortion regions for two primary scenarios: Joint Distortion (JD) and X-Distortion (XD).

The two distortion scenarios addressed: Joint Distortion (JD) and one-sided X-Distortion (XD).

1. Joint Distortion (JD)

In this scenario, both sources $X$ and $Y$ must be recovered such that their joint uncertainty is $\le D$. The achievable region is defined by:

  • $R_x + \delta_x \ge H(X|Y)$
  • $R_y + \delta_y \ge H(Y|X)$
  • $R_x + R_y + D \ge H(X, Y)$ where $\delta_x$ and $\delta_y$ are marginal distortions that sum to $D$. This region is essentially a "shifted" version of the Slepian-Wolf region; allowing $D$ bits of joint distortion reduces the total required rate $R_x + R_y$ by exactly $D$.

2. X-Distortion (XD)

In the one-sided case, only source $X$ has a distortion constraint $D_x$, while $Y$ serves as side information. The region is defined by:

  • $R_x + D_x \ge H(X|U)$
  • $R_y \ge I(Y;U)$ where $U$ is an auxiliary variable capturing the relationship between the sources. This corresponds directly to the Ahlswede-Körner-Wyner problem.

Insights and Discussion

The most significant insight is the conceptualization of distortion as "negative rate." Under the entropy-based measure, every bit of tolerated distortion reduces the transmission requirement by one bit. Furthermore, this "soft" measure yields the same rate-distortion trade-offs as a simpler "erasure" distortion measure, suggesting a deep underlying structure in how uncertainty behaves in distributed networks.

Conclusion and Future Work

While the entropy-based measure is mathematically elegant and natural for applications involving log-likelihoods or soft-decision decoding, its primary limitation is its lack of direct translation to common metrics like Mean Squared Error (MSE). However, this work serves as a vital proof-of-concept, demonstrating that complex lossy multiterminal problems can be simplified if the distortion measure is chosen to align with the information-theoretic properties of the sources. Future research may extend these findings to more complex network topologies with more than two sources.

Summary updated

BibTeX
@inproceedings{courtade2011multiterminal,
  author = {Thomas A. Courtade and Richard D. Wesel},
  title = {{Multiterminal source coding with an entropy-based distortion measure}},
  booktitle = {ISIT},
  year = {2011},
  doi = {10.1109/isit.2011.6033913},
}
Figure