CUED Publications database

Efficient random codebooks and databases for lossy compression in near-linear time

Kontoyiannis, I and Gioran, C (2009) Efficient random codebooks and databases for lossy compression in near-linear time. In: UNSPECIFIED pp. 236-240..

Full text not available from this repository.


We examine the compression-complexity trade-off of lossy compression algorithms that are based on a random codebook or a random database. Motivated, in part, by some recent results of Gupta-Verdù-Weissman (GVW) and their underlying connections with the pattern-matching scheme of Kontoyiannis' lossy Lempel-Ziv algorithm, we introduce a non-universal version of the lossy Lempel-Ziv method (termed LLZ), we prove its optimality for memoryless sources, and we compare its performance to that of the GVW divide-and-conquer approach. Experimental results indicate that the GVW approach often yields better compression than LLZ, but at the price of much higher memory requirements. To combine the advantages of both, we introduce a hybrid algorithm (HYB) that utilizes both the divide-andconquer idea of GVW and the single-database structure of LLZ. We show that HYB shares with GVW the exact same ratedistortion performance and implementation complexity, while, like LLZ, requiring much less memory, typically by at least one or two orders of magnitude. Experimental results are also presented, illustrating the performance of all three methods on data generated by simple discrete memoryless sources. In particular, the HYB scheme is shown to outperform existing schemes for the compression of some simple discrete sources with respect to the Hamming distortion criterion. © 2009 IEEE.

Item Type: Conference or Workshop Item (UNSPECIFIED)
Divisions: Div F > Signal Processing and Communications
Depositing User: Cron Job
Date Deposited: 08 Jan 2018 20:12
Last Modified: 27 Oct 2020 07:13
DOI: 10.1109/ITWNIT.2009.5158578