Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
1
Solutions To Problems of Chapter 6
6.1. Show that if A∈Cm×mis nonnegative definite, its trace is nonnegative.
Solution: By the definition of a positive semidefinite matrix, ∀x∈Cm,
6.2. Show that under a) the independence assumption of successive observation
vectors and b) the presence of white noise independent of the input, then
the LS estimator is asymptotically distributed according to the normal
distribution, i.e.,
√N(θ−θ0)−→ N(0, σ2Σ−1
x),
where σ2is the noise variance and Σxthe covariance matrix of the input
observation vectors, assuming that it is invertible.
Solution: Recall that according to the law of large numbers, we have
1
N
N
X
n=1
xnxT
n−→ Σx,
Thus, the covariance matrix of the sum of independent terms in
1
√N
N
X
xnηn(1)
n=1
get
√N(θ−θ0) = 1
N
N
X
n=1
xnxT
n!−1 1
√N
N
X
n=1
xnηn!
6.3. Let X∈Cm×l. Then show that the two matrices,
XXHand XHX,
have the same nonzero eigenvalues.
Solution: Let λibe an eigenvalue of XHX. Then
(XHX)vi=λivi⇒
X(XHX)vi=λiXvi⇒
6.4. Show that if X∈Cm×l, then the eigenvalues of XXH(XHX) are real
and nonnegative. Moreover, show that if λi6=λj,vi⊥vj.
Solution: By the definition we have,
XXHvi=λivi⇒
vH
iXXHvi=λikvik2⇒
6.5. Let X∈Cm×l. Then show that if viis the normalized eigenvector of
XHX, corresponding to λi6= 0, then the corresponding normalized eigen-
vector uiof XXHis given by,
ui=1
√λi
Xvi
Solution: From Problem 6.3, we know that the eigenvectors XXHand
XHXcorresponding to λiare related as,
qi=Xvi.
By the respective definition we have
XXHvi=λivi⇒
6.6. Show Eq. (6.19).
Solution: From the respective definitions, we get
6.7. Show that the right singular vectors, v1,...,vr, corresponding to the r
singular values of a rank-rmatrix, X, solve the following iterative opti-
mization task: compute vk, k = 2,3, . . . , r, such as,
minimize 1
2||Xv||2,
subject to ||v||2= 1,
v⊥ {v1,...,vk−1}, k 6= 1,
where || · || denotes the Euclidean norm.
Solution: We start with k= 1, to solve the (Rayleigh ratio) task
1
The corresponding Lagrangian becomes
v
2||Xv||2, k = 1,2, . . . , r,
s.t. ||v||2= 1,
v⊥v1.,
The Lagrangian is now given by,
6.8. Show that projecting the rows of Xonto the k-rank subspace, Vk=
span{v1,...,vk}, results in the largest variance, compared to any other
k-dimensional subspace, Zk.
Solution: The projection of a row xnof Xonto Vkis given by
ˆ
xn=
k
X
i=1
(xT
nvi)vi,
i=1
Then, projecting all the rows of the matrix onto Vkresults in a total
variance,
N
X
n=1 ||ˆ
xn||2=
N
X
n=1
k
X
i=1
(xT
nvi)2=
k
X
i=1 ||Xvi||2.(5)
to (5).
•Assume that Vk−1is the optimal (k−1)-dimensional subspace. Build
an orthonormal basis in any Zk, around a zkso that
6
6.13),
r
X
r
X
6.9. Show that the squared Frobenius norm is equal to the sum of the squared
singular values.
Solution: By the definition of the Frobenius norm,
kXk2
F:= X
6.10. Show that the best krank approximation of a matrix Xof rank r > k, in
the Frobenius norm sense, is given by:
ˆ
X=
k
X
i−1
σiuivT
i,
where σiare the singular values and vi,ui, i = 1,2, . . . , r, are the right
and left singular vectors of X, respectively. Then show that the approxi-
mation error is given by:
v
u
u
t
r
X
i=k+1
σ2
i.
Solution: Let,
ˆ
X:=
k
X
i=1
σiuivT
i=
k
X
i=1
(Xvi)vT
i.(6)
From (6), it is readily deduced that the rows of ˆ
X,ˆ
xT
n, n = 1,2, . . . , N,
are projections of the respective rows of Xonto the subspace spanned by
equivalent with the smallest error norm ||en||. Hence, the corresponding
Frobenius norm,
||X−ˆ
X||2
F=
N
X
n=1 ||en||2,
is the smallest one. We have proved that from all possible approximations
For the error matrix we have that,
E=
r
X
i=k+1
σiuivT
i.
Thus,
X
r
X
6.11. Show that ˆ
X, as given in Problem 6.10, also minimizes the spectral norm
and that,
||X−ˆ
X||2=σk+1.
Solution: We first show that,
||X−ˆ
X||2=σk+1.
i=1
Then, we have that
||(X−ˆ
X)v||2=||
r
X
i=k+1
(σiuivT
i)
l
X
j=1
ajvj||2
=||
r
X
aiσiuivT
ivi||2
r
X
Bis a rank kmatrix, its null space will be of dimension l−k. Thus, by
basic dimension arguments,
S:= N(B)∩span{v1,...,vk,vk+1} 6=∅.
Hence, ∃z6=0∈S,||z|| = 1. Then, by the definition of the spectral
norm, and taking into account that Bz=0, we get
i=1
j=1
=||
k+1
X
i=1
σiui(vT
iz)||2
k+1
X
k+1
X
6.12. Show that the Frobenius and spectral norms are unaffected by multipli-
cation with unitary matrices, i.e.,
kXkF=kQXUkF
10
and
kXk2=kQXUk,
if QQT=UUT=I.
Solution: The proof for the Frobenius was given in Problem 6.9. From the
definition of the the spectral norm, we have that
kXk2=σ1,
6.13. Show that the null and range spaces of a m×lmatrix, X, of rank rare
given by,
N(X) = span{vr+1,...,vl},
R(X) = span{u1,...,ur},
where
X= [u1,...,um]D O
O O
vT
1
.
.
.
vT
l
.
Solution: Recall that
X=
r
X
i=1
σiuivT
i.
Hence, ∀a∈Rl,
r
X
6.14. Show that for the ridge regression
ˆ
y=
l
X
i=1
σ2
i
λ+σ2
i
(uT
iy)ui
11
Solution: We have that
ˆ
y=UlDV T
lVlDUT
lUlDV T
l+λI−1VlDUT
ly
=UlDV T
lVlD2VT
l+λVlVT
l−1VlDUT
ly
i=1
λ+σ2
i
6.15. Show that the normalized steepest descent direction of J(θ) at a point θ0,
for the quadratic norm kvkPis given by
v=1
||P−1∇J(θ0)||P
P−1∇J(θ0).
Solution: The task is
minimize
v
vT∇J,
s.t. vTPv= 1.
2λ=(∇J)TP−1∇J
6.16. Justify why the convergence of Newton’s iterative minimization method
is relatively insensitive on the Hessian matrix.
Hint: Let Pbe a positive definite matrix. Define a change of variables,
˜
θ=P1
2θ,
12
and carry gradient descent minimization based on the new variable.
Solution: Let ˜
θ=P1
2θ.
Note that kθk2
p:= θTPθ. Also, define,
θ(˜
Then the gradient descent step for ˜
J(˜
θ) will be
be equal to
6.17. Show that the steepest descent direction, v, of J(θ) at a point, θ0, con-
strained to
kvk1= 1,
is given by ek, where ekis the standard basis vector in the direction, k,
such that
=kvk1kak∞.
Hence,
where eithe direction corresponding to the component associated with
kak∞.
b) Since the `1norm is not differentiable, the notion of subgradient will
be mobilized. We have
where ∂kvk1
∂vis the subdifferential set for kvk1. Then, taking into account
the subgradient of the absolute value, (10) can be written component wise
as
{1}, vj>0
which guarantees that
6.18. Show that the TLS solution is given by,
ˆ
θ=XTX−¯σ2
l+1I−1XTy,
where ¯σl+1 is the smallest singular value of [X.
.
.y].
Solution: By the respective definition we have that,
XTX XTy
yTXyTyˆ
θT LS
−1= ¯σ2
l+1 ˆ
θT LS
−1,
6.19. Given a set of centered data points, (yn,xn)∈Rl+1, derive a hyperplane
aTx+y= 0,
which crosses the origin, such as the total square distance of all the points
from it to be minimum.
Solution: Let
wT= [aT,1]T.
15
Then we will search for the wgiven by
minimize
w
N
X
kwk2.
Let
xT
1y1
zT
1
Then,
N
X
n=1 |wTzn|2=wTZTZw.
