Rate Distortion and Denoising of Individual Data Using Kolmogorov complexity

Details Rate Distortion and Denoising of Individual Data Using Kolmogorov complexity Rate Distortion and Denoising of Individual Data Using Kolmogorov complexity

2004-11-07

arxiv.org/abs/cs/0411014v4

Computer Science

Information Theory

LaTex, 31 pages, 2 figures. The new version is again completely rewritten, newly titled, and adds new results

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Rate Distortion and Denoising of Individual Data Using Kolmogorov complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Rate Distortion and Denoising of Individual Data Using Kolmogorov complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rate Distortion and Denoising of Individual Data Using Kolmogorov complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-25203