skip to Main Content

University of Hawaii

Electrical Engineering

Lossy Compression of Memoryless Sources

Date: 2016-11-30           Add to Google Calendar
Time: 4:00pm - 5:00pm
Location: Holmes Hall 389
Speaker: Maryam Hosseini, PhD student, University of Hawaiʻi Electrical Engineering

We consider the problem of lossy compression of memoryless sources. Unlike lossless compression, there is no optimal polynomial time algorithm for lossy case. We propose codelet parsing, a lossy compression algorithm, and investigate its compression rate and time complexity. Codelet parsing is extension of the Lempel Ziv algorithm subject to a fidelity criterion. It splits the input sequence naturally into phrases, representing each phrase by a codelet, a potentially distorted phrase of the same length. The codelets in the lossy representation of a length-n string x have length roughly (log n)/r(d). We use  “strong match" as the key part of the extension. We then demonstrate its compression rate and time complexity via simulation.