One codebook, and the wall

1Replace each vector by its nearest representative

Pick $K$ representative vectors, the codebook $\{\kbook{c_1},\dots,\kbook{c_K}\}$ . Replace each data point by the index of its nearest representative.

Store the index, the code: $\log_2 K$ bits.
Decode by looking the index up.
Train with k-means, which finds the representatives that minimise squared error.

This is vector quantization (VQ).

Fig 4.1.1One codebook: bits against error

Slide the bits Each extra bit doubles $K$ . On the right, error on a log scale. In two dimensions each bit roughly halves the error once $K$ is large; the dashed line is that slope.

VQ in numpy: encode = nearest neighbour, decode = lookupnumpy

def nearest(X, C):
    # ||x-c||² = ||x||² - 2x·c + ||c||²; drop ||x||², it doesn't move the argmin
    return (-2 * X @ C.T + (C ** 2).sum(1)).argmin(1)

codes = nearest(X, C)      # encode: log2(K) bits per row
X_hat = C[codes]           # decode: a table lookup

2The wall: bits per dimension

The right-hand plot hides a law. With a good codebook, distortion falls exponentially with the rate $R$ in bits per vector, but the exponent is divided by the dimension:

\kres{D}(R) \;\approx\; c \cdot 2^{-2\,\kbits{R}/d}

In two dimensions, one bit halves the error, which is what you saw. Now put in Marginalia’s $d = 384$ :

one bit shrinks the error by $2^{-2/384} \approx 0.996$ ;
getting anywhere useful takes dozens of bits per vector;
dozens of bits means $K = 2^{64}$ or more.

A codebook that size:

cannot be stored (18 quintillion vectors);
cannot be trained (k-means needs many more points than centroids);
cannot be searched when encoding (finding the nearest of $2^{64}$ entries is the very problem we were trying to make cheap).

VQ, SMALL Kdistortion highencode K·ddecode one lookuphuge K impossible

Can we have a gigantic codebook without storing it, and still find good entries in it?

The question that drives the rest of this part.