Minimax multiresolution scalar quantization

We consider the problem of design and analysis of optimal L_∞ (minmax) multiresolution scalar quantizers (MRSQ). The overall multiresolution L_∞ distortion of an MRSQ is denned to be a weighted sum of L_∞ 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 multiresolution L_∞ 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_∞ quantization error by at least 44%.