Exponential rate of convergence for Lloyd's method I

Abstract

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 in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</tex> . 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 time <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</tex> using the quantizer obtained on the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</tex> th 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.