{"id":120,"date":"2008-10-04T17:25:54","date_gmt":"2008-10-04T16:25:54","guid":{"rendered":"https:\/\/wpethzprd.ethz.ch\/kowalski\/2008\/10\/04\/projection-to-subspaces-and-a-theorem-of-chebychev\/"},"modified":"2024-02-20T13:40:57","modified_gmt":"2024-02-20T11:40:57","slug":"projection-to-subspaces-and-a-theorem-of-chebychev","status":"publish","type":"post","link":"https:\/\/blogs.ethz.ch\/kowalski\/2008\/10\/04\/projection-to-subspaces-and-a-theorem-of-chebychev\/","title":{"rendered":"Projection to subspaces and a theorem of Chebychev"},"content":{"rendered":"

I just taught at ETH the basic result of the theory of Hilbert spaces that states that, given such a space H<\/em>, a vector v<\/em> in H <\/em>and a closed, non-empty, convex<\/em> subset C<\/em>, there exists a unique vector y<\/em> in C<\/em> such that<\/p>\n

$latex ||v-y||=\\inf_{w\\in C}{||v-w||},$<\/p>\n

and which deserves to be called the orthogonal projection of v<\/em> on C<\/em>, as the picture tries to illustrate:<\/p>\n

\"Projection\"<\/a><\/p>\n

Having done this, I looked for counterexamples to illustrate that this natural statement does not extend to the Banach space setting; it is easy enough to find situations where the minimum is achieved more than once (in fact, infinitely often), but slightly more challenging to find one where the minimum is not<\/em> achieved at all. Here is one (it was in one of the books I use for my course): consider the Banach space c0<\/sub><\/em> of sequences (indexed by n>0<\/em>) of complex numbers converging to 0, with the sup norm<\/p>\n

$latex ||(u_n)||=\\sup_{n\\geq 1}{|u_n|}.$<\/p>\n

Consider then the linear map<\/p>\n

$latex \\lambda(u)=\\sum_{n\\geq 1}{2^{-n}u_n}$<\/p>\n

on c0<\/sub><\/em>. It is clear that this is a continuous linear map since it is bounded by 1 on the unit ball, and a moment’s thought shows that in fact we have<\/p>\n

$latex |\\lambda(u)|<1\\quad\\text{ if } \\quad ||u||\\leq 1$<\/p>\n

because equality<\/em> would require that u<\/em> be a constant sequence, and this is impossible if the sequence is to converge to zero, except (of course) when the constant is zero, but then \u03bb(0)=0<\/em> anyway….<\/p>\n

This is a case where a supremum is not achieved, and so it is easily transformed to what we want by taking, e.g., v=0<\/em> and the convex set<\/p>\n

$latex C=\\{v\\in c_0\\,\\mid\\, \\lambda(v)=1\\}.$<\/p>\n

Then there does not exist a vector in C<\/em> minimizing the distance to the origin.<\/p>\n

Now, this is probably not too surprising to anyone, but while preparing these counterexamples for exercises for the students of my course, I was reminded of a beautiful approximation result of Chebychev which is probably not well-known (outside the numerical analysis community, where it seems to be standard knowledge) and which gives a particular (important) case outside of the Hilbert space context<\/em> where the minimization process works.<\/p>\n

Consider the (real) Banach space B<\/em> of real-valued continuous functions on [0,1] with the supremum norm (i.e., the norm of uniform convergence of functions). Fix then a degree d>0<\/em>. In B<\/em>, the subspace Pold<\/sub><\/em> of real polynomials of degree at most d<\/em> is a closed (non-empty) convex subset. The approximation problem is therefore, for a given continuous function f<\/em>, to find the polynomials P<\/em> of degree at most d<\/em> which minimize the distance to f<\/em>:<\/p>\n

$latex ||f-P||=\\sup_{0\\leq x\\leq 1}\\ \\ |f(x)-P(x)|$<\/p>\n

must be equal to<\/p>\n

$latex D_d=\\inf_{P\\in \\text{Pol}_d}{||f-P||}.$<\/p>\n

It is not very difficult to prove the existence of at least one such polynomial P<\/em> (the idea being to show that the minimization can be restricted to a compact<\/em> subset of the subspace Pold<\/sub><\/em>). It is more difficult to prove unicity, and even more subtle to find the following characterization (which was found by Chebychev): a polynomial P<\/em> (of degree at most d<\/em>) is the best approximation to f<\/em> in this sense if and only if<\/em>, there exist at least d+2<\/em> points, say<\/p>\n

$latex x_1<x_2<\\ldots<x_n,\\quad n\\geq d+2,$<\/p>\n

such that<\/p>\n

$latex |f(x_i)-P(x_i)|=||f-P||,\\quad\\text{ for all } i,$<\/p>\n

and moreover the signs of f(xi<\/sub>)-P(xi<\/sub>)<\/em> alternate when i<\/em> increases. Below, I call the existence of points with these two properties the “d+2<\/em> alternation property”; note that it says nothing about the size of the distance from f<\/em> to P<\/em>. Here is an illustration:<\/p>\n

\"Chebychev<\/a><\/p>\n

the red function f<\/em> is the cosine function, and the blue graph is the best approximation of degree (at most) 3; the gray line is the difference cos(x)-P(x)<\/em>, and the 5 alternating extrema are clearly visible. (I used Maple<\/strong> to construct the approximation, and Sage<\/strong> to plot the graph).<\/p>\n

The unicity seems to be typically proved by first showing that there is at most one polynomial with the d+2<\/em> alternation property (which is fairly easy; in fact, alternation with d+1<\/em> points would be enough), and then showing that minimizing polynomials are characterized by it. The most technical part is the proof that a minimizing polynomial has the required property (if there are less than d+2<\/em> alternations, one shows how to improve the approximation).<\/p>\n

But the converse (an alternating polynomial is minimizing) looks also quite difficult at first since, as we observed, the defining condition doesn’t say anything about the size of<\/p>\n

$latex ||f-P||,$<\/p>\n

only that it is achieved at d+2<\/em> points. But here is the trick: suppose another polynomial Q<\/em> (of degree at most d<\/em>) is such that<\/p>\n

$latex (*)\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ ||f-Q||<||f-P||.$<\/p>\n

Then, at the points xi<\/sub><\/em>, the difference Q-P<\/em> has the same sign<\/em> as f-P<\/em> (by writing<\/p>\n

$latex Q(x_i)-P(x_i)=(f(x_i)-P(x_i)) – (f(x_i)-Q(x_i)),$<\/p>\n

and the second summand is not big enough, by (*), to provoke a change of sign). By the assumption of alternation of signs of the d+2<\/em> values<\/p>\n

$latex f(x_i)-P(x_i),$<\/p>\n

(which hasn’t been used yet), this means the polynomial Q-P<\/em>, of degree at most d<\/em>, has at least d+1<\/em> changes of signs, hence that many zeros, so we must have Q=P<\/em>, which is a contradiction.<\/p>\n

Incidentally, the only reason I know this result is that it was the subject of one of the entrance exams at the French \u00c9cole Polytechnique<\/em>, and that this exam text was (because of this) used by the teacher of my Math. Sp\u00e9<\/em> for one of our weekly take-home exams; the last questions were set up in a challenging way (which I don’t remember, but it must have been the proof of the clever part above), and the result was fixed in my mind because I succeeded in finding the trick…<\/p>\n

For a full account, see for instance Analysis of Numerical Methods<\/a>, by Isaacson and Keller (which I only have in my personal library because it was in the bargains bin in the English bookstore in Bordeaux one day, for some mysterious reason).<\/p>\n","protected":false},"excerpt":{"rendered":"

I just taught at ETH the basic result of the theory of Hilbert spaces that states that, given such a space H, a vector v in H and a closed, non-empty, convex subset C, there exists a unique vector y in C such that $latex ||v-y||=\\inf_{w\\in C}{||v-w||},$ and which deserves to be called the orthogonal … Continue reading Projection to subspaces and a theorem of Chebychev<\/span><\/a><\/p>\n","protected":false},"author":625,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-120","post","type-post","status-publish","format-standard","hentry","category-blogroll"],"_links":{"self":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/120","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/users\/625"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/comments?post=120"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/120\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/media?parent=120"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/categories?post=120"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/tags?post=120"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}