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 be a normed space with unit ball , let be a to-be-approximated subset of it, let , , be a family of approximating subsets, let be a set of mappings , and, finally, let . The number

(1)

measures the deviation of from the family of approximating sets using the approximation method .

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

If is the set of all linear manifolds (i.e. translates of linear subspaces) of dimension and is the set of all mappings from into , then the expression (1) is called the -width according to Kolmogorov of the set . It is usually denoted by , and measures the minimal deviation of a given set from -dimensional linear manifolds. Other, equivalent and generally accepted, definitions of are the following (see [1]):

(1prm)

If (or , the set of all subspaces of dimension ) and () is the set of all affine (linear) continuous mappings of into (), then the quantity (1) is denoted by () and is called the affine (linear) -width. It measures the approximation properties by affine (linear) -dimensional mappings.

If is the set of all -dimensional compacta (equivalently, of all -dimensional polyhedra) and is the set of all continuous mappings from into , then (1) is called the -width according to Aleksandrov; it is denoted by . It measures the degree of approximation of the set by -dimensional compacta.

If is the set of all -point sets of , and is the set of all mappings from into , then the width (1) is denoted by . It measures the minimal deviation of from -point sets.

All above-mentioned approximate widths depend on the ambient space and can change when 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 by elements of another sort. This process is often called the problem of recovering. Let be a metric space, let be a family of "coding" sets, and let be a family of mappings . Finally, let be the given set of coding methods. The quantity

(2)

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

If is the set of all possible mappings from into , where consists of the single set , then the width (2), denoted by , measures the accuracy of recovering an element using a table consisting of elements. If lies in a linear normed space and is the set of all continuous affine mappings on , then the quantity , where is defined by (2), is called the -width according to Gel'fand and is denoted by . It measures the accuracy of recovering the elements by their images under affine mappings on . In the case of sets symmetric with respect to the origin, the widths have another equivalent definition:

(2prm)

where is a closed subspace of codimension . Let consist of all -dimensional compacta , let be the set of all continuous mappings from into , and let . Then (2) is called the -width according to Urysohn and is denoted by . Another, equivalent and widely used, definition of the Urysohn width is the following: is the lower bound of all diameters of covering sets of of order . The Urysohn width measures the degree of -dimensionality (from the point of view of Brouwer dimension) of the set .

The first quantity that later was called a width was introduced in 1923 by P.S. Urysohn (see [2]) when he defined . In 1933 P.S. Aleksandrov [3] established approximative aspects of dimension theory which resulted in defining . In 1933 A.N. Kolmogorov [1] defined ; 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 (the inverse of ), which in a metric space equals the least number of elements of a -covering of . Interest in this type of characteristic increased in the 1950's when Kolmogorov [5] introduced (the inverse of ), based on arguments of information theory, and indicated a program of studying variables like and as a specific part of approximation theory related to questions of best tabulation of functions. The binary logarithm of is called the -entropy of the set , and is called the absolute -entropy of .

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 be the set of functions on a finite interval (e.g. on ) having an absolutely continuous -th order derivative and an -th order derivative for which

The following asymptotic formula is valid:

(3)

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 turned out to be asymptotically non-extremal. However, in a number of cases "rearranged" harmonics, i.e. 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 -octahedrons in :

For the quantity has been determined exactly; also, has been calculated exactly: it turned out to be . The following estimates (see [13]) are of fundamental importance for the calculation of Kolmogorov widths for Sobolev classes:

A) ;

B) , where is a constant;

C) if , then for the following inequality holds:

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

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 and the similar problem for the periodic class in the metric of .

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 . 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 , and the inverse values and see -entropy.

Problems related to widths are closely connected with various problems in geometry. For instance, the problem on the asymptotic behaviour of is closely related to the problem of the best sphere packing of the space . The dependence of the asymptotics of widths on the ambient space led to the introduction of absolute widths, i.e.

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

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 -widths according to Aleksandrov and Urysohn, respectively, can be used to give characterizations of covering dimension (see Dimension): If is a compact subspace of some Euclidean space , then if and only if , i.e. if and only if there are arbitrarily small mappings from into -dimensional polyhedra. Likewise, if is compact metric, then if and only if .

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, "-widths in approximation theory" , Springer (1985) (Translated from Russian)