Exponential rate of convergence for Lloyd's method I
John C. Kieffer · IEEE Transactions on Information Theory · 1982
For a random variable with finite second moment and log-concave density, a unique quantizer exists which produces the minimum expected encoding error, using squared-error distortion. An algorithm given by Lloyd (Lloyd's Method I) yields a sequence of quantizers which converges to the optimum quantizer. Using results of Fleischer, it is shown that the convergence takes place exponentially fast if the logarithm of the density is not piecewise affine. As a consequence the number of iterations of Lloyd's algorithm needed to obtain the optimum distortion correct to n decimal places approaches infinity no faster than linearly inn. Another consequence is that if the output of a stationary information source at each time is distributed according to the given density, the source output can be encoded at each timeiusing the quantizer obtained on theith iteration of Lloyd's method obtaining the same asymptotic behavior one would have obtained if the optimum quantizer had been used to encode at each time.