We study the potential merits of vector quantization and show that there can be an arbitrary discrepancy between the worst-case rate required for scalar and vector quantization. Specifically, we show that for every delta, however large, and every epsilon > 0, however small, there is a random variable and a distortion measure where quantization of a single instance within a given distortion requires more than delta bits in the worst case, but quantization of multiple independent instances within the same distortion requires at most epsilon bits per instance in the worst case. Furthermore, these discrepancies can be achieved by simple distortion measures that attain just two values: 0 and infinity.

For more information, see his website at http://www-ece.ucsd.edu/~alon/.