### Quantization of a bunch of scalar variables

You have a few uniformly distributed independant scalar variables, how do you optimally quantize them? Simply each independantly by uniform scalar quantization, wrong this is likely to the surprise of the reader not optimal.

One way to see the suboptimality is to look at what independantly uniform scalar quantization does if we have 2 variables, it splits the plane in squares and represents all points within a square by its center. How can we do better? just split the plane in hexagons, both worst case and average quantization error decreases. The worst case for the square is 2^0.5/2=~0.7071, the worst case for the hexagon is 12^0.25/3=~0.6204

Another way to see the suboptimality is to look at the worst case point, which in case of the square lies equidistant to the centers of 4 squares but with a hexagon it just lies equidistant to 3 centers of 3 hexagons. So there are just 3 redundant ways to quantize it instead of 4

If we consider the (uniform scaler) quantization of the first variable of 2 then we can simply improve the worst case which lies exactly between 2 values of the first variable by making use of the useless least significant bit. More exactly add half a quantization step to the second variable if the first was quantized to an odd value, this interrestingly turns out to be equivalent to using hexagons for quantization, though the hexagons are a little squished here compared to the optimal case with regular hexagons

Ive also written a little test program in case anyone wants to play with this quantization stuff

You write “uniformly distributed”, but from a first glance at the sample program you are using rand() to generate the test data. Or am i missing something?

Comment by mark cox — June 7, 2007 @ 4:16

rand()s output has a (discrete) uniform distribution or at least its supposed to have

Comment by Michael — June 7, 2007 @ 12:12

Can I extrapolate that the optimal basis for quantizing N independent uniform random variables is equivalent to N-dimensional sphere packing?

Comment by pengvado — June 11, 2007 @ 19:10

>Can I extrapolate that the optimal basis for quantizing N independent uniform random variables

>is equivalent to N-dimensional sphere packing?

iam not sure

i think its true for R^1-3, but its not if the space is bounded

but this is certainly a very interresting question

Comment by Michael — June 12, 2007 @ 10:03