Rate Distortion and Denoising of Individual Data Using Kolmogorov complexity
<|reference_start|>Rate Distortion and Denoising of Individual Data Using Kolmogorov complexity: We examine the structure of families of distortion balls from the perspective of Kolmogorov complexity. Special attention is paid to the canonical rate-distortion function of a source word which returns the minimal Kolmogorov complexity of all distortion balls containing that word subject to a bound on their cardinality. This canonical rate-distortion function is related to the more standard algorithmic rate-distortion function for the given distortion measure. Examples are given of list distortion, Hamming distortion, and Euclidean distortion. The algorithmic rate-distortion function can behave differently from Shannon's rate-distortion function. To this end, we show that the canonical rate-distortion function can and does assume a wide class of shapes (unlike Shannon's); we relate low algorithmic mutual information to low Kolmogorov complexity (and consequently suggest that certain aspects of the mutual information formulation of Shannon's rate-distortion function behave differently than would an analogous formulation using algorithmic mutual information); we explore the notion that low Kolmogorov complexity distortion balls containing a given word capture the interesting properties of that word (which is hard to formalize in Shannon's theory) and this suggests an approach to denoising; and, finally, we show that the different behavior of the rate-distortion curves of individual source words to some extent disappears after averaging over the source words.<|reference_end|>
@article{vereshchagin2004rate,
    title={Rate Distortion and Denoising of Individual Data Using Kolmogorov
  complexity},
    author={Nikolai K. Vereshchagin (Moscow State Univ.), Paul M.B. Vitanyi (CWI
  and University of Amsterdam)},
    journal={arXiv preprint arXiv:cs/0411014},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0411014},
    primaryClass={cs.IT math.IT}
}