I am working on a speech/image compression problem and reduced it to the following problem with normal distributions.  Assume normal distribution with zero mean and unit variance throughout.  The vector quantization problem is to represent a given sample by a m-bit number.  Assuming m to be 1, the problem consists of arranging the given sample with other samples of the same kind into a n-tuple (possible in this application because data consists of a long stream of these samples) and finding the nearest neighbor (in terms of Euclidean distance) in a previously collected database of 2^n samples.  (2^ n stands for 2 raised to the power of n).  Thus when n = 10, we are looking into 1024 10-tuples of gaussian samples to match the given 10-tuple.  Shannon gives a bound (rate distortion theory) of –log D bits for a given root mean squared error distortion D.  His bound gives a root mean squared error distortion of 0.368 (or mean squared error of 0.135) but my computer simulations indicate:

            # of Bits      Vector Length (n)   Distortion (root mean squared error)

                  1                     10                        0.5762

                  1                     15                        0.5595

                  1                     20                       0.5485

I am nowhere closer to Shannon’s bound of 0.368 (which I would like to get).  Note even for a modest length of 20, I have to look into 1 million samples of 20-tuples.  In speech at 8 KHz sampling rate, 20 samples take only 2.5 milliseconds implying a search involving 400 million 20-tuple matches per second.  I would like to venture into longer sequences with hardware and software solutions but would like to have a priori estimates on the error bounds.   In case you are wondering if this is all theoretical and no practical implications, I would like to say that for quality audio and video transmission over the internet these are relevant problems.

My question is that the basic problem can be reduced to statistical terms, concepts and distributions (like chi-square distributions, minimum norm vectors) and whether there are statistical contributions on this subject such as the dependence of the distortion on the block length.  Is it possible to derive an explicit relationship between distortion, number of bits and vector length for gaussian distributions ?

Responses can be directed to ReddiSS@AOL.COM.