Optimal quantization by matrix searching

Optimal quantization, a fundamental problem in source coding and information theory, can be formulated as a discrete optimization problem. In 1964 Bruce (“Optimum Quantization,” Sc.D. thesis, MIT, May 1964) devised a dynamic programming algorithm for discrete optimal quantization. For the mean-square error measure and when the amplitude density function of the quantized signal is represented by a histogram of N points, Bruce's algorithm can compute the optimal K-level quantizer in O(KN2) time. This paper shows that the same problem can be solved in O(KN) time. The improvement is made by a better understanding of the objective function in this particular non-linear programming problem and the use of Aggarwal et al.'s matrix-searching technique.