Information-Distilling Quantizers

Alankrita Bhatt, Bobak Nazer, Or Ordentlich, Yury Polyanskiy

Abstract

This paper investigates the design of scalar quantizers for a random variable $Y$ that maximize the mutual information between the quantizer's output and a dependent variable $X$. Unlike traditional quantization that minimizes distortion (e.g., mean-squared error), this "information-distilling" approach focuses on the multiplicative fraction of information preserved. We specifically examine the "low-information regime" where $I(X;Y)$ is small. We establish that for binary $X$, $\mathcal{O}(\log(1/I(X;Y)))$ quantization levels are necessary and sufficient to preserve a constant fraction of information. For larger alphabets, the required levels scale polynomially with the log-inverse of the initial information.

Introduction

In communication and machine learning, data compression often serves a specific downstream task: predicting a hidden variable $X$ from an observed variable $Y$. This objective is the foundation of the Information Bottleneck problem. While asymptotic results for block quantization (processing infinitely long sequences) are well-established, the performance of scalar quantization—processing one sample at a time—is less understood, particularly regarding how much information is lost when the available mutual information is already very small.

This paper addresses the "multiplicative gap": what fraction $\eta$ of the original mutual information $I(X;Y)$ can be retained using a quantizer with $M$ levels? This distinction is critical in the low-information regime, where the absolute (additive) loss might be small, but the relative loss can be catastrophic.

Methodology

The authors define an "information distillation" function, representing the minimum information a quantizer can guarantee to preserve for a given alphabet size and initial information level. The study utilizes several key theoretical approaches:

  • Bounding Techniques: Deriving lower and upper bounds for the distillation function across binary and finite alphabets.
  • One-Hot Encoding: Reducing the problem for larger alphabets ($|X| > 2$) into multiple binary sub-problems.
  • Constructive Counter-examples: Using specific distributions, such as a modified Binary Erasure Channel (BEC), to prove that certain quantization requirements are fundamental and cannot be reduced.
  • Optimization Analysis: Connecting the search for an optimal quantizer to the Subset Sum Problem to determine computational complexity.

Key Insights and Results

The Failure of MAP Quantization

A common intuition in signal processing is to use a Maximum A Posteriori (MAP) estimator as a quantizer. However, the authors demonstrate that this is suboptimal in the low-information regime. For a BEC with low capacity, the information preserved by a MAP quantizer vanishes much faster than that of an optimal information-distilling quantizer.

Scaling in Binary and Large Alphabets

The paper's primary contribution is characterizing the scaling of quantization levels ($M$):

  1. Binary $X$: To preserve a constant fraction of mutual information, one needs $M = \mathcal{O}(\log(1/I(X;Y)))$ levels. This is counter-intuitive, as one might expect two levels to suffice for a binary variable; however, the "distillation" process requires significantly more granularity to be effective.
  2. Large Alphabets: For an alphabet of size $K$, an $\eta$-fraction of information can be preserved using roughly $(\log(K/I(X;Y)))^{\eta(K-1)}$ levels.

Computational Complexity

The authors prove that finding the optimal $M$-level quantizer is NP-hard. By linking the $M=2$ optimization problem to the Subset Sum problem, they show that the task becomes computationally intractable as the alphabet size of $X$ grows without constraint.

Conclusion

This research highlights a significant efficiency gap between scalar quantization and block quantization. In the scalar case, distilling information in low-correlation environments requires a surprisingly high number of quantization levels.

Future work remains in bridging the gap between scalar and large-block results by investigating small-block quantization (e.g., pairs or triplets of samples). Additionally, while this paper provides existence bounds, the development of efficient, near-optimal algorithms for general alphabets remains an open challenge.

Summary updated

Abstract

Let $X$ and $Y$ be dependent random variables. This paper considers the problem of designing a scalar quantizer for $Y$ to maximize the mutual information between the quantizer's output and $X$, and develops fundamental properties and bounds for this form of quantization, which is connected to the log-loss distortion criterion. The main focus is the regime of low $I(X;Y)$, where it is shown that, if $X$ is binary, a constant fraction of the mutual information can always be preserved using $\mathcal{O}(\log(1/I(X;Y)))$ quantization levels, and there exist distributions for which this many quantization levels are necessary. Furthermore, for larger finite alphabets $2 < |\mathcal{X}| < \infty$, it is established that an $η$-fraction of the mutual information can be preserved using roughly $(\log(| \mathcal{X} | /I(X;Y)))^{η\cdot(|\mathcal{X}| - 1)}$ quantization levels.
BibTeX
@article{bhatt2018information,
  author = {Alankrita Bhatt and Bobak Nazer and Or Ordentlich and Yury Polyanskiy},
  title = {{Information-Distilling Quantizers}},
  journal = {IEEE Transactions on Information Theory},
  year = {2018},
  doi = {10.1109/tit.2021.3059338},
}
Figure