A Lower Bound on the Average Error of Vector Quantizers

J. H. Conway(*)
Department of Pure Mathematics and Mathematical Statistics
University of Cambridge
Cambridge, CB2 1SB, England

N. J. A. Sloane(**)
Mathematical Sciences Research Center
AT&T Bell Laboratories
Murray Hill, NJ 07974, USA

ABSTRACT

A lower bound is proposed for the mean squared error of an n-dimensional
vector quantizer with a large number of output points.
Although no formal proof has been found, a plausible geometrical argument
is given for believing that the bound is correct.

The new bound is analogous to the Rogers bound for packing spheres, the
Coxeter-Few-Rogers bound for covering space with spheres,
and the Coxeter-Boroczky bound for packing spherical caps.
It is significantly stronger than Zador's sphere bound for quantizers.


(*) Present address:
Mathematics Department
Princeton University,
Princeton, NJ 08540

(**) Present address:
Information Sciences Research
AT&T Shannon Lab
Florham Park, NJ 07932-0971



For the full version see
http://www.research.att.com/~njas/doc/low.pdf (pdf) or
http://www.research.att.com/~njas/doc/low.ps (ps)
For the figures see the files 
http://www.research.att.com/~njas/doc/lowfig1.JPG
http://www.research.att.com/~njas/doc/lowfig2.JPG
http://www.research.att.com/~njas/doc/lowfig3.JPG


This paper was published (in a somewhat different form) in
IEEE Trans. Information Theory, 31 (1985), 106-109.