Communication-Channel Optimized Impurity Partition
Thuan Nguyen, Thinh Nguyen · 2020
Given an original discrete source X with the distribution pX that is corrupted by noise to produce a noisy data Y with the given joint distribution p(X,Y). A quantizer/classifier Q : Y → Z is then used to classify/quantize Y to a discrete partitioned output Z having probability distribution pZ. Next, Z is transmitted over a discrete memoryless channel (DMC) with a given channel matrix A that produces the final discrete output T . One wants to design an optimal quantizer/classifier Q* to minimize the end-to-end impurity/cost function F(X, T) between the input X and the final output T. Our result generalizes some previous results. First, an iteration linear time complexity algorithm is proposed to find the locally optimal quantizer. Second, we show that the optimal quantizers produce the hard partitions that are equivalent to the cuts by hyper-planes in the space of the posterior distribution pX|Y. This result provides a polynomial-time complexity algorithm to find the globally optimal quantizer. Finally, in the special case where the source X is binary, an efficient algorithm is proposed to find the truly global optimal partition.