Source Coding With a Side Information "Vending Machine"

Haim H. Permuter, Tsachy WeissmanIEEE Trans. Information Theory 2011 · OpenReview

TL;DR

This paper introduces a novel framework for source coding where "actions" can be taken to influence the availability and quality of side information (SI). The authors characterize the fundamental limits of rate, distortion, and cost for these scenarios, revealing that a greedy approach to SI acquisition is often suboptimal, even without cost constraints.

What Problem Does This Paper Address?

Traditional source coding with side information (like Wyner-Ziv coding) assumes the SI is fixed and given. This paper tackles a more dynamic scenario: what if the system can actively influence the SI? Imagine a sensor network where you can choose how much power to allocate to a sensor (affecting its quality) or which sensors to activate, all while facing constraints on resources (cost) and the need to compress data (rate) with a certain fidelity (distortion). The problem is to find the optimal strategy for taking these actions to achieve the best rate-distortion-cost tradeoff.

Methods

The authors extend the Wyner-Ziv problem to incorporate "actions" that affect the SI. They analyze two main scenarios:

  1. Decoder-controlled actions: The decoder chooses actions after receiving an index from the encoder, influencing the SI it receives.
  2. Encoder-controlled actions: The encoder chooses actions before encoding, influencing the SI that nature generates.

They derive rate-distortion-cost functions for various settings, including lossless and lossy compression, and specific channel models (Gaussian, Markov). Key mathematical tools include information-theoretic quantities like mutual information and entropy, and the analysis of convex optimization problems to find optimal distributions. They also leverage concepts from Wyner-Ziv and Slepian-Wolf coding.

Datasets

Not discussed in the paper. The paper focuses on theoretical characterizations and examples based on defined source and channel models, not empirical evaluation on datasets.

Key Insights and Ideas

  • Active SI Management: The core idea is that SI isn't just a passive resource; it can be actively managed through system actions.
  • Greedy is Suboptimal: A crucial finding is that simply choosing the action that yields the "best" SI (e.g., lowest distortion) without considering the overall system constraints (rate, cost, encoder's information) is generally not optimal. This holds even without explicit costs.
  • Time-Sharing Suboptimality: Even when costs are involved, simply time-sharing between optimal schemes for different cost levels can be suboptimal.
  • Action-Dependent SI: The quality and availability of SI can be dynamically controlled, leading to new tradeoffs.
  • "Vending Machine" Analogy: The title aptly captures the idea of "purchasing" or "selecting" SI quality/availability with associated costs.

Key Results

  • Full Characterization (Decoder Actions): The paper fully characterizes the rate-distortion-cost tradeoff for the scenario where the decoder controls actions.
  • Partial Characterization (Encoder Actions): For encoder-controlled actions, they provide characterizations for specific important cases (lossless, Gaussian, Markov) and upper/lower bounds for the general case.
  • Specific Examples: The paper works out examples, such as a fair coin flip source with Z-channel and S-channel side information, demonstrating that the proposed framework can yield strictly better performance than simpler greedy or time-sharing strategies. For instance, in one example, a 1.5% improvement in rate was shown.
  • Gaussian Case Formula: A specific formula for the rate-distortion-cost function is derived for the Gaussian setting.

Limitations and Future Work

  • Encoder Actions - General Case: A full characterization of the rate-distortion-cost tradeoff for encoder-controlled actions remains an open problem.
  • Causal Decoder Actions: The paper explores decoder actions taken before seeing the index. The question of whether performance can be improved if actions can depend on past side information symbols (i.e., $A_i = A_i(T, Y^{i-1})$) is left open.
  • Complexity: While theoretical limits are characterized, the practical implementation of these optimal strategies might involve complex computations.

Summary updated

Abstract

We study source coding in the presence of side information, when the system can take actions that affect the availability, quality, or nature of the side information. We begin by extending the Wyner-Ziv problem of source coding with decoder side information to the case where the decoder is allowed to choose actions affecting the side information. We then consider the setting where actions are taken by the encoder, based on its observation of the source. Actions may have costs that are commensurate with the quality of the side information they yield, and an overall per-symbol cost constraint may be imposed. We characterize the achievable tradeoffs between rate, distortion, and cost in some of these problem settings. Among our findings is the fact that even in the absence of a cost constraint, greedily choosing the action associated with the “best” side information is, in general, suboptimal. A few examples are worked out.
BibTeX
@article{permuter2011source,
  author = {Haim H. Permuter and Tsachy Weissman},
  title = {{Source Coding With a Side Information "Vending Machine"}},
  journal = {IEEE Trans. Information Theory},
  year = {2011},
  url = {https://openreview.net/forum?id=Yuze7_5_ye},
}
Figure