Making the correct mistakes

Abstract

We propose a new sequential, adaptive, quadratic-time algorithm for variable-rate lossy compression of memoryless sources at a fixed distortion. The algorithm uses approximate pattern matching and is modeled after the Lempel-Ziv algorithm. As a key new idea, the algorithm uses lower mutual information to carefully select "good" codewords. For Bernoulli sources with Hamming distortion, we empirically demonstrate that the algorithm (a) discovers the optimal reproduction type, (b) leads to absence of multiple matches, and (c) seems to approach the rate-distortion coding rate. Based on empirical observations, we formulate two conjectures that could imply that the algorithm is asymptotically optimal for memoryless sources.