= Stuart P. Lloyd
{c}
<Stuart P. Lloyd> developed conditions and an iterative procedure for minimizing squared error in <quantization (signal processing)>. His paper <Least Squares Quantization in PCM by Stuart P. Lloyd>, published in 1982, identifies Bell Laboratories as his affiliation and records a presentation of part of the work in 1957. The motivating problem was <pulse-code modulation>: representing a signal sample by one of finitely many reconstruction values.<Least Squares Quantization in PCM by Stuart P. Lloyd>[Page 129, author footnote and introduction]{ref}
The central conditions have a clear interpretation. For fixed reconstruction values, assign an input to a nearest value. For fixed assignment regions of positive probability, place each reconstruction value at the corresponding <conditional expectation>. Alternating these operations gives <Lloyd's algorithm>; neither operation increases the <mean squared error>, but this does not guarantee the global optimum from every initialization.<Least Squares Quantization in PCM by Stuart P. Lloyd>[Sections IV–VI: best quanta, best partition and an algorithm]{ref}
For an original example, take a <continuous uniform distribution> on $[-1,1]$ and two reconstruction values. Splitting at zero gives conditional means $-1/2$ and $1/2$, whose midpoint is again zero. The <mean squared error> is
$$
\frac12\int_{-1}^{0}(x+1/2)^2\,dx+\frac12\int_{0}^{1}(x-1/2)^2\,dx=\frac1{12}.
$$
Using the single reconstruction value zero instead gives $1/3$. This concrete improvement explains the optimization objective: preserve signal amplitudes accurately with a limited collection of values.
Back to article page
