Namespaces
Variants
Actions

Difference between revisions of "Width"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (link)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
<!--
 +
w0978801.png
 +
$#A+1 = 178 n = 3
 +
$#C+1 = 178 : ~/encyclopedia/old_files/data/W097/W.0907880 Width
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''of a set''
 
''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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w0978801.png" /> be a normed space with unit ball <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w0978802.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w0978803.png" /> be a to-be-approximated subset of it, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w0978804.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w0978805.png" />, be a family of approximating subsets, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w0978806.png" /> be a set of mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w0978807.png" />, and, finally, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w0978808.png" />. The number
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w0978809.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
p _ {\mathfrak F }  ( C , X )  = \inf _ {f \in \mathfrak F } \
 +
\sup _ {x \in C }  \| x - f ( x) \|
 +
$$
  
measures the deviation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788010.png" /> from the family of approximating sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788011.png" /> using the approximation method <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788012.png" />.
+
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).
 
The majority of widths measuring approximation properties of various approximation methods are given by (1).
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788013.png" /> is the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788014.png" /> of all linear manifolds (i.e. translates of linear subspaces) of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788016.png" /> is the set of all mappings from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788017.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788018.png" />, then the expression (1) is called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788020.png" />-width according to Kolmogorov of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788021.png" />. It is usually denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788022.png" />, and measures the minimal deviation of a given set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788023.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788024.png" />-dimensional linear manifolds. Other, equivalent and generally accepted, definitions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788025.png" /> are the following (see [[#References|[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 [[#References|[1]]]):
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788026.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1prm)</td></tr></table>
+
$$ \tag{1'}
 +
d _ {N} ( C , X )  = \inf _ {\{ M _ {N} \} } \
 +
\sup _ {x \in C }  \inf _ {y \in M _ {N} } \
 +
\| x - y \| =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788027.png" /></td> </tr></table>
+
$$
 +
= \
 +
\inf _ {\{ M _ {N} \} }  \inf _ {\epsilon
 +
}  \{ \epsilon > 0 : C \subset  M _ {N} + \epsilon B \} .
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788028.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788029.png" />, the set of all subspaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788030.png" /> of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788031.png" />) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788032.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788033.png" />) is the set of all affine (linear) continuous mappings of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788034.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788035.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788036.png" />), then the quantity (1) is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788037.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788038.png" />) and is called the affine (linear) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788043.png" />-width. It measures the approximation properties by affine (linear) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788044.png" />-dimensional mappings.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788045.png" /> is the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788046.png" /> of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788047.png" />-dimensional compacta (equivalently, of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788048.png" />-dimensional polyhedra) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788049.png" /> is the set of all continuous mappings from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788050.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788051.png" />, then (1) is called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788053.png" />-width according to Aleksandrov; it is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788054.png" />. It measures the degree of approximation of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788055.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788056.png" />-dimensional compacta.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788057.png" /> is the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788058.png" /> of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788059.png" />-point sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788060.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788061.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788062.png" /> is the set of all mappings from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788063.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788064.png" />, then the width (1) is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788065.png" />. It measures the minimal deviation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788066.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788067.png" />-point sets.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788068.png" /> and can change when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788069.png" /> together with its metric is imbedded in another normed space.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788070.png" /> by elements of another sort. This process is often called the problem of recovering. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788071.png" /> be a metric space, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788072.png" /> be a family of  "coding"  sets, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788073.png" /> be a family of mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788074.png" />. Finally, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788075.png" /> be the given set of coding methods. The quantity
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788076.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
p  ^  \Phi  ( C)  = \inf _ {f \in \Phi } \
 +
\sup _ {z \in f ( C) }  D ( f ^ { - 1 } ( z) ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788077.png" /> denotes the diameter of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788078.png" />, measures the recoverability of the elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788079.png" /> by the information  "coded"  by elements of the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788080.png" /> from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788081.png" /> using mappings from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788082.png" />. The majority of widths related to processes of recovering are given by formulas analogous to (2).
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788083.png" /> is the set of all possible mappings from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788084.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788085.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788086.png" /> consists of the single set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788087.png" />, then the width (2), denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788088.png" />, measures the accuracy of recovering an element using a table consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788089.png" /> elements. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788090.png" /> lies in a linear normed space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788091.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788092.png" /> is the set of all continuous affine mappings on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788093.png" />, then the quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788094.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788095.png" /> is defined by (2), is called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788097.png" />-width according to Gel'fand and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788098.png" />. It measures the accuracy of recovering the elements by their images under affine mappings on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w09788099.png" />. In the case of sets symmetric with respect to the origin, the widths <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880100.png" /> have another equivalent definition:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880101.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2prm)</td></tr></table>
+
$$ \tag{2'}
 +
d  ^ {N} ( C)  = \inf _ {\{ N \} } \
 +
\sup
 +
_ {x \in C \cap L  ^ {N} }  \| x \| =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880102.png" /></td> </tr></table>
+
$$
 +
= \
 +
\inf _ { N }  \sup _  \epsilon  \{ \epsilon >
 +
0 : C \cap L  ^ {N} \subset  \epsilon B \} ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880103.png" /> is a closed subspace of codimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880104.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880105.png" /> consist of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880106.png" />-dimensional compacta <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880107.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880108.png" /> be the set of all continuous mappings from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880109.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880110.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880111.png" />. Then (2) is called the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880113.png" />-width according to Urysohn and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880114.png" />. Another, equivalent and widely used, definition of the Urysohn width is the following: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880115.png" /> is the lower bound of all diameters of covering sets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880116.png" /> of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880117.png" />. The Urysohn width measures the degree of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880118.png" />-dimensionality (from the point of view of Brouwer dimension) of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880119.png" />.
+
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 [[#References|[2]]]) when he defined <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880120.png" />. In 1933 P.S. Aleksandrov [[#References|[3]]] established approximative aspects of dimension theory which resulted in defining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880121.png" />. In 1933 A.N. Kolmogorov [[#References|[1]]] defined <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880122.png" />; this width was studied in depth in approximation theory. In 1931 L.S. Pontryagin and L.G. Shnirel'man (see [[#References|[4]]]) expressed the dimension (a topological characteristic) by an asymptotic metric characteristic <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880123.png" /> (the inverse of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880124.png" />), which in a metric space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880125.png" /> equals the least number of elements of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880126.png" />-covering of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880127.png" />. Interest in this type of characteristic increased in the 1950's when Kolmogorov [[#References|[5]]] introduced <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880128.png" /> (the inverse of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880129.png" />), based on arguments of information theory, and indicated a program of studying variables like <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880130.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880131.png" /> as a specific part of approximation theory related to questions of best tabulation of functions. The binary logarithm of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880132.png" /> is called the [[Epsilon-entropy|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880133.png" />-entropy]] of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880134.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880135.png" /> is called the absolute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880137.png" />-entropy of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880138.png" />.
+
The first quantity that later was called a width was introduced in 1923 by P.S. Urysohn (see [[#References|[2]]]) when he defined $  u _ {N} $.  
 +
In 1933 P.S. Aleksandrov [[#References|[3]]] established approximative aspects of dimension theory which resulted in defining $  a _ {N} $.  
 +
In 1933 A.N. Kolmogorov [[#References|[1]]] defined $  d _ {N} $;  
 +
this width was studied in depth in approximation theory. In 1931 L.S. Pontryagin and L.G. Shnirel'man (see [[#References|[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 [[#References|[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| $  \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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880139.png" /> be the set of functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880140.png" /> on a finite interval (e.g. on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880141.png" />) having an absolutely continuous <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880142.png" />-th order derivative and an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880143.png" />-th order derivative for which
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880144.png" /></td> </tr></table>
+
$$
 +
\| 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:
 
The following asymptotic formula is valid:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880145.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \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.
 
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 [[#References|[10]]], [[#References|[13]]]). The set of trigonometric polynomials spanned by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880146.png" /> turned out to be asymptotically non-extremal. However, in a number of cases  "rearranged"  harmonics, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880147.png" /> harmonics taken in a  "wrong"  order, turned out to be extremal.
+
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 [[#References|[10]]], [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880148.png" />-octahedrons in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880149.png" />:
+
The solution of the problem of widths of Sobolev classes is based on the problem of diameters for $  n $-
 +
octahedrons in $  \mathbf R  ^ {n} $:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880150.png" /></td> </tr></table>
+
$$
 +
O _ {p}  ^ {n}  = \left \{ {x \in \mathbf R  ^ {n} } : {\sum _ { i=1} ^ { n }
 +
| x _ {i} |  ^ {p} \leq  1 } \right \}
 +
.
 +
$$
  
For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880151.png" /> the quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880152.png" /> has been determined exactly; also, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880153.png" /> has been calculated exactly: it turned out to be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880154.png" />. The following estimates (see [[#References|[13]]]) are of fundamental importance for the calculation of Kolmogorov widths for Sobolev classes:
+
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 [[#References|[13]]]) are of fundamental importance for the calculation of Kolmogorov widths for Sobolev classes:
  
A) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880155.png" />;
+
A) $  d _ {N} ( O _ {1}  ^ {n} , l _  \infty  ^ {n} ) \leq  2N  ^ {- 1/2} (  \mathop{\rm ln}  n )  ^ {1/2} $;
  
B) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880156.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880157.png" /> is a constant;
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880158.png" />, then for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880159.png" /> the following inequality holds:
+
C) if $  \lambda \in ( 0 , 1 ) $,
 +
then for $  n  ^  \lambda  \leq  N \leq  n $
 +
the following inequality holds:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880160.png" /></td> </tr></table>
+
$$
 +
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
 
The asymptotic behaviour of the Aleksandrov widths for Sobolev classes has been considered as well. It has been shown that
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880161.png" /></td> </tr></table>
+
$$
 +
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 [[#References|[1]]] who solved the problem of calculating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880162.png" /> and the similar problem for the periodic class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880163.png" /> in the metric of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880164.png" />.
+
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 [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880165.png" />. This theorem was generalized (see [[#References|[12]]]) and used to obtain other exact solutions. Later some interesting relations with the calculus of variations and optimal control were established (see [[#References|[9]]]).
+
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 [[#References|[12]]]) and used to obtain other exact solutions. Later some interesting relations with the calculus of variations and optimal control were established (see [[#References|[9]]]).
  
For information on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880166.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880167.png" /> and the inverse values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880168.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880169.png" /> see [[Epsilon-entropy|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880170.png" />-entropy]].
+
For information on $  \epsilon _ {N} $,  
 +
$  \epsilon  ^ {N} $
 +
and the inverse values $  N _  \epsilon  ( C) $
 +
and $  N _  \epsilon  ( C , X ) $
 +
see [[Epsilon-entropy| $  \epsilon $-
 +
entropy]].
  
Problems related to widths are closely connected with various problems in geometry. For instance, the problem on the asymptotic behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880171.png" /> is closely related to the problem of the best sphere packing of the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880172.png" />. The dependence of the asymptotics of widths on the ambient space led to the introduction of absolute widths, i.e.
+
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.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880173.png" /></td> </tr></table>
+
$$
 +
p _ {F}  ^ {A} ( C)  = \inf  p _ {F} ( C , X ) ,
 +
$$
  
where the infimum is taken over all imbeddings of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880174.png" /> having its metric into the ambient space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880175.png" />. Moreover, it turns out (see [[#References|[9]]]) that, e.g.,
+
where the infimum is taken over all imbeddings of $  C $
 +
having its metric into the ambient space $  X $.  
 +
Moreover, it turns out (see [[#References|[9]]]) that, e.g.,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880176.png" /></td> </tr></table>
+
$$
 +
\epsilon _ {N}  ^ {A} ( C)  =
 +
\frac{1}{2}
 +
\epsilon  ^ {N} ( C) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880177.png" /></td> </tr></table>
+
$$
 +
a _ {N}  ^ {A} ( C)  =
 +
\frac{1}{2}
 +
u _ {N} ( C) .
 +
$$
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.N. Kolmogorov,  "Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse"  ''Ann. of Math.'' , '''37'''  (1936)  pp. 107–110</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  P.S. Urysohn,  "Works on topology and other areas of mathematics" , '''1''' , Moscow-Leningrad  (1951)  pp. 483  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  P.S. Aleksandrov,  "Über die Urysohnschen Konstanten"  ''Fund. Math.'' , '''20'''  (1933)  pp. 140–150</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  W. Hurevicz,  G. Wallman,  "Dimension theory" , Princeton Univ. Press  (1948)  ((Appendix by L.S. Pontryagin and L.G. Shnirel'man in Russian edition.))</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  A.N. Kolmogorov,  "On certain asymptotic characteristics of completely bounded metric spaces"  ''Dokl. Akad. Nauk SSSR'' , '''108''' :  3  (1956)  pp. 385–388  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  Yu.A. Brudnyi,  A.F. Timan,  "Constructional characteristics of compact sets in Banach spaces and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880178.png" />-entropy"  ''Dokl. Akad. Nauk SSSR'' , '''126''' :  5  (1959)  pp. 927–930  (In Russian)</TD></TR><TR><TD valign="top">[7a]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[7b]</TD> <TD valign="top">  V.M. Tikhomirov,  "A remark on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880179.png" />-dimensional diameters of sets in Banach spaces"  ''Uspekhi Mat. Nauk'' , '''20''' :  1  (1965)  pp. 227–230  (In Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  V.M. Tikhomirov,  "Some problems in approximation theory" , Moscow  (1976)  (In Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  N.P. Korneichuk,  "Extremal problems in approximation theory" , Moscow  (1976)  (In Russian)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.N. Kolmogorov,  "Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse"  ''Ann. of Math.'' , '''37'''  (1936)  pp. 107–110</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  P.S. Urysohn,  "Works on topology and other areas of mathematics" , '''1''' , Moscow-Leningrad  (1951)  pp. 483  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  P.S. Aleksandrov,  "Über die Urysohnschen Konstanten"  ''Fund. Math.'' , '''20'''  (1933)  pp. 140–150</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  W. Hurevicz,  G. Wallman,  "Dimension theory" , Princeton Univ. Press  (1948)  ((Appendix by L.S. Pontryagin and L.G. Shnirel'man in Russian edition.))</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  A.N. Kolmogorov,  "On certain asymptotic characteristics of completely bounded metric spaces"  ''Dokl. Akad. Nauk SSSR'' , '''108''' :  3  (1956)  pp. 385–388  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  Yu.A. Brudnyi,  A.F. Timan,  "Constructional characteristics of compact sets in Banach spaces and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880178.png" />-entropy"  ''Dokl. Akad. Nauk SSSR'' , '''126''' :  5  (1959)  pp. 927–930  (In Russian)</TD></TR><TR><TD valign="top">[7a]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[7b]</TD> <TD valign="top">  V.M. Tikhomirov,  "A remark on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880179.png" />-dimensional diameters of sets in Banach spaces"  ''Uspekhi Mat. Nauk'' , '''20''' :  1  (1965)  pp. 227–230  (In Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  V.M. Tikhomirov,  "Some problems in approximation theory" , Moscow  (1976)  (In Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  N.P. Korneichuk,  "Extremal problems in approximation theory" , Moscow  (1976)  (In Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
 
Probably the best source in Western literature on widths in approximation theory is [[#References|[a3]]]; it also contains an extensive bibliography including many references to the Russian literature.
 
Probably the best source in Western literature on widths in approximation theory is [[#References|[a3]]]; it also contains an extensive bibliography including many references to the Russian literature.
  
The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880180.png" />-widths according to Aleksandrov and Urysohn, respectively, can be used to give characterizations of covering dimension (see [[Dimension|Dimension]]): If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880181.png" /> is a compact subspace of some Euclidean space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880182.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880183.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880184.png" />, i.e. if and only if there are arbitrarily small mappings from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880185.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880186.png" />-dimensional polyhedra. Likewise, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880187.png" /> is compact metric, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880188.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880189.png" />.
+
The $  N $-
 +
widths according to Aleksandrov and Urysohn, respectively, can be used to give characterizations of [[covering dimension]] (see [[Dimension|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====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R. Engelking,  "Dimension theory" , North-Holland &amp; PWN  (1978)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Pinkus,  "<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w097/w097880/w097880190.png" />-widths in approximation theory" , Springer  (1985) (Translated from Russian)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  R. Engelking,  "Dimension theory" , North-Holland &amp; PWN  (1978)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  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</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Pinkus,  "$n$-widths in approximation theory" , Springer  (1985) {{ZBL|0551.41001}}</TD></TR></table>

Latest revision as of 19:54, 3 February 2021


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
How to Cite This Entry:
Width. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Width&oldid=18052
This article was adapted from an original article by V.M. Tikhomirov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article