Near-Optimal Rates for Limited-Delay Universal Lossy Source Coding

作者：Gyoergy Andras; Neu Gergely

来源：IEEE Transactions on Information Theory, 2014, 60(5): 2823-2827.

DOI：10.1109/TIT.2014.2307062

We consider the problem of limited-delay lossy coding of individual sequences. Here the goal is to design (fixed-rate) compression schemes to minimize the normalized expected distortion redundancy relative to a reference class of coding schemes, measured as the difference between the average distortion of the algorithm and that of the best coding scheme in the reference class. In compressing a sequence of length T, the best schemes available in the literature achieve an O (T-1/3) normalized distortion redundancy relative to finite reference classes of limited delay and limited memory. It has also been shown that the distortion redundancy is at least of order 1 / root T in certain cases. In this paper we narrow the gap between the upper and lower bounds, and give a compression scheme whose distortion redundancy is O (root ln(T)/T), only a logarithmic factor larger than the lower bound. The method is based on the recently introduced Shrinking Dartboard prediction algorithm, a variant of the exponentially weighted average prediction. Our method is also applied to the problem of zero-delay scalar quantization, where O (ln(T) / root T) distortion redundancy is achieved relative to the (infinite) class of scalar quantizers of a given rate, almost achieving the known lower bound of order 1 / root T

• 出版日期2014-5