Vector Quantizes Trained on Small Training Sets

We examine how the performance of a memoryless vector quantizer (VQ) changes as a function of its training set size. By relating the training distortion of such a codebook to its test (true) distortion, we demonstrate that one may obtain "good" codebooks at a fraction of the computational cost by training on a small random subset of the blocks in the target image.