THE MINIMAX DISTORTION REDUNDANCY IN EMPIRICAL QUANTIZER DESIGN

We obtain minimax lower and upper bounds for the expected distortion r edundancy of empirically designed vector quantizers. We show that the mean-squared distortion of a vector quantizer designed from n independ ent and identically distributed (i.i.d.) data points using any design algorithm is at least Omega(n(-1/2)) away from the optimal distortion for some distribution on a bounded subset of R-d. Together with existi ng upper bounds this result shows that the mininax distortion redundan cy for empirical quantizer design, as a function of the size of the tr aining data, is asymptotically on the order of n(-1/2). We also derive a new upper bound for the performance of the empirically optimal quan tizer.