Title :
Near-optimal rates for limited-delay universal lossy source coding
Author :
György, András ; Neu, Gergely
Author_Institution :
Machine Learning Res. Group, Hungarian Acad. of Sci., Budapest, Hungary
fDate :
July 31 2011-Aug. 5 2011
Abstract :
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=√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(√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)=√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=√T.
Keywords :
distortion; quantisation (signal); redundancy; source coding; average distortion; exponentially weighted average prediction; limited memory; limited-delay lossy coding; logarithmic factor; near-optimal rates; normalized expected distortion redundancy; sequence compression; shrinking dartboard prediction; universal lossy source coding; zero-delay scalar quantization; Decoding; Delay; Distortion measurement; Prediction algorithms; Redundancy; Source coding;
Conference_Titel :
Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on
Conference_Location :
St. Petersburg
Print_ISBN :
978-1-4577-0596-0
Electronic_ISBN :
2157-8095
DOI :
10.1109/ISIT.2011.6033954