Problem Set 3

STAT 309: MATHEMATICAL COMPUTATIONS I
FALL 2014
PROBLEM SET 3
1. Let A ∈ Cm×n and b ∈ Cm . We will discuss a variant of Ax ≈ b where the error occurs only in
A. Note that in ordinary least squares we assume that the error occurs only in b while in total
least squares we assume that it occurs in both A and b.
(a) Show that if 0 6= x ∈ Cm , then
2
∗ 2
xx
= kAk2F − kAxk2 .
A I −
x∗ x F
x∗ x
(b) Show that the matrix
(b − Ax)x∗
∈ Cm×n
x∗ x
has the smallest 2-norm of all m × n matrices E that satisfy
E=
(A + E)x = b.
(c) What are the solutions of
min
kEk2
and
min
(A+E)x=b
kEkF ?
(A+E)x=b
The minimum is taken over all E ∈ Rm×n such that (A + E)x = b is consistent (i.e., has a
solution).
(d) Given a ∈ Cn , b ∈ Cm , and δ > 0. Show how to solve the problems
min kEa − bk2
kEkF ≤δ
max kEa − bk2
and
kEkF ≤δ
over all E ∈ Cm×n .
2. Let u ∈ Rn , u 6= 0. A Householder matrix Hu ∈ Rn×n is defined by
Hu = I −
2uuT
.
kuk22
(a) Show that Hu is both symmetric and orthogonal.
(b) Show that for any α ∈ R, α 6= 0,
Hαu = Hu .
In other words, Hu only depends on the ‘direction’ of u and not on its ‘magnitude’.
(c) In general, given a matrix M ∈ Rn×n and a vector x ∈ Rn , computing the matrix-vector
product M x requires n inner products — one for each row of M with x. Show that Hu x
can be computed using only two inner products.
(d) Given a, b ∈ Rn where a 6= b and kak2 = kbk2 . Find u ∈ Rn , u 6= 0 such that
Hu a = b.
(e) Show that u is an eigenvector of Hu . What is the corresponding eigenvalue?
(f) Show that every v ∈ span{u}⊥ (cf. orthogonal complement in Homework 2) is an eigenvector of Hu . What are the corresponding eigenvalues? What is dim(span{u}⊥ )?
Date: October 24, 2014 (Version 1.0); due: October 31, 2014.
1
2
STAT 309 ASSIGNMENT 3
(g) Find the eigenvalue decomposition of Hu , i.e., find an orthogonal matrix Q and a diagonal
matrix Λ such that
Hu = QΛQT .
3. Let A ∈ Rm×n and suppose its complete orthogonal decomposition is given by
L 0 T
Q ,
A = Q1
0 0 2
where Q1 and Q2 are orthogonal, and L is an nonsingular lower triangular matrix. Recall that
X ∈ Rn×m is the unique pseudo-inverse of A if the following Moore-Penrose conditions hold:
(i) AXA = A,
(ii) XAX = X,
(iii) (AX)T = AX,
(iv) (XA)T = XA
and in which case we write X = A† .
(a) Let
−1
L
Y
A− = Q2
QT
Y 6= 0.
1,
0
0
Which of the four conditions (i)–(iv) are satisfied?
(b) Prove that
−1 L
0 T
A† = Q2
Q
0
0 1
by letting
X11 X12
†
A = Q2
QT
1
X21 X22
and by completing the following steps:
• Using (i), prove that X11 = L−1 .
• Using the symmetry conditions (iii) and (iv), prove that X12 = 0 and X21 = 0.
• Using (ii), prove that X22 = 0.
4. Let A ∈ Rm×n , b ∈ Rm , and c ∈ Rn . We are interested in the least squares problem
min kAx − bk22 .
x∈Rn
(4.1)
(a) Show that x is a solution to (4.1) if and only if x is a solution to the augmented system
I A r
b
=
.
(4.2)
0
AT 0 x
(b) Show that the (m + n) × (m + n) matrix in (4.2) is nonsingular if and only if A has full
column rank.
(c) Suppose A has full column rank and the QR decomposition of A is
R
A=Q
.
0
Show that the solution to the augmented system
I A y
b
=
c
AT 0 x
can be computed from
z=R
−T
c,
d1
= QT b,
d2
STAT 309 ASSIGNMENT 3
and
3
z
x = R (d1 − z),
y=Q
.
d2
(d) Hence deduce that if A has full column rank, then
−1
A† = R−1 QT
1
where Q = [Q1 , Q2 ] with Q1 ∈ Rm×n and Q2 ∈ Rm×(m−n) . Check that this agrees with the
general formula derived for a rank-retaining factorization A = GH in the lectures.
5. Let A ∈ Rm×n . Suppose we apply QR with column pivoting to obtain the decomposition
R S
A=Q
ΠT
0 0
where Q is orthogonal and R is upper triangular and invertible. Let xB be the basic solution,
i.e.,
−1 R
0 T
xB = Π
Q b,
0
0
ˆ = A† b. Show that
and let x
ˆ k2
kxB − x
≤ kR−1 Sk2 .
kˆ
xk2
(Hint: If
u
c
T
Π x=
and Q b =
,
v
d
consider the associated linearly constrained least-squares problem
T
min kuk22 + kvk22
s.t. Ru + Sv = c
and write down the augmented system for the constrained problem.)
6. Given a symmetric A ∈ Rn×n , 0 6= x ∈ Rn , and b ∈ Rn . Let
r = b − Ax
Consider the QR decomposition
[x, r] = QR
and observe that if Ex = r, then
(QT EQ)(QT x) = QT r.
Show how to compute a symmetric E ∈ Rn×n so that it attains
min
kEkF .
(A+E)x=b

Download Report