10-605 · Randomized algorithms 2 · product quantization

Product quantization in two dimensions

Split each point x = (x, y) into m = 2 subvectors, x(1) = x and x(2) = y, and run J-means separately in each subspace. That stores only 2J one-dimensional centroids, but every pair (c(1), c(2)) is a possible reconstruction c: J2 codewords on a grid. Compare it with ordinary J-means using the same number of codewords (J2) and using the same storage (J two-dimensional centroids). Click any panel to place a point q.

 
 
 

Product quantization

J-means on x and on y separately. Ticks on the axes are the 1-D centroids; the grid is every pair of them.

J-means, same codewords

Ordinary J-means with J² centroids: the same code length as PQ, but J² 2-D centroids to store and search.

J-means, same storage

Ordinary J-means with J centroids: the same 2J stored numbers as PQ, but only J codewords.

point x codeword (reconstruction) 1-D centroid of one subspace error x → c(x) q (click to move)

Side by side

PQJ-means, J²J-means, J

MSE is the mean squared distance ‖x − c(x)‖² over all points (the data fills the unit square). "Codewords used" counts codewords that at least one point maps to: PQ's grid is axis-aligned, so when the data runs diagonally many grid cells are empty.

Algorithm

Train:
  for z = 1, …, m:                       here m = 2: z = x-axis, y-axis
    run J-means on {x(z) : x in D} → centroids c1(z),…,cJ(z)
Encode x:
  for z = 1, …, m:
    jz = argminj ‖x(z) − cj(z)‖          J distance computations
  code = (j1,…,jm)                       m·log₂J bits, Jm possible codes
  c(x) = cj1(1) … cjm(m)