Stuart P. Lloyd

Stuart P. Lloyd developed conditions and an iterative procedure for minimizing squared error in quantization. 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.^[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.^[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 isUsing 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.