Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising
<|reference_start|>Approximating Rate-Distortion Graphs of Individual Data: Experiments in Lossy Compression and Denoising: 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.<|reference_end|>
@article{de rooij2006approximating,
    title={Approximating Rate-Distortion Graphs of Individual Data: Experiments in
  Lossy Compression and Denoising},
    author={Steven de Rooij and Paul Vitanyi},
    journal={arXiv preprint arXiv:cs/0609121},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0609121},
    primaryClass={cs.IT math.IT}
}