Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising
Abstract
Description
Classical rate-distortion theory requires knowledge of an elusive source distribution. Instead, we analyze rate-distortion properties of individual objects using the recently developed algorithmic rate-distortion theory. The latter is based on the noncomputable notion of Kolmogorov complexity. To apply the theory we approximate the Kolmogorov complexity by standard data compression techniques, and perform a number of experiments with lossy compression and denoising of objects from different domains. We also introduce a natural generalization to lossy compression with side information. To maintain full generality we need to address a difficult searching problem. While our solutions are therefore not time efficient, we do observe good denoising and compression performance.
22 pages, submitted to IEEE transactions on information theory
22 pages, submitted to IEEE transactions on information theory