Distortion bounds for vector quantizers with finite codebook size

Upper and lower bounds are presented for the distortion of the optimal N-po int vector quantizer applied to k-dimensional signals. Under certain smooth ness conditions on the source distribution, the bounds are shown to hold fo r each and every value of N, the codebook size. These results extend hounds derived in the high-resolution limit, which assumes that the number of cod e vectors is arbitrarily large. Two approaches to the upper bound are prese nted. The first, constructive construction, achieves the correct asymptotic rate of convergence as well as the correct dependence on the source densit y, although leading to an inferior value for the constant. The second const ruction, based on a random coding argument, is shown to additionally achiev e a value of the constant which is much closer to the best known result der ived within the asymptotic theory. Lower bound results derived in the corre spondence are again shown to possess the correct asymptotic form and yield a constant which is almost indistinguishable from the best value achieved i n the asymptotic regime. Finally, application of the results to the problem of source coding yields upper bounds on the distortion rate function for a wide class of processes.