The investigators perform a systematic study of issues related to the tradeoffs between dimension and rate in vector quantization. They investigate the compression gains achievable by simultaneous quantization of a block of data over scalar quantization. Theoretical limits on the savings, rates of convergence, and algorithms achieving them are sought for worst-case as well as average-case performance criteria. Special consideration is given to "combinatorial" distortion measures that attain only two values: zero or infinity. These measures allow only certain types of errors and are important in applications where some mistakes cannot be tolerated. These measures are simpler to analyze, yet display many of the complexities of general measures.
