On $L_{\infty}$ Properties of Multiresolution Scalar Quantizers

We investigate the max-norm $(L_{\infty})$ properties of multiresolution scalar quantizers (MRSQ). The multiresolution requirement imposes nontrivial constraints on the maximum distortion at each level of the quantizer. To quantify these constraints, we define the overall multiresolution $L_{\infty}$ distortion of an MRSQ to be a weighted sum of $L_{\infty}$ distortions over all refinement levels of the MRSQ. We then seek MRSQ constructions that minimize this average-max distortion measure. An interesting relationship between this problem and the structure of Huffman code trees is established. Lower bounds for the average-max distortion are derived based on this relationship. The derivation of these lower bounds also lead to efficient dynamic programming heuristic solutions.