Minimax Multiresolution Scalar Quantization

We consider the problem of design and analysis of optimal $L_{\infty}$ (minmax) multi-resolution scalar quantizers (MRSQ). The overall multi-resolution $L_{\infty}$ distortion of an MRSQ is defined to be a weighted sum of $L_{\infty}$ distortions over all refinement levels of the MRSQ. The weight for a refinement level usually denotes the probability that the MRSQ will operate at that level (rate). An interesting relation of the problem to the design of optimal binary prefix codes under a code cell contiguity constraint is established. Lower bounds for the overall multi-resolution $L_{\infty}$ distortion are derived based on this relation. Provably optimal as well as fast, near optimal algorithms are also developed for practically interesting scenarios. Furthermore, the performance penalty incurred by making a scalable quantizer embedded (progressively refinable) is analyzed. It is shown that constraining the quantizers to be embedded would on average increase the $L_{\infty}$ quantization error by at least 44fo.