Width

of a set

A value characterizing the deviation of a set in a metric space and a system of (as a rule, finite-dimensional) objects using a certain method of approximation. It also measures the accuracy with which an element from the given set can be recovered using certain coding techniques. Widths measuring the possibility of approximating a set by finite-dimensional compacta (width according to Aleksandrov) and finite-dimensional linear manifolds (width according to Kolmogorov) are the ones most widely studied.

Let $ X $ be a normed space with unit ball $ B $, let $ C \subset X $ be a to-be-approximated subset of it, let $ \mathfrak A = \{ A \} $, $ A \subset X $, be a family of approximating subsets, let $ F ( C , A ) $ be a set of mappings $ f : C \rightarrow A $, and, finally, let $ \mathfrak F = \mathfrak F ( C , \mathfrak A ) = \cup _ {A \in \mathfrak A } F ( C , A ) $. The number

$$ \tag{1 } p _ {\mathfrak F } ( C , X ) = \inf _ {f \in \mathfrak F } \ \sup _ {x \in C } \| x - f ( x) \| $$

measures the deviation of $ C $ from the family of approximating sets $ \mathfrak A $ using the approximation method $ \mathfrak F $.

The majority of widths measuring approximation properties of various approximation methods are given by (1).

If $ \mathfrak A = \mathfrak M _ {N} $ is the set $ \{ M _ {N} \} $ of all linear manifolds (i.e. translates of linear subspaces) of dimension $ \leq N $ and $ F ( C , M _ {N} ) $ is the set of all mappings from $ C $ into $ M _ {N} $, then the expression (1) is called the $ N $- width according to Kolmogorov of the set $ C $. It is usually denoted by $ d _ {N} ( C , X ) $, and measures the minimal deviation of a given set $ C $ from $ N $- dimensional linear manifolds. Other, equivalent and generally accepted, definitions of $ d _ {N} $ are the following (see [1]):

$$ \tag{1'} d _ {N} ( C , X ) = \inf _ {\{ M _ {N} \} } \ \sup _ {x \in C } \inf _ {y \in M _ {N} } \ \| x - y \| = $$

$$ = \ \inf _ {\{ M _ {N} \} } \inf _ {\epsilon } \{ \epsilon > 0 : C \subset M _ {N} + \epsilon B \} . $$

If $ \mathfrak A = \mathfrak M _ {N} $( or $ = \mathfrak L _ {N} $, the set of all subspaces $ \{ L _ {N} \} $ of dimension $ \leq N $) and $ F ( C , M _ {N} ) $( $ F ( C , L _ {N} ) $) is the set of all affine (linear) continuous mappings of $ C $ into $ M _ {N} $( $ L _ {N} $), then the quantity (1) is denoted by $ \alpha _ {N} ( C , X ) $( $ \lambda _ {N} ( C , X ) $) and is called the affine (linear) $ N $- width. It measures the approximation properties by affine (linear) $ N $- dimensional mappings.

If $ \mathfrak A = \mathfrak K _ {N} $ is the set $ \{ K _ {N} \} $ of all $ N $- dimensional compacta (equivalently, of all $ N $- dimensional polyhedra) and $ F ( C , K _ {N} ) $ is the set of all continuous mappings from $ C $ into $ K _ {N} $, then (1) is called the $ N $- width according to Aleksandrov; it is denoted by $ a _ {N} ( C , X ) $. It measures the degree of approximation of the set $ C $ by $ N $- dimensional compacta.

If $ \mathfrak A = \Sigma _ {N} $ is the set $ \{ \xi _ {N} \} $ of all $ N $- point sets $ \xi _ {N} = \{ x _ {1} \dots x _ {N} \} $ of $ X $, and $ F ( C , \xi _ {N} ) $ is the set of all mappings from $ C $ into $ \xi _ {N} $, then the width (1) is denoted by $ \epsilon _ {N} ( C , N ) $. It measures the minimal deviation of $ C $ from $ N $- point sets.

All above-mentioned approximate widths depend on the ambient space $ X $ and can change when $ C $ together with its metric is imbedded in another normed space.

Another class of widths is related to the problem of "coding" the elements of a set $ C $ by elements of another sort. This process is often called the problem of recovering. Let $ C $ be a metric space, let $ Z = \{ \zeta \} $ be a family of "coding" sets, and let $ \phi ( C , \zeta ) $ be a family of mappings $ f: C \rightarrow \zeta $. Finally, let $ \Phi = \Phi ( C , Z ) = \cup _ {\zeta \in Z } \phi ( C , \zeta ) $ be the given set of coding methods. The quantity

$$ \tag{2 } p ^ \Phi ( C) = \inf _ {f \in \Phi } \ \sup _ {z \in f ( C) } D ( f ^ { - 1 } ( z) ) , $$

where $ D ( E) $ denotes the diameter of the set $ E $, measures the recoverability of the elements of $ C $ by the information "coded" by elements of the sets $ \zeta $ from $ Z $ using mappings from $ \Phi $. The majority of widths related to processes of recovering are given by formulas analogous to (2).

If $ \Phi $ is the set of all possible mappings from $ C $ into $ Z $, where $ Z $ consists of the single set $ \{ 1 \dots N \} $, then the width (2), denoted by $ \epsilon ^ {N} ( C) $, measures the accuracy of recovering an element using a table consisting of $ N $ elements. If $ C $ lies in a linear normed space $ X $ and $ \Phi $ is the set of all continuous affine mappings on $ \mathbf R ^ {N} $, then the quantity $ p ^ \Phi ( C) / 2 $, where $ p ^ \Phi ( C) $ is defined by (2), is called the $ N $- width according to Gel'fand and is denoted by $ d ^ {N} ( C) $. It measures the accuracy of recovering the elements by their images under affine mappings on $ \mathbf R ^ {N} $. In the case of sets symmetric with respect to the origin, the widths $ d ^ {N} $ have another equivalent definition:

$$ \tag{2'} d ^ {N} ( C) = \inf _ {\{ N \} } \ \sup _ {x \in C \cap L ^ {N} } \| x \| = $$

$$ = \ \inf _ { N } \sup _ \epsilon \{ \epsilon > 0 : C \cap L ^ {N} \subset \epsilon B \} , $$

where $ L ^ {N} $ is a closed subspace of codimension $ N $. Let $ Z $ consist of all $ N $- dimensional compacta $ \{ K _ {N} \} $, let $ \phi ( C , K _ {N} ) $ be the set of all continuous mappings from $ C $ into $ K _ {N} $, and let $ \Phi = \cup \phi ( C , K _ {N} ) $. Then (2) is called the $ N $- width according to Urysohn and is denoted by $ u _ {N} ( C) $. Another, equivalent and widely used, definition of the Urysohn width is the following: $ u _ {N} ( C) $ is the lower bound of all diameters of covering sets of $ C $ of order $ \leq N + 1 $. The Urysohn width measures the degree of $ N $- dimensionality (from the point of view of Brouwer dimension) of the set $ C $.

The first quantity that later was called a width was introduced in 1923 by P.S. Urysohn (see [2]) when he defined $ u _ {N} $. In 1933 P.S. Aleksandrov [3] established approximative aspects of dimension theory which resulted in defining $ a _ {N} $. In 1933 A.N. Kolmogorov [1] defined $ d _ {N} $; this width was studied in depth in approximation theory. In 1931 L.S. Pontryagin and L.G. Shnirel'man (see [4]) expressed the dimension (a topological characteristic) by an asymptotic metric characteristic $ N _ \epsilon ( C) $( the inverse of $ \epsilon ^ {N} ( C) $), which in a metric space $ C $ equals the least number of elements of a $ 2 \epsilon $- covering of $ C $. Interest in this type of characteristic increased in the 1950's when Kolmogorov [5] introduced $ N _ \epsilon ( C , X ) $( the inverse of $ \epsilon _ {N} ( C , X ) $), based on arguments of information theory, and indicated a program of studying variables like $ N _ \epsilon ( C) $ and $ N _ \epsilon ( C , X ) $ as a specific part of approximation theory related to questions of best tabulation of functions. The binary logarithm of $ N _ \epsilon ( C , X ) $ is called the $ \epsilon $- entropy of the set $ C $, and $ \mathop{\rm log} _ {2} N _ \epsilon ( C) $ is called the absolute $ \epsilon $- entropy of $ C $.

A number of concrete results have been obtained, in which certain widths have been calculated for a number of different classes of functions and geometric objects. These calculations can be divided into two groups: asymptotic and exact.

Some results related to the asymptotic calculation of widths of Sobolev classes are given below. Let $ W _ {p} ^ { r } $ be the set of functions $ x ( \cdot ) $ on a finite interval (e.g. on $ [ 0 , 1] $) having an absolutely continuous $ ( r- 1) $- th order derivative and an $ r $- th order derivative for which

$$ \| x ^ {r} ( \cdot ) \| _ {p} = \left ( \int\limits _ { 0 } ^ { 1 } | x ^ {(r)} ( t) | ^ {p} dt \right ) ^ {1/2} < 1 ,\ p \geq 1 . $$

The following asymptotic formula is valid:

$$ \tag{3 } d _ {N} ( W _ {p} ^ { r } , L _ {q} ) \sim \left \{ \begin{array}{ll} N^{-(r - (1/p-1/q))} & 1 \le q < p \le \infty\ \text{ or }\ 1 \le p \le q \le 2 \\ N^{-(r - (1/p-1/2))} & 1 \le p \le q \le \infty\,,\ q \ge 2 \end{array} \right. $$

For particular cases of the upper row of (3) it follows that the asymptotically best approximating space is the space of trigonometric polynomials or the space of splines with uniformly distributed nodes.

It was conjectured that such asymptotic behaviour always occurs, i.e. the subspace of trigonometric polynomials of a given order is always asymptotically extremal. It has turned out this is not true (see [10], [13]). The set of trigonometric polynomials spanned by $ \{ {\cos nt , \sin nt } : {0 \leq n \leq N } \} $ turned out to be asymptotically non-extremal. However, in a number of cases "rearranged" harmonics, i.e. $ \sim N $ harmonics taken in a "wrong" order, turned out to be extremal.

The solution of the problem of widths of Sobolev classes is based on the problem of diameters for $ n $- octahedrons in $ \mathbf R ^ {n} $:

$$ O _ {p} ^ {n} = \left \{ {x \in \mathbf R ^ {n} } : {\sum _ { i=1} ^ { n } | x _ {i} | ^ {p} \leq 1 } \right \} . $$

For $ p > q $ the quantity $ d _ {N} ( O _ {p} ^ {n} , l _ {q} ^ {n} ) $ has been determined exactly; also, $ d _ {N} ( O _ {1} ^ {n} , l _ {2} ^ {n} ) $ has been calculated exactly: it turned out to be $ ( 1 - N / n ) ^ {1/2} $. The following estimates (see [13]) are of fundamental importance for the calculation of Kolmogorov widths for Sobolev classes:

A) $ d _ {N} ( O _ {1} ^ {n} , l _ \infty ^ {n} ) \leq 2N ^ {- 1/2} ( \mathop{\rm ln} n ) ^ {1/2} $;

B) $ d _ {N} ( O _ {2} ^ {n} , l _ \infty ^ {n} ) \leq AN ^ {- 1/2} ( 1 + \mathop{\rm ln} n / N ) ^ {3/2} $, where $ A $ is a constant;

C) if $ \lambda \in ( 0 , 1 ) $, then for $ n ^ \lambda \leq N \leq n $ the following inequality holds:

$$ d _ {N} ( O _ {1} ^ {n} , l _ \infty ^ {n} ) \leq C _ \lambda N ^ {- 1/2} . $$

The asymptotic behaviour of the Aleksandrov widths for Sobolev classes has been considered as well. It has been shown that

$$ a _ {N} ( W _ {p} ^ { r } , L _ {q} ) \sim \frac{1}{N ^ {r} } \ \ \textrm{ for } 1 < p , q < \infty , r \in \mathbf N . $$

The exact calculation of widths is equivalent to finding extremal approximations for a given class. The first result of this kind was obtained by Kolmogorov [1] who solved the problem of calculating $ d _ {N} ( W _ {2} ^ {r} , L _ {2} [ 0 , 1 ] ) $ and the similar problem for the periodic class $ \widetilde{W} {} _ {2} ^ {r} $ in the metric of $ L _ {2} ( [ - \pi , \pi ] ) $.

Topological methods (the theorem on the width of a sphere reduces to Borsuk's antipodal theorem) were first applied (see ) to determine the exact value of $ d _ {N} ( \widetilde{W} {} _ \infty ^ {r} , L _ \infty [ - \pi , \pi ] ) $. This theorem was generalized (see [12]) and used to obtain other exact solutions. Later some interesting relations with the calculus of variations and optimal control were established (see [9]).

For information on $ \epsilon _ {N} $, $ \epsilon ^ {N} $ and the inverse values $ N _ \epsilon ( C) $ and $ N _ \epsilon ( C , X ) $ see $ \epsilon $- entropy.

Problems related to widths are closely connected with various problems in geometry. For instance, the problem on the asymptotic behaviour of $ N _ \epsilon ( C , \mathbf R ^ {n} ) $ is closely related to the problem of the best sphere packing of the space $ \mathbf R ^ {n} $. The dependence of the asymptotics of widths on the ambient space led to the introduction of absolute widths, i.e.

$$ p _ {F} ^ {A} ( C) = \inf p _ {F} ( C , X ) , $$

where the infimum is taken over all imbeddings of $ C $ having its metric into the ambient space $ X $. Moreover, it turns out (see [9]) that, e.g.,

$$ \epsilon _ {N} ^ {A} ( C) = \frac{1}{2} \epsilon ^ {N} ( C) , $$

$$ a _ {N} ^ {A} ( C) = \frac{1}{2} u _ {N} ( C) . $$

References

[1]	A.N. Kolmogorov, "Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse" Ann. of Math. , 37 (1936) pp. 107–110
[2]	P.S. Urysohn, "Works on topology and other areas of mathematics" , 1 , Moscow-Leningrad (1951) pp. 483 (In Russian)
[3]	P.S. Aleksandrov, "Über die Urysohnschen Konstanten" Fund. Math. , 20 (1933) pp. 140–150
[4]	W. Hurevicz, G. Wallman, "Dimension theory" , Princeton Univ. Press (1948) ((Appendix by L.S. Pontryagin and L.G. Shnirel'man in Russian edition.))
[5]	A.N. Kolmogorov, "On certain asymptotic characteristics of completely bounded metric spaces" Dokl. Akad. Nauk SSSR , 108 : 3 (1956) pp. 385–388 (In Russian)
[6]	Yu.A. Brudnyi, A.F. Timan, "Constructional characteristics of compact sets in Banach spaces and -entropy" Dokl. Akad. Nauk SSSR , 126 : 5 (1959) pp. 927–930 (In Russian)
[7a]	V.M. Tikhomirov, "Diameters of sets in function spaces and the theory of best approximations" Russian Math. Surveys , 15 : 3 (1960) pp. 75–111 Uspekhi Mat. Nauk , 15 : 3 (1960) pp. 81–120
[7b]	V.M. Tikhomirov, "A remark on -dimensional diameters of sets in Banach spaces" Uspekhi Mat. Nauk , 20 : 1 (1965) pp. 227–230 (In Russian)
[8]	V.M. Tikhomirov, "Some problems in approximation theory" , Moscow (1976) (In Russian)
[9]	V.M. Tikhomirov, "Extremal problems in approximation theory and the diameters of smooth functions" , The theory of approximation of functions. Internat. Conf. Theory Approximation of Functions Kaluga, 1975 , Moscow (1977) pp. 359–365 (In Russian)
[10]	R.S. Ismagilov, "The widths of compacta in normed spaces" , Geometry of Linear Spaces and Theory of Operators , Yaroslavl' (1977) pp. 75–113 (In Russian)
[11]	R.S. Ismagilov, "Diameters of sets in normed linear spaces and the approximation of functions by trigonometric polynomials" Russian Math. Surveys , 29 : 3 (1974) pp. 169–186 Uspekhi Mat. Nauk , 29 : 3 (1974) pp. 161–178
[12]	Yu.I. Makovoz, "On a method of estimation from below of diameters of sets in Banach spaces" Math. USSR-Sb. , 16 (1972) pp. 139–146 Mat. Sb. , 87 : 1 (1972) pp. 136–142
[13]	B.S. Kashin, "Diameters of some finite-dimensional sets and classes of smooth functions" Math. USSR Izv. , 11 (1977) pp. 317–333 Izv. Akad. Nauk SSSR Ser. Mat. , 41 : 2 (1977) pp. 334–351
[14]	N.P. Korneichuk, "Extremal problems in approximation theory" , Moscow (1976) (In Russian)

Comments

Probably the best source in Western literature on widths in approximation theory is [a3]; it also contains an extensive bibliography including many references to the Russian literature.

The $ N $- widths according to Aleksandrov and Urysohn, respectively, can be used to give characterizations of covering dimension (see Dimension): If $ X $ is a compact subspace of some Euclidean space $ \mathbf R ^ {n} $, then $ \mathop{\rm dim} X \leq N $ if and only if $ a _ {N} ( X) = 0 $, i.e. if and only if there are arbitrarily small mappings from $ X $ into $ N $- dimensional polyhedra. Likewise, if $ X $ is compact metric, then $ \mathop{\rm dim} X \leq N $ if and only if $ u _ {N} ( X) = 0 $.

References

[a1]	R. Engelking, "Dimension theory" , North-Holland & PWN (1978)
[a2]	C.A. Michelli, T.J. Rivlin, "A survey in optimal recovery" C.A. Michelli (ed.) T.J. Rivlin (ed.) , Optimal estimation in approximation theory , Plenum (1977) pp. 1–54
[a3]	A. Pinkus, "$n$-widths in approximation theory" , Springer (1985) Zbl 0551.41001