Machine Learning Chapter 8 Solutions Problems Prove The Cauchy Schwartzs Inequality General Hilbert Space Solution

1

Solutions To Problems of Chapter 8

1. Prove the Cauchy – Schwartz’s inequality in a general Hilbert space.

Solution: We have to show that ∀x,y∈H,

|hx,yi| ≤ kxkkyk,

kyk2.

Thus

0≤ kxk2−|hx,yi|2

kyk2,

2. Show a) that the set of points in a Hilbert space H,

C={x:kxk ≤ 1}

is a convex set, and b) the set of points

2

is a nonconvex one.

Solution: From the definition of a Hilbert space (see Appendix of this

chapter) the norm is the induced by the inner product norm, i.e.,

kxk= (hx,xi)

1

2.

a) Let us now consider two points, x1,x2∈H, such that

kx1k ≤ 1,kx2k ≤ 1,

and let

3. Show the first order convexity condition.

Solution: Assume that fis convex. Then

fλy+ (1 −λ)x≤λf(y) + (1 −λ)f(x)

or

fx+λ(y−x)−f(x)≤λf(y)−f(x).

Taking λ−→ 0, we can employ the Taylor expansion and get

4. Show that a function fis convex, iff the one-dimensional function,

g(t) := f(x+ty),

is convex, ∀x,yin the domain of definition of f.

Solution: Observe that,

g(λt1+ (1 −λ)t2) = f(x+λt1y+ (1 −λ)t2y)

5. Show the second order convexity condition.

Hint: Show the claim first for the one-dimensional case and then use the

result of the previous problem, for the generalization.

Solution: We start with the one-dimensional case. Let a function f(x)

be convex. Then we know from the first order convexity condition that

6. Show that a function

f:Rl7−→ R

is convex iff its epigraph is convex.

Solution: a) Assume fto be convex. We have to show that its epigraph

f(x1)≤r1, f(x2)≤r2.(14)

Combining (11) and (14) we get

f(x)≤λf(x1) + (1 −λ)f(x2)≤λr1+ (1 −λ)r2=r,

7. Show that if a function is convex, then its lower level set is convex for any ξ.

Solution: Let the function fbe convex and two points, x,y, which lie in

8. Show that in a Hilbert space, H, the parallelogram rule,

kx+yk2+kx−yk2= 2 kxk2+kyk2,∀x,y∈H.

holds true.

Solution: The proof is straightforward from the respective definitions and

the properties of the inner product relation.

9. Show that if x,y∈H, where His a Hilbert space, then the induced by

the inner product norm satisfies the triangle inequality, as required by any

norm, i.e.,

kx+yk ≤ kxk+kyk

Solution: By the respective definitions we have

kx+yk2:= hx+y,x+yi=kxk2+hx,yi+hy,xi+kyk2,

10. Show that if a point x∗is a local minimizer of a convex function, it is nec-

essarily a global one. Moreover, it is the unique minimizer if the function

is strictly convex.

Solution: Let x∗be a local minimizer. Then, there exists ǫ > 0 and

y∗/∈B[0, ǫ] such that

f(x∗)≤f(x∗+ ∆),∀∆∈B[0, ǫ],

11. Let Cbe a closed convex set in a Hilbert space, H. Then show that

∀x∈H, there exists a point, denoted as PC(x)∈C, such that

kx−PC(x)k= min

y∈Ckx−yk.

Solution: Let x6∈ C, otherwise it is trivial. Let ρbe the largest lower

bound of kx−yk,y∈C, i.e.,

ρ:= inf

From the parallelogram law, we can write

8

However, since Cis convex, the point 1

2(xn+xm)∈Cand we deduce

That is, xnis a Cauchy sequence and since His Hilbert the sequence

converges to a point x∗. Moreover it converges in C, since Cis closed,

i.e., x∈C. Hence we have

kx−x∗k=kx−xn+xn−x∗k

12. Show that the projection of a point x∈Honto a non-empty closed convex

set, C⊂H, lies on the boundary of C.

Solution: Assume that PC(x) is an interior point of C. By the defini-

tion of interior points, ∃δ > 0 such that

13. Derive the formula for the projection onto a hyperplane in a (real) Hilbert

space, H.

Solution: Let us first show that a hyperplane, H, is a closed convex set.

Convexity is shown trivially. To show closeness, let yn∈H−→ y∗. We

will show that y∗∈H. Let

hθ,zi+θ0=0hx−z,x−zi.

Using Lagrange multipliers, we obtain the Lagrangian

L(z, λ) = hx−z,x−zi − λhθ,zi+θ0.

For those not familiar with infinite dimensional spaces, it suﬃces to say

that similar rules of differentiation apply, although the respective defini-

14. Derive the formula for the projection onto a closed ball, B[0, ρ].

Solution: The closed ball is defined as

B[0, ρ] = {y:kyk ≤ ρ}.

We have already seen (Problem 2) that it is convex. Let us show the

closeness. Let

kzk2=ρ2,

since the projection is on the boundary. Taking the gradient of the La-

grangian we get

2(z−x) + 2λz= 0,

or

z=1

z=−ρ

kxkx.

11

From the two possible vectors, we have to keep the one that has the smaller

distance from x. However,



15. Find an example of a point whose projection on the ℓ1ball is not unique.

Solution: The ℓ1ball of radius ρ= 1 in Rlis defined as

S1[0, ρ] = {y:X

i=1

|yi| ≤ ρ}.

16. Show that if C⊂H, is a closed convex set in a Hilbert space, then ∀x∈H

and ∀y∈C, the projection PC(x) satisfies the following properties:

12

•Real{hx−PC(x),y−PC(x)i} ≤ 0.

• kPC(x)−PC(y)k2≤Real{hx−y, PC(x)−PC(y)i}.

Solution: We know that PC(x)∈C. Hence, due to the convexity of C,

∀λ∈[0,1]

λy+ (1 −λ)PC(x)∈C.

Hence

17. Prove that if Sis a closed subspace S⊂Hin a Hilbert space H, then

∀x,y∈H,

hx, PS(y)i=hPS(x),yi=hPS(x), PS(y)i.

and

PS(ax+by) = aPS(x) + bPS(y).

Hint: Use the result of Problem 18.

18. Let Sbe a closed convex subspace in a Hilbert space H,S⊂H. Let S⊥be

the set of all elements x∈Hwhich are orthogonal to S. Then show that,

a) S⊥is also a closed, subspace, b) S∩S⊥={0}, c) H=S⊕S⊥; that

is, ∀x∈H,∃x1∈Sand x2∈S⊥:x=x1+x2, where x1,x2are unique.

Solution:

a) We will first prove that S⊥is a subspace. Indeed if x1∈S⊥and

x2∈S⊥then

hx1,yi=hx2,yi= 0,∀y∈S.

14

where the Cauchy-Schwartz inequality has been used. The last inequality

b) Let x∈S∩S⊥. By definition, since it belongs to both subspaces,

c) Let x∈H. We have that

We apply the same for jy. Then we have that

hx−PS(x), jyi=−jhx−PS(x),yi.

x=x3+x4,x3∈S, x4∈S⊥.

15

Then

x1+x2=x3+x4

or

S→x1−x3=x4−x2∈S⊥,

since x−PS(x)∈S⊥. Note that we used the fact that if y∈Sthen

since

19. Show that the relaxed projection operator is a non-expansive mapping.

Solution: By the respective definitions we have,

kTC(x)−TC(y)k=kx+µ(PC(x)−x)−y−µ(PC(y)−y)k

=k(1 −µ)(x−y) + µ(PC(x)−PC(y))k.

20. Show that the relaxed projection operator is a strongly attractive map-

ping.

Solution: By the respective definition we have,

kTC(x)−yk2=kx+µ(PC(x)−x)−yk2

=kx−yk2+µ2kPC(x)−xk2+ 2µReal{hx−y, PC(x)−xi}

21. Give an example of a sequence in a Hilbert space H, which converges

weakly but not strongly.

Solution: Define the sequence of points xn∈l2,

xn={0,0,…,1,0,0, . . .}:= {δni}, i = 0,1,2, . . .

22. Prove that if C1. . . CKare closed convex sets in a Hilbert space H, then

the operator

T=TCK· · · TC1,

is a regular one; that is,

kTn−1(x)−Tn(x)k −→ 0, n −→ ∞,

Fact 2:

Fix(T) =

K

\

k=1

Ck:= C.

Indeed, if x∈Cthen

TKTK−1· · · T1(x) = TKTK−1· · · T2(x) = . . .

previous two facts are valid for general Hilbert spaces.

Fact3: If Cis a closed subspace, then Tk, k = 1, . . . , K, and T=

TKTK−1· · · T1are linear operators. The proof is trivial from the respec-

tive linearity of the projection operators, Pk, k = 1, . . . , K. This is also

true for general Hilbert spaces.

kx−T1(x)k=µ2

1kx−P1(x)k2≤µ1

2−µ1kx−yk2− kT1(x)−yk2.

Let now

kx−T2T1(x)k2=kx−T1(x) + T1(x)−T2T1(x)k2