2020

Entropy-Constrained Maximizing Mutual Information Quantization

Nguyen, Thuan, Nguyen, Thinh

Understand

In this paper, we investigate the quantization of the output of a binary input discrete memoryless channel that maximizing the mutual information between the input and the quantized output under an entropy-constrained of the quantized output.

A polynomial time algorithm is introduced that can find the truly global optimal quantizer.
These results hold for binary input channels with an arbitrary number of quantized output.
Finally, we extend these results to binary input continuous output channels and show a sufficient condition such that a single threshold quantizer is an optimal quantizer.

Built on

Entropy-constrained vector quantization
Philip A. Chou, Tom D. Lookabaugh, and Robert M. Gray · 1989
Earlier work this paper cites.
Vector quantization and signal compression
Allen Gersho and Robert M. Gray · 1991
Earlier work this paper cites.
Optimal partitioning for classification and regression trees
Philip A. Chou · 1991
Earlier work this paper cites.
Minimum impurity partitions
David Burshtein, Vincent Della Pietra, Dimitri Kanevsky, and Arthur Nadas · 1992
Earlier work this paper cites.
Partitioning nominal attributes in decision trees
Don Coppersmith, Se June Hong, and Jonathan RM Hosking · 1999
Earlier work this paper cites.
On the structure of entropy-constrained scalar quantizers
A. Gyorgy and Tamás Linder · 2001
Earlier work this paper cites.
Performance of low rate entropy-constrained scalar quantizers
Daniel Marco and David L. Neuhoff · 2004
Earlier work this paper cites.
On entropy-constrained vector quantization using
David Yuheng Zhao, Jonas Samuelsson, and Mattias Nilsson · 2008
Earlier work this paper cites.

Similar

How to construct polar codes
Original
Ido Tal and Alexander Vardy · 2011
Cited alongside, same era.
Ckmeans. 1d. dp: optimal k-means clustering in one dimension by dynamic programming
Haizhou Wang and Mingzhou Song · 2011
Cited alongside, same era.
Channel-optimized vector quantization with mutual information as fidelity criterion
Andreas Winkelbauer, Gerald Matz, and Andreas Burg · 2013
Cited alongside, same era.
Threshold optimization for capacity-achieving discrete input one-bit output quantization
Rudolf Mathar and Meik Dörpinghaus · 2013
Cited alongside, same era.
At low snr, asymmetric quantizers are better
Tobias Koch and Amos Lapidoth · 2013
Cited alongside, same era.
Quantization of binary-input discrete memoryless channels
Brian M Kurkoski and Hideki Yagi · 2014
Cited alongside, same era.
Quantizer design for outputs of binary-input discrete memoryless channels using smawk algorithm
Ken-ichi Iwata and Shin-ya Ozawa · 2014
Cited alongside, same era.
Suboptimal quantizer design for outputs of discrete memoryless channels with a finite-input alphabet
Yuta Sakai and Ken-ichi Iwata · 2014
Cited alongside, same era.

Then

Decoding ldpc codes with mutual information-maximizing lookup tables
Francisco Javier Cuadros Romero and Brian M Kurkoski · 2015
Later among the works it cites.
Low-complexity quantization of discrete memoryless channels
Jiuyang Alan Zhang and Brian M Kurkoski · 2016
Later among the works it cites.
The deterministic information bottleneck
DJ Strouse and David J Schwab · 2017
Later among the works it cites.
Single-bit quantization of binary-input, continuous-output channels
Brian M Kurkoski and Hideki Yagi · 2017
Later among the works it cites.
On the capacities of discrete memoryless thresholding channels
Thuan Nguyen, Yu-Jung Chu, and Thinh Nguyen · 2018
Later among the works it cites.
Dynamic programming for discrete memoryless channel quantization
Original
Xuan He, Kui Cai, Wentu Song, and Zhen Mei · 2019
Later among the works it cites.
Minimizing impurity partition under constraints
Original
Thuan Nguyen and Thinh Nguyen · 2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…