# Epsilon-entropy

of a set in a metric space

The logarithm to the base 2 of the smallest number of points in an $\epsilon$- net for this set. In other words, the $\epsilon$- entropy ${\mathcal H} _ \epsilon ( C , X )$ of a set $C$ lying in a metric space $( X , \rho )$ is

$${\mathcal H} _ \epsilon ( C , X ) = \ \mathop{\rm log} _ {2} N _ \epsilon ( C , X ) ,$$

where

$$N _ \epsilon ( C , X ) = \inf \left \{ {n } : { \exists x _ {1} \dots x _ {n} , x _ {i} \in X :\ C \subset \cup _ { i= } 1 ^ { n } B ( x _ {i} , \epsilon ) } \right \}$$

and $B ( \zeta , \alpha ) = \{ {x \in X } : {\rho ( x , \zeta ) \leq \alpha } \}$ is a ball of radius $\alpha$ with centre at $\zeta$. The definition of ${\mathcal H} _ \epsilon ( C , X )$ was given by A.N. Kolmogorov in , motivated by ideas and definitions of information theory (cf. Information theory). ${\mathcal H} _ \epsilon ( C , X )$ is also called the relative $\epsilon$- entropy; it depends on the space $X$ in which the set $C$ is situated, that is, on the metric extension of $C$. The quantity

$${\mathcal H} _ \epsilon ( C) = \inf {\mathcal H} _ \epsilon ( C , X ) ,$$

where the infimum is taken over all metric extensions $X$ of $C$, is called the absolute $\epsilon$- entropy of $C$. It may also be defined directly (Kolmogorov, ): for a metric space $C$, ${\mathcal H} _ \epsilon ( C)$ is the logarithm to the base 2 of the cardinality $N _ \epsilon ( C)$ of the most economic (by the number of sets) $2 \epsilon$- covering of $C$. Here a system of sets $\{ C _ {i} \}$ is called a $2 \epsilon$- covering of $C$ if $C _ {i} \subset C$, $\cup _ {i=} 1 ^ {n} C _ {i} = C$ and the diameter of each set does not exceed $2 \epsilon$. It has been shown  that the absolute $\epsilon$- entropy is the minimum relative $\epsilon$- entropy. The quantities $N _ \epsilon ( C)$ and $N _ \epsilon ( C , X )$ are inverse to the widths (cf. Width) $\epsilon ^ {N} ( C)$ and $\epsilon _ {N} ( C , X )$. This characterizes the fact that it is possible to recover the elements of $C$ from tables of $N$ elements and to approximate by $N$- point sets.

The investigation of the asymptotic behaviour of the $\epsilon$- entropy of various function classes is a special branch of approximation theory.

How to Cite This Entry:
Epsilon-entropy. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Epsilon-entropy&oldid=50801
This article was adapted from an original article by V.M. Tikhomirov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article