An O(KN lg N) algorithm for optimum K-level quantization on histograms of N points
Xiaolin Wu, Jon George Rokne · 1989
Optimum quantization is a fundamental problem in digital signal processing and information theory. In 1964 Bruce [1] devised a polynomial-time algorithm to solve this particular non-linear programming problem using the dynamic programming technique. 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 generate the optimum K-level quantizer in O(KN2) time. This paper proposes an efficient algorithm which can do the same job with the worst-case time complexity of O(KN lg N). This is due to the discovery of some useful properties of optimum meansquare quantizers and an innovative algorithm structure combining the two algorithmic techniques, dynamic programming and divide-and-conquer. This algorithm structure contributes a new effective methodology to the design of efficient algorithms. Finally the paper outlines a more sophisticated algorithm which can reduce both the time and space complexity of the O(KN lg N) algorithm derived in the paper.