1.2 Kolmogorov entropy

Given $ϵ>0$ , and the compact set $K$ , consider all coverings of $K$ by balls of radius $ϵ$ , as shown in . In other words,

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:

The Kolmogorov entropy solves our problem of optimal encoding in the sense of the following theorem.

For any compact set $K\subset X$ , we have $n_{ϵ}(K,X)=\lceil H_{ϵ}(K,X)\rceil$ , where $\lceil ·\rceil$ is the ceiling function.

Sketch: We can define an encoder-decoder as follows To encode: Say $f\in K$ . Just specify which ball it is covered by. Because the number of balls is $N_{ϵ}(K,\overline{\underline{X}})$ , we need at most $\lceil log{N}_{ϵ}(K,\overline{\underline{X}})\rceil$ 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. $\square$

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.