Pl. Bartlett et al., THE MINIMAX DISTORTION REDUNDANCY IN EMPIRICAL QUANTIZER DESIGN, IEEE transactions on information theory, 44(5), 1998, pp. 1802-1813
Citations number
23
Categorie Soggetti
Computer Science Information Systems","Engineering, Eletrical & Electronic","Computer Science Information Systems
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.