Kolmogorov n-width of N+1 dimensional ball

1.3k Views Asked by At

For a normed linear space $\mathscr{X}$, let $\mathscr{A}\subset\mathscr{X}$ and $\mathscr{X}_N$ any $N$-dimensional subspace of $\mathscr{X}$. Define the $n$-width of $ \mathscr{A}$ in $\mathscr{X}$ as $$d_N(\mathscr{A}, \mathscr{X}) = \inf_{\mathscr{X}_N \subset \mathscr{X}} \sup_{f \in \mathscr{A}} \inf_{g \in \mathscr{X}_N} \|f-g\|.$$ This represents the extent to which $\mathscr{A}$ can be approximated by $N$-dimensional subspaces of $\mathscr{X}$.

Consider now the N+1 dimensional ball $U_{N+1}$ defined by $$g(t) = \sum_{n=0}^N a_n \psi_n(t), \;\; \|g\|\leq r.$$

I want to prove that $$d_N(U_{N+1}) = r.$$

The rough idea is that the approximating hyperplane for which the "worst" point on the ball can be "best" approximated by a point on the plane, should pass through the center of the ball, so that the distance to the farthest point is $r$.

Any ideas how to make this rigorous?

1

There are 1 best solutions below

0
On

Given $\mathscr X_N$ as above, pick $y\notin \mathscr X_N$ and let $z$ be a point of $\mathscr X_N$ that minimizes the distance to $y$. Let $u=(y-z)/\|y-z\|$; this is a unit vector.

Since $u$ is not parallel to $\mathscr X_N$, there is $t\in \mathbb R$ such that $tu\in \mathscr X_N$. Let $$w=\begin{cases} -ru\quad &\text{if }t\ge 0 \\ ru\quad &\text{if }t< 0 \end{cases}$$ and observe that $$\operatorname{dist}(w,\mathscr X_N)= \operatorname{dist}(w-tu,\mathscr X_N-tu)=\|w-tu\| = r+|t|$$