Computer Science – Information Theory
Scientific paper
2009-04-21
Computer Science
Information Theory
23 pages, four figures, four tables
Scientific paper
The compression-complexity trade-off of lossy compression algorithms that are based on a random codebook or a random database is examined. Motivated, in part, by recent results of Gupta-Verd\'{u}-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). The optimality of LLZ for memoryless sources is established, and its performance is compared 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-and-conquer idea of GVW and the single-database structure of LLZ. It is proved that HYB shares with GVW the exact same rate-distortion performance and implementation complexity, while, like LLZ, requiring less memory, by a factor which may become unbounded, depending on the choice or the relevant design parameters. Experimental results are also presented, illustrating the performance of all three methods on data generated by simple discrete memoryless sources. In particular, the HYB algorithm is shown to outperform existing schemes for the compression of some simple discrete sources with respect to the Hamming distortion criterion.
Gioran Chris
Kontoyiannis Ioannis
No associations
LandOfFree
Lossy Compression in Near-Linear Time via Efficient Random Codebooks and Databases does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Lossy Compression in Near-Linear Time via Efficient Random Codebooks and Databases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lossy Compression in Near-Linear Time via Efficient Random Codebooks and Databases will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-274487