Communication-Channel Optimized Partition
This work addresses communication channel optimization for signal processing or machine learning applications, offering incremental improvements by generalizing existing theoretical results.
The paper tackles the problem of designing an optimal quantizer/classifier to minimize a cost function between input and output under a concave constraint, generalizing prior results. It proposes an iterative linear-time algorithm for local optima and proves that the globally optimal quantizer can be found in polynomial time via hyper-plane cuts in probability space.
Given an original discrete source X with the distribution p_X that is corrupted by noise to produce the noisy data Y with the given joint distribution p(X, Y). A quantizer/classifier Q : Y -> Z is then used to classify/quantize the data Y to the discrete partitioned output Z with probability distribution p_Z. Next, Z is transmitted over a deterministic channel with a given channel matrix A that produces the final discrete output T. One wants to design the optimal quantizer/classifier Q^* such that the cost function F(X; T) between the input X and the final output T is minimized while the probability of the partitioned output Z satisfies a concave constraint G(p_Z) < C. Our results generalized some famous previous results. First, an iteration linear time complexity algorithm is proposed to find the local optimal quantizer. Second, we show that the optimal partition should produce a hard partition that is equivalent to the cuts by hyper-planes in the probability space of the posterior probability p(X|Y). This result finally provides a polynomial-time algorithm to find the globally optimal quantizer.