Universal Weak Variable-Length Source Coding on Countably Infinite Alphabets

Jorge F. Silva, Pablo PiantanidaIEEE Trans. Information Theory 2020 · OpenReview

TL;DR

This paper introduces "almost lossless source coding" for infinite alphabets, relaxing the strict lossless requirement to allow vanishing distortion. This makes universal source coding feasible for a broad class of sources, offering a trade-off between distortion and redundancy that can outperform traditional lossless methods.

What Problem Does This Paper Address?

Traditional universal source coding (USC) aims to compress data from sources with unknown statistics without sacrificing any information (lossless). This works well for finite alphabets. However, for sources with countably infinite alphabets (like sequences of integers), achieving lossless universal coding is impossible. This is because the "information radius," a measure of how much information is needed to identify the source's true statistics, grows too quickly. This paper tackles this by proposing a relaxed version: "almost lossless source coding." The goal is to achieve a rate close to the theoretical minimum (Shannon entropy) while allowing a small, asymptotically vanishing distortion. This opens the door to universal coding for a much wider range of infinite-alphabet sources.

Methods

The core idea is to relax the "lossless" constraint to "almost lossless." This means allowing a small, per-letter distortion that disappears as the block length of the data increases. The authors achieve this by proposing a two-stage coding scheme:

  1. Lossy Alphabet Reduction: The infinite alphabet is first "quantized" or reduced to a finite set of symbols. This is where the distortion is introduced.
  2. Lossless Coding: The reduced alphabet symbols are then encoded using a standard variable-length lossless code.

They analyze this scheme by:

  • Characterizing Achievable Rates: Showing that Shannon entropy still dictates the minimum achievable rate even with this relaxation.
  • Proving Feasibility: Demonstrating that almost lossless universal source coding is possible for finite-entropy stationary memoryless sources on infinite alphabets.
  • Investigating Universality Notions: Defining and studying both point-wise and uniform convergence of distortion.
  • Analyzing "Envelope Distributions": Focusing on a specific family of distributions (indexed by an "envelope function") to derive precise conditions for uniform convergence and to compare redundancy rates with lossless methods.

Datasets

Not discussed in the paper. The paper deals with theoretical source coding and does not use specific datasets for training or evaluation.

Key Insights and Ideas

  • Relaxing Losslessness is Key: The fundamental insight is that by allowing a vanishing distortion, the impossibility of lossless universal coding for infinite alphabets can be overcome. This is a crucial shift in perspective.
  • Two-Stage Coding as a Bridge: The proposed two-stage scheme (quantization + lossless coding) provides a practical framework for achieving almost lossless coding.
  • Shannon Entropy Remains Fundamental: Even with distortion, the theoretical limit for the coding rate is still dictated by the source's Shannon entropy.
  • Uniform Convergence is a Stronger Goal: Achieving uniform convergence of distortion across all sources in a family (not just point-wise) is a more stringent requirement, leading to specific conditions related to "envelope distributions."
  • Redundancy vs. Distortion Trade-off: The paper highlights that almost lossless coding can offer faster convergence of redundancy compared to traditional lossless methods, at the cost of introducing a controlled distortion. This allows for different performance regimes.

Key Results

  • Feasibility of Almost Lossless USC: The paper proves that almost lossless universal source coding is feasible for the entire family of finite-entropy stationary memoryless sources on countably infinite alphabets.
  • Shannon Entropy as Minimum Rate: For a known source distribution, the minimum achievable rate for almost lossless coding is its Shannon entropy.
  • Uniform Convergence Conditions: For "envelope distributions," a necessary and sufficient condition for uniform convergence of distortion (and vanishing redundancy) is identified, which surprisingly matches the condition for strong minimax universality in the lossless case.
  • Redundancy Gains: For certain families of distributions (summable envelope functions), an almost lossless scheme can achieve faster convergence of redundancy compared to lossless methods, by carefully balancing distortion and redundancy.

Limitations and Future Work

  • Focus on Specific Families: While feasibility is shown for a broad class, detailed analysis of redundancy gains is focused on "envelope distributions." Future work could explore other distribution families.
  • Theoretical Framework: The paper is primarily theoretical, establishing feasibility and characterizing performance. Practical implementation details and performance on real-world data are not discussed.
  • Distortion Metric: The paper primarily uses normalized Hamming distance. Exploring other distortion metrics could be a future direction.
  • Generalizing to Other Source Models: The current work focuses on stationary and memoryless sources. Extending the results to more complex source models (e.g., Markov sources) would be a natural next step.

Summary updated

Abstract

Motivated from the fact that universal source coding on countably infinite alphabets (∞-alphabets) is not feasible, this work introduces the notion of “almost lossless source coding”. Analog to the weak variable-length source coding problem studied by Han (IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1217-1226, Jul. 2000), almost lossless source coding aims at relaxing the lossless block-wise assumption to allow an average per-letter distortion that vanishes asymptotically as the block-length tends to infinity. In this setup, we show on one hand that Shannon entropy characterizes the minimum achievable rate (similarly to the case of finite alphabet sources) while on the other that almost lossless universal source coding becomes feasible for the family of finite-entropy stationary memoryless sources with ∞-alphabets. Furthermore, we study a stronger notion of almost lossless universality that demands uniform convergence of the average per-letter distortion to zero, where we establish a necessary and sufficient condition for the so-called family of “envelope distributions” to achieve it. Remarkably, this condition is the same necessary and sufficient condition needed for the existence of a strongly minimax (lossless) universal source code for the family of envelope distributions. Finally, we show that an almost lossless coding scheme offers faster rate of convergence for the (minimax) redundancy compared to the well-known information radius developed for the lossless case at the expense of tolerating a non-zero distortion that vanishes to zero as the block-length grows. This shows that even when lossless universality is feasible, an almost lossless scheme can offer different regimes on the rates of convergence of the (worst case) redundancy versus the (worst case) distortion.
BibTeX
@article{silva2020universal,
  author = {Jorge F. Silva and Pablo Piantanida},
  title = {{Universal Weak Variable-Length Source Coding on Countably Infinite Alphabets}},
  journal = {IEEE Trans. Information Theory},
  year = {2020},
  url = {https://openreview.net/forum?id=Hhzh59dGMGI},
}
Figure