Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising

Abstract

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.

arXiv comment22 pages, submitted to IEEE transactions on information theory

Cited by in corpus (1)

• On the equivalence between minimal sufficient statistics, minimal typical models and initial segments of the Halting sequence