On asymptotic solutions of the Lloyd-Max scalar quantization
Bormin Huang, Jing Ma · 2007
The Lloyd-Max scalar quantization is to find a set of quanta {q1, ..., qn} and a set of partition endpoints {x1,..., xn-1] that minimize the mean squared error distortion, given a probability distribution p(x). For symmetrical distributions, optimal quantizers can be nonsymmetrical. Previous studies proved that the log-concavity of p(x) is sufficient for the uniqueness of a locally optimal solution, which is therefore globally optimal. When the distribution satisfies the log-concavity condition, the optimal quantizer is symmetrical. The condition covers the Gaussian, Laplace, and Rayleigh distributions. In this paper we show that there exist asymptotic solutions for such distributions that arenumericallyconsidered as the solutions to the Lloyd-Max problem within any finite machine precision, althoughtheoreticallythey are not. We use MATLAB symbolic math toolbox to list these asymptotic solutions with 21 decimal digits of accuracy, with dqnsmaller than 64-bit floating point spacing to be regarded as zero. These asymptotic solutions are degenerate solutions with some quanta and endpoints approaching to infinity. For such a log-concave distribution with an even number (n = 2 m ges 6) of quantization levels, the Lloyd- Max quantization seems to yield k = lceilm/2rceil-1 degenerate solutions with n - 4, ... , n - 4 kfinitequanta, respectively. Furthermore, the k degenerate solutions of the Lloyd-Max quantization with n quantizer level correspond to the optimal solutions of the Lloyd-Max quantization with n-4, ... , n-4k quantizer levels, respectively. These asymptotic solutions are locally minimum mean-square error quantizers, but none of them is the globally optimal quantizer.