Kolmogorov Entropy 1.1 2007/07/16 12:20:42.648 GMT-5 2007/09/21 18:47:53.865 GMT-5 Ronald A. DeVore devore@math.sc.edu Shriram Sarvotham shri@rice.edu Elchin Asgarov deoxman@gmail.com Raymond Wagner rwagner@rice.edu Richard G. Baraniuk richb@rice.edu Mark Davenport md@rice.edu Ronald A. DeVore devore@math.sc.edu Shriram Sarvotham shri@rice.edu

Coverings of K by balls of radius ϵ.

Given ϵ>0, and the compact set K, consider all coverings of K by balls of radius ϵ, as shown in . In other words, K⊆U i=1 N b(f i ,ϵ). Let N ϵ :=inf{N:overallsuchcovers}. N ϵ (K) is called the covering number of K. Since it depends on X and K, we write it as N ϵ =N ϵ (K,X). Kolmogorov entropy The Kolmogorov entropy, denoted by H ϵ (K,X), of the compact set K in X is defined as the logarithm of the covering number: H ϵ (K,X)=logN ϵ (K,X). The Kolmogorov entropy solves our problem of optimal encoding in the sense of the following theorem. For any compact set K⊂X, we have n ϵ (K,X)=⌈H ϵ (K,X)⌉, where ⌈·⌉ is the ceiling function. Sketch: We can define an encoder-decoder as follows To encode: Say f∈K. Just specify which ball it is covered by. Because the number of balls is N ϵ (K,X ̲ ¯), we need at most ⌈logN ϵ (K,X ̲ ¯)⌉ bits to specify any such ball ball. To decode: Just take the center of the ball specified by the bitstream. It is now easy to see that this encoder-decoder pair is optimal in either of the senses given above. □ The above encoder is not practical. However, the Kolmogorov entropy tells us the best performance we can expect from any encoder-decoder pair. Kolmogorov entropy is defined in the deterministic setting. It is the analogue of the Shannon entropy which is defined in a stochastic setting.