Rate-Distortion Function for a Heegard-Berger Problem with Two Sources and Degraded Reconstruction sets

Meryem Benammar, Abdellatif Zaidi

Abstract: In this work, we investigate an instance of the Heegard-Berger problem with two sources and arbitrarily correlated side information sequences at two decoders, in which the reconstruction sets at the decoders are degraded. Specifically, two sources are to be encoded in a manner that one of the two is reproduced losslessly by both decoders, and the other is reproduced to within some prescribed distortion level at one of the two decoders. We establish a single-letter characterization of the rate-distortion function for this model. The investigation of this result in some special cases also sheds light on the utility of joint compression of the two sources. Furthermore, we also generalize our result to the setting in which the source component that is to be recovered by both users is reconstructed in a lossy fashion, under the requirement that all terminals (i.e., the encoder and both decoders) can share an exact copy of the compressed version of this source component, i.e., a common encoder-decoders reconstruction constraint. For this model as well, we establish a single-letter characterization of the associated rate-distortion function.

Introduction

In information theory, the Heegard-Berger (HB) problem explores how to transmit a source to multiple decoders, each equipped with its own side information. Imagine a server broadcasting a video stream to two phones: Phone A has a weak signal (poor side info), while Phone B has a cached version of the video (strong side info). How do you compress the stream to satisfy both?

Most existing solutions assume "degraded side information," where one user's local data is strictly better than the other's. This paper addresses a more realistic and complex gap by considering arbitrary correlation. What if the side information at the two decoders isn't "ordered"? (e.g., User 1 knows about the weather, while User 2 knows about traffic). Furthermore, the authors introduce degraded reconstruction sets, where User 1 needs to reconstruct Source $S_1$ (lossily) and Source $S_2$ (losslessly), while User 2 only needs Source $S_2$ (losslessly).

Problem Formulation

The core of the research lies in finding the Rate-Distortion Function: the absolute minimum number of bits required to satisfy these specific, mismatched requirements. The system model involves a source encoder that processes two sources, $S_1^n$ and $S_2^n$, and outputs a message $W$ of rate $R$. This message is sent to two decoders.

System model for the Heegard-Berger problem with two sources and degraded reconstruction sets.

As shown in the figure above, Decoder 1 utilizes the message $W$ and its local side information $Y_1^n$ to produce estimates $\hat{S}_1^n$ and $\hat{S}_2^n$. Decoder 2 utilizes $W$ and $Y_2^n$ to produce $\hat{S}_2^n$. The goal is to minimize the rate $R$ such that the distortion for $S_1$ at Decoder 1 is within a threshold $D_1$, and $S_2$ is recovered losslessly at both decoders.

Theoretical Methodology

The paper is a theoretical work utilizing the tools of Shannon Theory. The authors employ two primary proof techniques to establish their results:

  • The Converse Proof: Using the Csiszár-Körner sum-identity, they prove that no coding scheme can ever achieve a rate lower than their proposed function. This establishes the "impossibility" boundary.
  • The Achievability Proof: They propose a coding scheme based on Random Binning (a standard technique in multi-terminal source coding) and Auxiliary Random Variables ($U_0, U_1$).
  • $U_1$ represents an "individual description" tailored for User 1.
  • $U_0$ represents a "common description" layer that helps both users.
  • Fourier-Motzkin Elimination (FME): This mathematical algorithm is used to simplify complex systems of rate inequalities into a single, elegant rate-distortion expression.

One of the key insights is the power of joint compression. Intuitively, one might think you should compress the two sources separately. However, the paper shows that joint compression—where the common description $U_0$ can include parts of both sources—is necessary to reach the theoretical optimum. The auxiliary variable $U_0$ acts as a flexible "bridge." Depending on the side information, $U_0$ might contain parts of the source that only User 1 technically needs, because sending it as a "common layer" might actually be more efficient than sending it as an "individual layer."

Generalization to Lossy Common Reconstruction

The authors extend their result to a "Lossy Common Reconstruction" model. In this setup, the encoder and both decoders must share the exact same compressed version of a source.

Heegard-Berger model with a common reconstruction constraint.

This constraint fundamentally changes how side information can be used. In this generalized model, side information can be used for "binning" (reducing the transmission rate) but not for "estimation" (improving the quality of the reconstruction beyond what the encoder provides). This distinction is critical for designing robust communication protocols where all nodes must agree on the state of the data.

Key Results and Implications

  • Theorem 1: Provides the first single-letter characterization of the rate-distortion function $R(D_1)$ for the degraded reconstruction problem with arbitrary side information.
  • Theorem 3: Generalizes the result to the "Lossy Heegard-Berger" problem with a common reconstruction constraint.
  • Efficiency Gains: In a binary example using four independent Bernoulli(1/2) sources, the authors show that a naive approach (ignoring the utility of the common description $U_0$) requires 3 bits/sample, while their optimal approach requires only 2 bits/sample—a significant 33% reduction in data.

Conclusion and Future Work

While this work provides a rigorous foundation for two-user systems, several challenges remain. Scaling these results to $N$ users with arbitrary side information is significantly more complex and remains an open problem. Additionally, while the paper provides the formula for the optimal rate, finding the specific probability distributions for the auxiliary variables ($U_0, U_1$) for real-world sources is a non-trivial optimization task. Finally, extending these results from memoryless sources to sources with memory (like video or speech) would be a natural next step for practical implementation.

Summary updated

Abstract

In this work, we investigate an instance of the Heegard-Berger problem with two sources and arbitrarily correlated side information sequences at two decoders, in which the reconstruction sets at the decoders are degraded. Specifically, two sources are to be encoded in a manner that one of the two is reproduced losslessly by both decoders, and the other is reproduced to within some prescribed distortion level at one of the two decoders. We establish a single-letter characterization of the rate-distortion function for this model. The investigation of this result in some special cases also sheds light on the utility of joint compression of the two sources. Furthermore, we also generalize our result to the setting in which the source component that is to be recovered by both users is reconstructed in a lossy fashion, under the requirement that all terminals (i.e., the encoder and both decoders) can share an exact copy of the compressed version of this source component, i.e., a common encoder-decoders reconstruction constraint. For this model as well, we establish a single-letter characterization of the associated rate-distortion function.
BibTeX
@article{benammar2016rate,
  author = {Meryem Benammar and Abdellatif Zaidi},
  title = {{Rate-Distortion Function for a Heegard-Berger Problem with Two Sources and Degraded Reconstruction sets}},
  journal = {IEEE Trans. Information Theory},
  year = {2016},
  url = {https://openreview.net/forum?id=9AYy12MbroBg},
}
Figure