Least Squares Quantization in PCM

When you speak into a telephone, your voice is a smooth, continuous voltage that varies over time. To send it digitally, we must sample it at regular intervals and round each sample to one of $N$ allowed values — this rounding is called quantization. The rounded values are called quanta (or reproduction values, or centroids).

The simplest approach is uniform quantization: space the $N$ quanta evenly across the voltage range. But this is wasteful. A typical voice signal spends most of its time at low amplitudes (near silence) and only rarely hits loud peaks. Uniform spacing gives equal precision to the rare peaks and the common quiet parts — wasting bits where they matter least.

The question Lloyd asked was: given that we know the probability distribution of the signal, where exactly should we place the $N$ quanta to minimize the average squared error?

Lloyd proved that any quantizer minimizing the mean squared error must satisfy two conditions simultaneously. Before seeing the math, understand what each one means — they are remarkably intuitive:

Rule 1 — Nearest-neighbor condition. Every signal sample must be assigned to the closest quantum. If you have a sample at voltage 3.7 and quanta at 3.0 and 4.0, the sample goes to 4.0 — never to the farther one. This means the decision boundary between two adjacent quanta sits exactly at their midpoint.

Rule 2 — Centroid condition. Each quantum must be the average (centroid) of all samples assigned to it. If the samples landing in some interval are clustered toward the left end, the quantum should move leftward to reduce their average error.

These two rules are necessary — violating either one means you can reduce the error by fixing the violation. Together, they define the shape of any locally optimal quantizer.

Suppose the signal amplitude $x$ follows a probability density function $p(x)$. A quantizer with $N$ levels divides the real line into $N$ intervals $[t_{i-1}, t_i)$ with reproduction values (quanta) $q_i$ inside each interval. The goal is to minimize the distortion — the expected squared difference between the original signal and its quantized version.

Fix the quanta $q_i$ and ask: where should the decision boundary $t_i$ between adjacent quanta $q_i$ and $q_{i+1}$ sit? A sample at $x = t_i$ is equidistant from both quanta, so its assignment doesn't matter. Samples to the left are closer to $q_i$, samples to the right closer to $q_{i+1}$. The boundary that minimizes distortion is simply the midpoint:

Now fix the boundaries $t_i$ and ask: where should the quantum $q_i$ sit inside its interval $[t_{i-1}, t_i)$? The value that minimizes the total squared error for samples in that interval is their probability-weighted average — the conditional expectation:

Neither condition alone gives a complete answer — boundaries depend on quanta and quanta depend on boundaries. Lloyd's insight was to alternate:

Step 0 — Initialize. Pick $N$ starting quanta (randomly, or evenly spaced). Step 1 — Assign. Set each boundary $t_i$ to the midpoint of adjacent quanta (nearest-neighbor rule). Step 2 — Update. Move each quantum $q_i$ to the centroid of the samples in its interval (centroid rule). Repeat Steps 1–2 until the quanta stop moving (convergence).

At every iteration, Step 1 can only decrease (or maintain) $D$ for the current quanta, and Step 2 can only decrease (or maintain) $D$ for the current boundaries. Since $D$ is bounded below by 0, it must converge.

The convergence argument is beautifully simple. Define the distortion $D$ as a function of both the quanta and the boundaries. Each step of the algorithm optimizes one set of variables while holding the other fixed — and each such optimization can only lower $D$ (never increase it). A sequence that is non-increasing and bounded below must converge.

This is not guaranteed to reach the global minimum — the algorithm converges to a local minimum that depends on initialization. Different starting points may yield different solutions. In practice, running the algorithm several times with random initializations and keeping the best result is standard.

Lloyd wrote this paper for signal engineers: the input is a 1D voltage and the goal is minimizing quantization noise. But strip away the signal-processing language and the algorithm is pure geometry:

Given $N$ points and a cloud of data, (1) assign each datum to its nearest point (Voronoi partition), (2) move each point to the centroid of its cell. Repeat.

This is k-means clustering — one of the most used algorithms in machine learning and data science. Lloyd's 1957 unpublished technical report is the origin of the algorithm, though it was independently rediscovered by Forgy (1965) and named "k-means" by MacQueen (1967). The 1982 publication brought it to wider attention and cemented its place in the literature.

Lloyd also showed that as the number of quanta $N$ grows large, his finite-$N$ solution approaches a result known since 1951: the asymptotic density of quanta should be proportional to $p(x)^{1/3}$, where $p(x)$ is the signal's probability density. In other words, a region where the signal is 8 times more likely should get only $8^{1/3} = 2$ times as many quanta — not 8. This cube-root law balances the benefit of fine quantization in dense regions against the diminishing returns of crowding too many quanta there.