Description
1. Here we continue the problem studied in Activity 11. Let a 4-by-2 matrix X have
SVD X = USV T where U =
1
2
1 1
1 −1
1 −1
1 1
, S =
”
1 0
0 γ
#
, and V = √
1
2
”
1 1
1 −1
#
Let y =
1
0
0
1
.
a) The ratio of the largest to the smallest singular values is termed the condition
number of X. Find the condition number if γ = 0.1, and γ = 10−8
. Solve
Xw = y for w and find ||w||2
2
for these two values of γ.
b) A system of linear equations with a large condition number is said to be “illconditioned”. One consequence of an ill-conditioned system of equations is solutions with large norms as you found in the previous part of this problem.
A second
consequence is that the solution is very sensitive to small errors in y such as may
result from measurement error or numerical error. Suppose y =
1 +
0
0
1
.
Write
w = wo + w where wo is the solution for arbitrary γ when = 0 and w
is the
perturbation in that solution due to some error 6= 0. How does the norm of the
perturbation due to 6= 0, ||w
||2
2
, depend on the condition number? Find ||w
||2
2
for = 0.01 and γ = 0.1 and γ = 10−8
.
c) Now consider a “low-rank” inverse. Instead of writing
(XTX)
−1XT =
X
p
i=1
1
σi
viu
T
i
where p is the number of columns of X (assumed less than the number of rows),
we approximate
(XTX)
−1XT ≈
Xr
i=1
1
σi
viu
T
i
In this approximation we only invert the largest r singular values, and ignore all
of them smaller than σr. Use r = 1 in the low-rank inverse to find w = wo + w
where y =
1 +
0
0
1
as in part b). Compare the results to part b).