Least Squares Quantization in PCM
Stuart P. Lloyd
IEEE Transactions on Information Theory 28(2):129-137 (Bell Labs memo)
about this write-up
No legal free copy was found. This write-up is from secondary sources and standard accounts of the Lloyd-Max quantiser, not from a reading of the original PDF.
the original →the setting
To turn a sound signal into bits, you first sample it in time, then round each sample
to one of k allowed levels. That rounding adds error. Lloyd asked: given how the
signal's values are spread out, where should the k levels go to make the average
squared error as small as possible?
Evenly spaced levels are only best for a signal that's evenly spread. Real signals, like speech, sit near zero most of the time, so the levels should crowd there.
two rules every best answer follows
For the best levels q₁ < … < q_k with boundaries between them:
- Each boundary sits halfway between its two neighbouring levels. Given the levels, rounding every value to the nearest one is clearly best.
- Each level sits at the average of the values in its cell. Given the cells, the average is the point that minimises squared error inside each one.
the algorithm
Start with some levels, then alternate: recompute the boundaries as halfway points, then recompute each level as the average of its cell. The error never goes up, so it always settles, though possibly at a good-but-not-best answer.
Move from one dimension to many, and from a known signal to a set of points, and this is exactly the k-means algorithm. That's why it's called Lloyd's algorithm.
history
- It was written as an internal technical memo that circulated for many years before it was formally published.
- Joel Max found the same rules independently, so the one-dimensional version is often called the Lloyd-Max quantiser.
- Others had similar ideas (Steinhaus, Forgy, and MacQueen, who coined "k-means"). The standard back-and-forth algorithm is usually credited to Lloyd.
in this repo
lloyd_max_1d(samples, k)is Lloyd's setting directly.KMeansis the same two steps in any number of dimensions.- The k-means demo recovers the best 4 levels for a bell-curve signal (±0.453 and ±1.510), matching Max's published table.