Coding for Computing Arbitrary Functions Unknown to the Encoder

Sourya Basu, Lav R. Varshney

TL;DR

This paper tackles the problem of source coding where the receiver needs to compute a function of the data, but the encoder doesn't know what that function is. They establish the fundamental limits (rate regions) for both point-to-point and distributed scenarios, showing that these limits expand beyond traditional entropy bounds when the function is non-bijective. This has implications for efficient data compression when the ultimate use of the data is unknown to the sender.

What Problem Does This Paper Address?

Traditionally, source coding (like data compression) aims to reproduce the original data at the receiver with minimal bits. However, in many real-world applications, the receiver is not interested in the raw data itself, but rather in a specific function or computation performed on that data (e.g., inferring a trend, classifying an image). A key challenge arises when the sender (encoder) doesn't know what function the receiver (decoder) will eventually want to compute. This can be due to privacy concerns, computational limitations of sensors, or simply an exploratory phase where the exact analysis is yet to be determined. The authors address this by defining and characterizing the optimal compression rates for scenarios where the encoder is blind to the function of interest at the decoder.

Methods

The paper introduces two main problems: computational source coding (point-to-point) and distributed computational source coding. For both, they derive the achievable rate regions. A core technique employed is a novel proof method called "codebook trimming," which is described as being similar to random binning. This technique is used to construct efficient coding schemes and prove the derived rate regions. The proofs rely heavily on concepts from information theory, particularly typicality properties of sequences and bounds derived from Fano's inequality and Chernoff bounds. They also leverage existing results from information theory, such as the Slepian-Wolf theorem and bounds on the size of typical sets.

Datasets

Not discussed in the paper. The paper deals with theoretical limits and achievable schemes for information sources, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Encoder Ignorance is Solvable: The paper demonstrates that it's possible to achieve reliable computation of a function of data even when the encoder has no knowledge of that function. This is a significant departure from traditional coding where the encoder needs to know what it's encoding for.
  • Functionality Expands Rate Regions: When the destination is interested in a non-bijective function (meaning multiple inputs can map to the same output), the achievable rate region for point-to-point coding expands beyond the entropy of the original data, and for distributed coding, it expands beyond the Slepian-Wolf rate region. This implies that more bits might be needed compared to simply encoding the raw data, but it's still achievable and characterized.
  • "Codebook Trimming" as a Proof Tool: The introduction of codebook trimming as a proof technique is a novel contribution, offering a structured way to handle the complexity of unknown functions in coding.
  • Asymptotic Optimality: The proposed schemes are shown to be asymptotically optimal, meaning they can achieve rates arbitrarily close to the theoretical limits as the block length (amount of data) increases.

Key Results

  • Point-to-Point Computational Source Coding: For a single encoder and decoder, the achievable rate $R$ for reliably computing $f(X)$ is $R > H(f(X))$, where $H(f(X))$ is the entropy of the function's output. This is achievable even without the encoder knowing $f(\cdot)$.
  • Distributed Computational Source Coding: For two encoders and one decoder, the achievable rate region $(R_1, R_2)$ for computing $f(X, Y)$ is characterized by:
  • $R_1 \ge H(f(X,Y)|Y)$
    • $R_2 \ge H(f(X,Y)|X)$
    • $R_1 + R_2 \ge H(f(X,Y))$ These bounds are achieved even when the encoders are unaware of $f(\cdot)$.

Limitations and Future Work

  • Lossy vs. Lossless: This paper focuses on lossless source coding. The authors mention that their approach can be a subcomponent for lossy functional problems, suggesting future work in that direction.
  • Specific Function Types: While the paper characterizes the rate regions for arbitrary functions, the practical implications and efficiency for specific classes of functions (e.g., linear functions, specific types of non-bijective functions) might warrant further investigation.
  • Computational Complexity: The paper focuses on theoretical limits. The practical implementation and computational complexity of the proposed coding schemes, especially the codebook trimming process, are not detailed and could be an area for future research.

Summary updated

Abstract

In this paper we consider point-to-point and distributed source coding problems where the receiver is only interested in a function of the data sent by the source encoder(s), while knowledge of the function remains unknown to the encoder(s). We find the rate region for these problems, and in particular, show that if the destination is interested in computing a non-bijective function then the rate region for the point-to-point source coding problem expands over the entropy, and the rate region over the distributed source coding problem expands over the Slepian-Wolf rate region. A novel proof technique, similar to random binning, is developed to prove these results.
BibTeX
@misc{basu2018coding,
  author = {Sourya Basu and Lav R. Varshney},
  title = {{Coding for Computing Arbitrary Functions Unknown to the Encoder}},
  year = {2018},
  eprint = {1810.10666},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.10666},
}

Loading related content...

Figure