Machine Learning Chapter 9 Solutions Problems Show That Are Real Numbers Then Prove The Cauchyschwarz

1

Solutions To Problems of Chapter 9

9.1. Show that if xi, yi, i = 1,2, . . . , l, are real numbers, then prove the

Cauchy-Schwarz inequality:

l

X

i=1

xiyi!2

≤ l

X

i=1

x2

i! l

X

i=1

y2

i!.

Solution: Consider the identity

l

X

i=1

(zxi+yi)2≥0,∀z∈R.

9.2. Prove that the l2(Euclidean) norm is a true norm, i.e., it satisfies the

four conditions that define a norm.

Hint: To prove the triangle inequality, use the Cauchy-Schwarz in-

equality.

Solution: To prove the three first conditions, i.e.,

i=1

9.3. Prove that any function that is a norm is also a convex function.

Solution: Let a function f:Rl7−→ [0,∞), which is a norm. Then

9.4. Show Young’s inequality for nonnegative real numbers aand b,

ab ≤ap

p+bq

q,

for ∞>p>1 and ∞> q > 1 such that

1

p+1

q= 1.

Solution: First, it is obvious that the inequality holds if aand/or bare

zero. Then, we turn our attention to the case that both of them are

9.5. Prove Holder’s inequality for lpnorms,

||xTy||1=

l

X

i=1

|xiyi| ≤ ||x||p||y||q= l

X

i=1

|xi|p!

1

p q

X

i=1

|yi|q!1

q

,

for p≥1 and q≥1 such that

1

p+1

q= 1.

Hint: Use Young’s inequality.

Solution: First note that if p= 1 and q=∞then the inequality

is obvious, since in this case ||y||∞= max{|y1|,…,|yl|}. Thus we

9.6. Prove Minkowski’s inequality,

l

X

i=1

(|xi|+|yi|)p!

1

p

≤ l

X

i=1

|xi|p!

1

p

+ l

X

i=1

|yi|p!

1

p

,

for p≥1.

Hint: Use Holder’s inequality together with the identity:

(|a|+|b|)p= (|a|+|b|)p−1|a|+ (|a|+|b|)p−1|b|.

Solution: The result is obvious for p= 1.We will prove it for p > 1.

In the given identity, put in place of a xiand in the place of b yiand

add to get

i=1

1) = p, we get

l

X

1

q

X

1

p

X

1

p

Dividing by Pl

i=1(|xi|+|yi|)p1

9.7. Prove that for p≥1 the lpnorm is a true norm.

Solution: The first three conditions for a function to be a norm are

9.8. Use a counterexample to show that the lpnorm for 0 <p<1 is not a

true norm and it violates the triangle condition.

Solution: Consider the two vectors in the l-dimensional space

x= [1,0,…,0]T,y= [0,0,…,1]T.

9.9. Show that the null space of a full rank N×lmatrix Xis a subspace

of dimensionality l−N, for N < l.

Solution: By the definition of a null space, i.e.,

N={z:Xz=0},

5

9.10. Show, using Lagrange multipliers, that the l2minimizer in (9.18) ac-

cepts the closed form solution

ˆ

θ=XTXXT−1y.

Solution: The `2minimizer task is given by

minimize ||θ||2

9.11. Show that the necessary and suffcient condition for a θto be a mini-

mizer of

minimize : ||θ||1

s.t. Xθ=y,

is the following

value of t,θiand θi+tziwill have the same sign, whenever θi6= 0.

Hence, the previous inequality becomes

X

i:θi=0

|tzi|+X

i:θi6=0

sign(θi)(θi+tzi)≥X

i:θi6=0

sign(θi)θi,or

tX

sign(θi)zi+X

|tzi| ≥ 0,or

(b) Suffciency

Let X

i:θi6=0

sign(θi)zi

≤X

i:θi=0

|zi|(2)

7

9.12. Prove that if the `1norm minimizer is unique, then the number of its

components, which are identically zero, must be at least as large as

the dimensionality of the null space of the corresponding input matrix.

Solution: Assume that

ξ:= card{i:ˆ

θi= 0}<dim(null(X)) := m.

θiξ

u1iξ· · · umiξ

am

0. This implies also that the nonzero z, defined as z=Pm

j=1 ajuj,

satisfies zi1=· · · =ziξ= 0. If we plug this last result into Lemma ??

i:ˆ

θi6=0

i:ˆ

θi=0

9.13. Show that the l1norm is a convex function (as all norms), yet it is not

strictly convex. In contrast, the squared Euclidean norm is a strictly

convex function.

Solution: From the definition of convexity we have that

f(λx+ (1 −λ)y)≤λf(x) + (1 −λ)f(y),

and for strict convexity the strict inequality is valid. For the l1norm

we have

i

Following a similar path, and exploiting the Cauchy-Schwartz inequal-

ity (which becomes equality for co-linear vectors) show that the `2

norm function is not strictly convex.

9.14. Construct in the 5-dimensional space a matrix that has a) rank equal

to five and spark equal to four, b) rank equal to five and spark equal

to three and c) rank and spark equal to four.

Solution: What we do here can obviously be applied in any Rlspace.

Consider a basis in the space, e.g.,

1



0



0



0



0



9.15. Let Xbe a full row rank N×lmatrix, with l > N. Derive the Welch

bound for the mutual coherence µ(X),

µ(X)≥sl−N

N(l−1).(5)

The bound for N=lis obviously zero, since the matrix can be or-

thogonal.

Solution: Without harming generality, let us assume that the columns

xc

l

Tx1. . . xc

l

Txc

l

We know that the trace of Gis equal to the sum of its eigenval-

i=1

i,(7)

i=1

N.(8)

However from linear algebra, we know that the Frobenius norm sat-

isfies the following: ([Golu 83]. This is true for any matrix and it

is easily shown by the definition of the Frobenius norm and the fact

i=1

j=1

Txc

N.(11)

i=1

j=1,j6=i

N,(12)

i=1

j=1,j6=i

Txc

N.(13)

i6=j(|xc

i

j|2)≥1

l2−l

j=1,j6=i

i

j|2,(14)

9.16. Let Xbe a N×lmatrix. Then prove that its spark is bounded as

spark(X)≥1 + 1

µ(X),

where µ(X) is the mutual coherence of the matrix.

Hint: Consider the Gram matrix XTXand the following theorem,

xc

l

Tx1. . . xc

l

Txc

l

12

Observe that all diagonal elements are equal to one. Moreover, all

(17) implies that this will also be true for any m≤p. Thus, if this is

valid, then any m≤pcolumns are linearly independent, hence

spark(X)≥p+ 1,(18)

9.17. Show that if the underdetermined system of equations y=Xθaccepts

a solution such that

||θ||0<1

21 + 1

µ(X)

then the l1minimizer is equivalent to the l0one. Assume that the

where θis the solution with l0norm that satisfies the given condition.

Let us assume, without loss of generality, that the k=||θ||0nonzero

elements are the first kelements of the vector. Then we obtain

k

X

j=1

(|θj+zj|−|θj|) + X

j>k

|zj| ≤ 0.

implies that

XTXz=0⇒ −z=XTX−Iz.

Hence the following is true

−zi=

l

X

xc

i

Txc

jzj−zi=

l

X

xc

i

Txc

jzj,

or

|zi| ≤ µ(X)

1 + µ(X)||z||1⇒ −2

k

X

i=1

|zi| ≥ −2kµ(X)

1 + µ(X)||z||1.

The last one combined with (20) results in

||z||11−2kµ(X)

k

X

|zi| ≤ 0.

9.18. Prove that if the RIP of order kis valid for a matrix Xand δk<1 ,

then any m<kcolumns of Xare necessarily linearly independent.

Solution: Recall from the definition of RIP that it is valid for any k

sparse vector, that is, for any vector that has up to knonzero ele-

9.19. Show that if Xsatisfies the RIP of order kand some isometry constant

δkso does the product XΨ if Ψ is an orthonormal matrix.

Solution: This is a direct consequence of the properties of the ma-

Bibliography

[Horn 85] Horn R.A., Johnson C.R. Matrix Analysis, Cambridge University

Press, New York 1985.

[Golu 83] Golub G.H., Van Loan C.F. Matrix Computations, The John Hop-

kins University Press, Baltimore, 1983.

15