Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
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
i=1
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
i=1
i=1
1) = p, we get
l
X
X
1
q
X
1
p
X
1
p
Dividing by Pl
i=1(|xi|+|yi|)p1
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
ˆ
θ=XTXXT−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=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
21 + 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−Iz.
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||11−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
