Nearest point projection, part I: eschewing transliterations

A subset A of a metric space (X,d) is called a Чебышёв (Chebyshev) set if for every x\in X there exists a\in A such that d(a',x)>d(a,x) for all a'\in A\setminus \{a\}. In words, for each point of the space there is a well-defined nearest point of A. We can then define the nearest point projection P\colon X\to A by sending x to a. This is consistent with the notion of orthogonal projection onto a subspace of a Euclidean space. More generally, every closed convex subset of a Hilbert space is a Чебышёв set. Whether the converse is true is unknown. It’s been proved in finite dimensions and in some other special cases, such as for weakly closed sets. (Yes, being weakly closed is a stronger property than being closed…)

How could a nonconvex set have NPP?

There isn’t much one can prove about Чебышёв sets in general metric spaces. They must be closed, and that’s about it. Let’s specialize to X being a real Banach space, and A a closed subspace thereof. There are two ways in which A could fail to be Чебышёв:

  1. the infimum \inf_{a\in A} d(a,x) is attained for more than one point a\in A.
  2. the infimum is not attained at all.

Examples of the first kind are easy to produce. Let X be the plane with the taxicab norm \|x\|=|x_1|+|x_2|. The point (1,0) is at distance 1 from the line \lbrace x_1=x_2\rbrace, and this distance is realized by any point (t,t) with 0\le t\le 1.

It’s also easy to see exactly how we can avoid such examples: assume that the space X is strictly convex, i.e., its unit sphere does not contain any line segments.

Examples of the second kind are not as simple. To attain the infimum, it suffices to find a cluster point of a minimizing sequence (a_n). So if the space is reflexive, we can use the weak compactness of closed balls [note in passing: weak compactness is weaker than compactness] to obtain a weakly convergent minimizing sequence. Its limit also belongs to A and minimizes the distance.

The converse is also true: if every closed subspace is Чебышёв, then X is reflexive. Indeed, by the James theorem every non-reflexive space has a linear functional \varphi that is not norm-attaining, that is, |\varphi(x)|<\|\varphi\|\|x\| for all x\ne 0. Let A=\mathrm{ker}\,\varphi. I claim that A has no nearest points to any point x\notin A.

Fix a point x\notin A and suppose that a\in A is the corresponding nearest point. We may assume \|x-a\|=1. Since |\varphi(x)|=|\varphi(x-a)|<\|\varphi \|, there exists a unit vector y\in X such that \varphi(y)>|\varphi(x)|. The vector a' = x-\frac{\varphi(x)}{\varphi(y)}\,y belongs to A and \|x-a'\|<1, a contradiction.

For a concrete example, take X=\ell_1 and \displaystyle A=\lbrace x\in\ell_1\colon \sum_{n=1}^\infty \frac{n}{n+1}x_n=0\rbrace. One can check that the unit vector e_1\in\ell_1 has \mathrm{dist}(e_1,A)=1/2, and this distance is not attained. The sequence \displaystyle a_n=\frac{n}{2n+1}e_1-\frac{n+1}{2n+1}e_n has \mathrm{dist}(x,a_n)\to 1/2, but contains no weakly convergent subsequence. Its weak* limit is \frac{1}{2}e_1, which is outside of A. Like this:

Closed subspace is always weakly closed, but not necessarily weak*ly closed

Just as the name Чебышёв has no nearest point projection onto the Latin alphabet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s