Lecture notes, lectures 1 - 3 PDF

Preview

Summary

Download Lecture notes, lectures 1 - 3 PDF

Description

Chapter 3

Hilbert spaces Contents Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Inner products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cauchy-Schwarz inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Induced norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hilbert space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Minimum norm optimization problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chebyshev sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Projectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Orthogonality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Orthogonal complements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Orthogonal projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Direct sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Orthogonal sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Gram-Schmidt procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Normal equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Gram matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Orthogonal bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Approximation and Fourier series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Linear varieties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dual approximation problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fourier series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Complete orthonormal sequences / countable orthonormal bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . Wavelets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Normed spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Inner product spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Minimum distance to a convex set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Projection onto convex sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1

3.2 3.2 3.2 3.3 3.4 3.5 3.5 3.6 3.6 3.11 3.12 3.13 3.14 3.15 3.17 3.17 3.18 3.18 3.18 3.20 3.20 3.22 3.24 3.26 3.26 3.27 3.27 3.28 3.28 3.29 3.30 3.31

c J. Fessler, November 5, 2004, 17:8 (student version) 

3.2

Key missing geometrical concepts: angle and orthogonality (“right angles”). 3.1 Introduction We now turn to the subset of normed spaces called Hilbert spaces, which must have an inner product. These are particularly useful spaces in applications/analysis. Why not introduce Hilbert first then? For generality: it is helpful to see which properties are general to vector spaces, or to normed spaces, vs which require additional assumptions like an inner product. Overview • inner product • orthogonality • orthogonal projections • applications • least-squares minimization • orthonormalization of a basis • Fourier series General forms of things you have seen before: Cauchy-Schwarz, Gram-Schmidt, Parseval’s theorem 3.2 Inner products Definition. A pre-Hilbert space, aka an inner product space , is a vector space X defined on the field F = R or F = C, along with an inner product operation h·, ·i : X × X → F , which must satisfy the following axioms ∀x, y ∈ X , α ∈ F . 1. hx, yi = hy, xi∗ (Hermitian symmetry), where ∗ denotes complex conjugate. 2. hx + y, zi = hx, zi + hy, zi (additivity) 3. hαx, yi = αhx, yi (scaling) 4. hx, xi ≥ 0 and hx, xi = 0 iff x = 0. (positive definite) Properties of inner products Bilinearity property:

* X i

αi x i ,

X j

βj yj

+

=

XX j

i

αi β j∗ hxi , yj i.

Lemma. In an inner product space, if hx, yi = 0 for all y, then x = 0. Proof. Let y = x.

✷

Cauchy-Schwarz inequality Lemma. For all x,y in an inner product space, p p |hx, yi| ≤ hx, xi hy, yi = kxk ky k (see induced norm below) ,

with equality iff x and y are linearly dependent. Proof. For any λ ∈ F the positive definiteness of h·, ·i ensures that

2

0 ≤ hx − λy, x − λyi = hx, xi − λhy, xi − λ∗ hx, yi + |λ| hy, y i. If y = 0, the inequality holds trivially. Otherwise, consider λ = hx, y i/hy , y i and we have 2

0 ≤ hx, xi − |hy, xi| /hy , y i. p Rearranging yields |hy, xi| ≤ hx, xihy , y i = kxk kyk . The proof about equality conditions is Problem 3.1. ✷ This result generalizes all the “Cauchy-Schwarz inequalities” you have seen in previous classes, e.g., vectors in Rn , random variables, discrete-time and continuous-time signals, each of which corresponds to a particular inner product space.

c J. Fessler, November 5, 2004, 17:8 (student version) 

3.3

Angle Thanks to this inequality, we can generalize the notion of the angle between vectors to any general inner product space as follows:   |hx, y i| θ = cos−1 , ∀x, y 6= 0. kxk kyk This definition is legitimate since the argument of cos−1 will always be between 0 and 1 due to the Cauchy-Schwarz inequality. Induced norm Proposition. In an inner product space (X , h·, ·i), the induced norm kxk =

p

hx, xi is indeed a norm.

Proof. What must we show? • The first axiom ensures that hx, xi is real. • kxk ≥ 0 p with equality iffp x = 0 follows p from Axiom 4. p p • kαxk = hαx, αxi = αhx, αxi = αhαx, xi∗ = αα∗ hx, xi∗ = |α| hx, xi = |α| kxk, using Axioms 1 and 3. 2 • The only condition remaining to be verified is the triangle inequality: kx + y k = hx, xi + hx, yi + hy, xi + hy, y i 2 2 2 2 2 2 2 = kxk + 2 real(hx, y i) + ky k ≤ kxk √ + 2 |hx, yi| + kyk ≤ kxk + 2 kxk kyk + kyk = (kxk + kyk) . ✷ 2 2 (Recall if z = a + ıb, then a = real(z) ≤ a + b = |z |.) ...................................................................................................................... Any inner product space is necessarily a normed space. Is the reverse true? Not in general. The following property distinguishes inner product spaces from mere normed spaces. Lemma. (The parallelogram law.) In an inner product space: 2

2

2

2

kx + yk + kx − y k = 2 kxk + 2 ky k ,

∀x, y ∈ X .

Proof. Expand the norms into inner products and simplify.

(3-1) ✷

x

x-y

x+y

y

Remarkably, the converse of this Lemma also holds (see, e.g., problem [2, p. 175]). Proposition. If (X , k·k) is a normed space over C or R, and its norm satisfies the parallelogram law (3-1), then X is also an inner product space, with inner product: hx, yi =

Proof. homework challenge problem.

 1 2 2 2 2 kx + y k − kx − y k + i kx + iy k − i kx − iy k . 4

Continuity of inner products Lemma. In an inner product space (X , h·, ·i), if xn → x and yn → y, then hxn , yn i → hx, y i. Proof. |hxn , yn i − hx, yi| = |hxn , yn i − hx, yn i + hx, yn i − hx, yi| ≤ |hxn , yn i − hx, yn i| + |hx, yn i − hx, y i| = |hxn − x, yn i| + |hx, yn − y i|

≤ kxn − xk kyn k + kxk kyn − yk by Cauchy-Schwarz

≤ kxn − xk M + kxk kyn − yk since yn is convergent and hence bounded → 0 as n → ∞.

Thus hxn , yn i → hx, y i.

✷

c J. Fessler, November 5, 2004, 17:8 (student version) 

3.4

Examples Many of the normed spaces we considered previously are actually induced by suitable inner product space. Example. In Euclidean space, the usual inner product (aka “dot product”) is hx, yi =

n X

ai bi , where x = (a1 , . . . , an ) and y = (b1 , . . . , bn ).

i=1

Verifying the axioms is trivial. The induced norm is the usual ℓ2 norm. P Example. For the space ℓ2 over the complex field, the usual inner product is1 hx, yi = i aiib.∗ The H¨older inequality, which is equivalent to the Cauchy-Schwarz inequality for this space, ensures that |hx, yi| ≤ kxk2 ky k2 . So the inner product is indeed finite for x, y ∈ ℓ2 . Thus ℓ2 is not only a Banach space, it is also an inner product space. Example. What about ℓp for p 6= 2? Do suitable inner products exist? Consider X = R2 , k·kp · with x = (1, 0) and y = (0, 1).

The parallelogram law holds (for this x and y ) iff 2(1 + 1)2/p = 2 · 12 + 2 · 12 , i.e., iff 22/p = 2. Thus ℓ2 is only inner product space in the ℓp family of normed spaces. Example. The space of measurable functions on [a, b] with inner product hf, gi =

Z

b

w(t)f (t)g ∗ (t) dt,

a

where w(t) > 0, ∀t is some (real) weighting function. Choosing w = 1 yields L2 [a, b].

Hilbert space Definition. A complete inner product space is called a Hilbert space. In other words, a Hilbert space is a Banach space along with an inner product that induces its norm. The addition of the inner product opens many analytical doors, as we shall see. The concept “complete” is appropriate here since any inner product space is a normed space. All of the preceding examples of inner product spaces were complete vector spaces (under the induced norm). Example. The following is an inner product space, but not a Hilbert space, since it is incomplete: R2 [a, b] =

(

f : [a, b] → R : Riemann integral

with inner product (easily verified to satisfy the axioms): hf, gi =

Z

b

a

Rb f (t)g (t) dt . a

2

)

f (t) dt < ∞ ,

1 Note that the conjugate goes with the second argument become of Axiom 3. I have heard that some treatments scale the second argument in Axiom 3, which affects where the conjugates go in the inner products.

c J. Fessler, November 5, 2004, 17:8 (student version) 

3.5

Minimum norm optimization problems Section 3.3 is called “the projection theorem” and it is about a certain type of minimum norm problem. Before focusing on that specific minimum norm problem, we consider the broad family of such problems. Consider the following problem, which arises in many applications such as in approximation problems: Given x in a normed space (X , k·k), and a subset S in X , find “the” vector s ∈ S that minimizes kx − sk. Example. Control subject to energy constraint. See Section 3.11. Pn Example. Least-squares estimation: minθ ky − i=1 θi xi k is equivalent to minm∈[{x1 ,...,xn }] ky − mk . ...................................................................................................................... What questions should we ask about such problems? • Is there any best s? I.e., does there exist s⋆ ∈ S s.t. kx − s⋆ k = d(x, S)? What answers do we have so far for this question?

??

• If so, is s⋆ unique? Answers thus far? ?? • How is s⋆ characterized? (Better yet would be an explicit formula for s⋆ .) Chebyshev sets One way to address such questions is “answer by definition.” Definition. A set S in a normed space (X , k·k) is called proximinal [16] iff ∀x ∈ X, there exists at least one point s ∈ S s.t. kx − sk = d(x, S). Definition. In a normed space, a set S is called a Chebyshev set iff ∀x ∈ X , there exists a unique s ∈ S s.t. kx − sk = d(x, S).

Fact. Any proximinal set is closed. (The points in S − S do not have a closest point in S.) Fact. Any Chebyshev set is a proximinal set. Fact. Any compact set is a proximinal set (due to Weierstrass theorem).

Note that we have not said anything about inner products here, so why not study minimum norm problems in detail in Banach spaces? The answer is due to one of the most famous unsolved problems in functional analysis: characterization of Chebyshev sets in general Banach spaces and in infinite-dimensional Hilbert spaces. What is known includes the following. (See Deutsch paper [17], a scanned version of which is available on the course web page.) • inner product space • In finite-dimensional Hilbert spaces, any Chebyshev set is closed, convex, and nonempty. • “Conversely,” in any inner product space, any complete and convex set is Chebyshev. (We will prove this later in 3.12). • normed space • Are all Chebyshev sets convex? In general: no. A nonconvex Chebyshev set (in an incomplete infinite-dimensional normed space within the space of finite-length sequences) is given in [18]. • In [3, p. 285], an example is given in a Banach space of a closed (and thus complete) subspace (hence convex) that is not a Chebyshev set. There is continued effort to characterize Chebyshev sets, e.g., [19–21]. Since the characterization of Chebyshev sets is unsolved in normed spaces, we focus primarily on closed convex sets in inner product spaces hereafter.   However, this fact is encouraging. If S is a nonempty closed subset of Rn , then x ∈ Rn : arg miny∈S kx − yk is nonunique has Lebesgue measure zero [16, p. 493]. Are all complete and bounded sets also proximinal? The answer is yes in finite-dimensional normed spaces since there all closed and bounded sets are compact. But the answer is “not necessarily” in infinite dimensional normed spaces, even in a Hilbert space in fact. Example. Let S = {(1 + 1/n)en : n ∈ N} ⊂ ℓp . Then S is bounded, and is complete since there are no “non-trivial” Cauchy sequences in S. Since d(0, (1 + 1/n)en ) = 1 + 1/n, we have d(0, S) = 1, yet there is no s ∈ S for which ks − 0k = 1.

c J. Fessler, November 5, 2004, 17:8 (student version) 

3.6

closed proximinal

compact

complete

Projectors If S is a Chebyshev set in a normed space (X , k·k ), then we can define a projector P : X → S that, for each point x ∈ X , gives the closest point P(x) ∈ S. In other words, for a Chebyshev set S, we can define legitimately P(x) = arg min kx − sk , s∈S

and “arg min” is well defined since there exists a unique minimizer when S is Chebyshev. When needed for clarity, we will write PS rather than just P . Such a projector satisfies the following properties. • P(x) ∈ S, ∀x ∈ S • kx − P(x)k ≤ kx − yk , ∀y ∈ S, i.e., kx − P(x)k = d(x, S ) • P(P(x)) = P(x) or more concisely: P2 = P. As noted above, closedness of S is a necessary condition for existence of a projector defined on all of X . ...................................................................................................................... Example. Consider X = R and S = [0, ∞). This is a Chebyshev set with P(x) = max{x, 0}. ..................................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example. Consider X = R2 and the (compact) set K = y ∈ R2 : kyk = 1 (the unit circle). There is not a unique minimizer of the distance to x = 0, the center of the unit circle. This why there is not a plethora of signal processing papers on “projections onto compact sets” (POKS?) methods.

3.3 Orthogonality Definition. In an inner product space, two vectors x,y are called orthogonal iff hx, yi = 0, which is denoted x ⊥ y . (This is consistent with the earlier cos−1 definition of angle.) Definition. A vector x is called orthogonal to a set S iff ∀s ∈ S, x ⊥ s, in which case we write x ⊥ S .

Definition. Two sets S and T in an inner product space (X , h·, ·i) are called orthogonal and written S ⊥ T iff hs, ti = 0, ∀s ∈ S, ∀t ∈ T . Exercise. Show x ⊥ S = [y1 , . . . , yn ] iff x ⊥ yi , i = 1, . . . , n. Lemma. (Pythagorean theorem)

Proof. kx + y k2 = kxk2 + kyk2 + 2 real(hx, y i) .

2

2

2

x ⊥ y =⇒ kx + yk = kxk + kyk . ✷ 2

2

2

The converse does not hold. Consider C and the vectors x = 1 and y = ı. Then kx + yk = kxk + kyk = 2 but x and y are not perpendicular since here hx, yi = xy∗ = −ı 6= 0.

c J. Fessler, November 5, 2004, 17:8 (student version) 

3.7

We first consider the easiest version of the general minimum norm problem, where the set of interest is actually a subspace of X . Theorem. ( ) Let X be an inner product space, M a subspace of X , and x a vector in X . • If there exists a vector m0 ∈ M such that kx − m0 k = d(x, M), then that m0 is unique. • A necessary and sufficient condition that m0 ∈ M be the unique minimizing vector in M is that the be orthogonal to M .

x − m0

Proof. Claim 1. If ∃m ∈ M (not necessarily unique) s.t. kx − m0 k = d(x, M ), then x − m0 ⊥ M .

Pf. We show by contradiction. Suppose m0 ∈ M is a minimizer, but x − m0 ⊥ ⊘M. Then ∃m ∈ M s.t. hx − m0 , mi = δ 6= 0, for some δ, where w.l.o.g. we assume kmk = 1. Consider m1 , m0 + δm ∈ M . 2

2

2

2

2

kx − m1 k = kx − m0 − δmk = kx − m0 k − δ ∗ hx − m0 , mi − δ hm, x − m0 i + |δ |2 = kx − m0 k −|δ |2 < kx − m0 k , contradicting the assumption that m0 is a minimizer. Claim 2. If ∃m0 ∈ M s.t. x − m0 ⊥ M , then m0 is a unique minimizer. Pf. For any m ∈ M , since m0 − m ∈ M , by the Pythagorean theorem: 2

2

2

2

kx − mk = k(x − m0 ) + (m0 − m)k = kx − m0 k + km0 − mk > kx − m0 k if m 6= m0 . So m0 , and only m0 , is the minimizer.

2

✷ x

M 0

m0

In words: in an inner product space, if a subspace is proximinal, then it is Chebyshev. The “good thing” about this theorem is that it does not require completeness of X , only the presence of an inner product. However, it does not prove the existence of a minimizer! Is this lack of an existence proof simply because “we” have not been clever enough to find it? Or, are there (incomplete) inner product spaces in which no such minimizer exists? (We cannot find an example drawing 2d or 3d pictures, since En is complete!) Example. Consider the Hilbert space ℓ2 with the incomplete (and hence non-closed) subspace M that consists of sequences with only finitely many nonzero terms, and consider x = (1, 1/2, 1/3, 1/4, . . .). 2 2 P For n ∈ N, let mn be identical to x for the first n terms, and then zero thereafter. Then kx − mn2k = ∞ k=n (1/k) , which approaches 0 as n → ∞, but {mn } converges to x ∈ / M . So d(x, M ) = inf m∈M kx − mk = 0. But clearly no m ∈ M achieves this minimum since x h...