The minimax distortion redundancy in empirical quantizer design

Peter Bartlett, Tamas Linder and Gabor Lugosi

Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra

Abstract: We obtain minimax lower and upper bounds for the expected distortion redundancy of empirically designed vector quantizers. We show that the mean squared distortion of a vector quantizer designed from $n$ 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 ${\cal R}^d$. Together with existing upper bounds this result shows that the minimax distortion redundancy for empirical quantizer design, as a function of the size of the training data, is asymptotically on the order of $n^{1/2}$. We also derive a new upper bound for the performance of the empirically optimal quantizer.

Keywords: Estimation; hypothesis testing; statistical decision theory: operations research (search for similar items in EconPapers)
JEL-codes: C13 C14 (search for similar items in EconPapers)
Date: 1997-01
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://econ-papers.upf.edu/papers/198.pdf Whole Paper (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:upf:upfgen:198

Access Statistics for this paper

More papers in Economics Working Papers from Department of Economics and Business, Universitat Pompeu Fabra
Bibliographic data for series maintained by (william.carlson@upf.edu this e-mail address is bad, please contact repec@repec.org).