Universal multiresolution source codes

A multiresolution source code is a single code giving an embedded source de scription that can be read at a variety of rates and thereby yields reprodu ctions at a variety of resolutions. The resolution of a source reproduction here refers to the accuracy with which it approximates the original source . Thus, a reproduction with low distortion is a "high-resolution" reproduct ion while a reproduction with high distortion is a "low-resolution" reprodu ction. This paper treats the generalization of universal lossy source codin g from single-resolution source codes to multiresolution source codes. Resu lts described in this work include new definitions for weakly minimax unive rsal, strongly minimax universal, and weighted universal sequences of fixed - and variable-rate muitiresolution source codes that extend the correspond ing notions from lossless coding and (single-resolution) quantization to mu ltiresolution quantizers. A variety of universal multiresolution source cod ing results follow, including necessary and sufficient conditions for the e xistence of universal multiresolution codes, rate of convergence bounds for universal multiresolution coding performance to the theoretical bound, and a new multiresolution approach to two-stage universal source coding.