  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.
