Epsilon-entropy

Epsilon - entropy or ε-entropy - a term introduced by A. N. Kolmogorov to characterize classes of functions. It determines the measure of the complexity of the function , the minimum number of characters required to set the function with accuracy $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ .

Introduction to the concept

Consider a compact metric space. $M$ ${\ displaystyle M}$ and define an epsilon network in it, that is, such a finite one (consisting of $N(\varepsilon )$ ${\ displaystyle N (\ varepsilon)}$ dots) set that the radius balls $\varepsilon$ ${\ displaystyle \ varepsilon}$ with centers at these points entirely cover everything $M$ ${\ displaystyle M}$ . Then to set any element $M$ ${\ displaystyle M}$ with precision $\varepsilon$ ${\ displaystyle \ varepsilon}$ (that is, in fact, the choice of one of the network nodes) is enough order $\log _{2}N(\varepsilon )$ ${\ displaystyle \ log _ {2} N (\ varepsilon)}$ characters ( bits ).

For the segment $M=[0,\;1]$ ${\ displaystyle M = [0, \; 1]}$ magnitude $N$ ${\ displaystyle N}$ grows with decreasing $\varepsilon$ ${\ displaystyle \ varepsilon}$ as $1/\varepsilon$ ${\ displaystyle 1 / \ varepsilon}$ for a square like $1/{\varepsilon ^{2}}$ ${\ displaystyle 1 / {\ varepsilon ^ {2}}}$ etc. Thus, the indicator determines the dimension of the Minkowski set $M$ ${\ displaystyle M}$ .

In the case of space $M$ ${\ displaystyle M}$ smooth functions (on a compact cube in $n$ ${\ displaystyle n}$ -dimensional space and with bounded constant derivatives to order $p$ ${\ displaystyle p}$ so that this space is compact) the dimension of space is infinite, but the number $N(\varepsilon )$ ${\ displaystyle N (\ varepsilon)}$ network elements of course, although it grows faster than any (negative) degree of magnitude $\varepsilon$ ${\ displaystyle \ varepsilon}$ .

Kolmogorov proved that the logarithm of $N(\varepsilon )$ ${\ displaystyle N (\ varepsilon)}$ minimum points $\varepsilon$ ${\ displaystyle \ varepsilon}$ -network grows in this case as $(1/\varepsilon )^{n/p}$ ${\ displaystyle (1 / \ varepsilon) ^ {n / p}}$ .

Application

The introduction of the concept of epsilon-entropy allowed us to understand and solve the 13th problem of Hubert .

Had functions $k$ ${\ displaystyle k}$ the variables involved in the superposition had smoothness $p$ ${\ displaystyle p}$ , then with their help it would be possible to obtain a network for the functions being represented, the logarithm of the number of points of which would be of the order $(1/\varepsilon )^{k/p}$ ${\ displaystyle (1 / \ varepsilon) ^ {k / p}}$ . If this number is less than the minimum possible for functions $n$ ${\ displaystyle n}$ smoothness variables $p$ ${\ displaystyle p}$ , it means that the assumed representation by superpositions of functions of such a large smoothness is impossible.

Then Kolmogorov showed that if we abandon smoothness and allow all continuous functions to participate in superposition, then any continuous function of $n$ ${\ displaystyle n}$ variables is represented by a superposition of continuous functions of only three variables, and then his student, V. I. Arnold, presented them as superpositions of continuous functions of two variables. As a result, Kolmogorov's theorem contained a single function of two variables — the sum, and all the other continuous functions, from which the representation representing all continuous functions of $n$ ${\ displaystyle n}$ variable superposition, each depends on only one variable.

Epsilon-entropy

Introduction to the concept

Application

More articles: