Tracking the best quantizer

In this paper we consider zero delay lossy coding schemes for individual sequences, and address the problem of tracking the best scalar quantizer which is adaptively matched to the sequence. The problem is an individual-sequence version of the problem of scalar quantization of piecewise stationary sources. A randomized algorithm is presented which can perform, on any source sequence, asymptotically as well as the best scalar quantization algorithm matched to the sequence which is allowed to change the employed quantizer from time to time. The complexity of the algorithm is quadratic in the sequence length. At the price of a slight deterioration of performance, the complexity can be made linear in the sequence length