Description

General Instructions

The following document contains the solutions to the theory-based questions for
Question 1

Given G = AT A where A ∈ Rm×n with m ≥ n. Now
GT = (AT A)T
= AT A
= G
i.e., G is a symmetric matrix ∈ Rn×n. Let λ be an eigenvalue of G for the non-zero eigen vector x.
Gx = λx
⟹ AT Ax = λx
⟹ xT AT Ax = xT λx
⟹ ∥Ax∥22 = λ∥x∥22
⟹
λ must be both real and non-negative to satisfy the above equation with λ = 0 iff ∥x∥22 = 0. But this contradicts the assumption that x is a non-zero vector. Thus the eigenvalues of G are real and positive.
Question 2

Let any matrix A ∈ Rm×n with rank r. Let v1 ∈ Rn be an unit vector in the row space of A.
Corresponding to v1 we can find a vector u1 which is an unit vector such that
Av1 = σ1u1
where σ1 will handle the scaling of the vector and u1 is the direction of the vector.
As we know that r = dim(C(A)) = dim(R(A)), so taking an orthonormal basis of R(A) i.e. {v1,⋯,vr}, we can find vectors {u1,⋯,ur} such that
Av = σiui ∀i = 1,⋯ r
Similarly finding the orthonormal basis of (A) i.e. {vr+1,⋯,vn}, we can find vectors
{ur+1,⋯,un} such that
Avi,n
Now, we can write the SVD of A as
A = UΣVT ⎤
0 ⋯ σr 0 ⋯ 0
= [u1 ⋯ ur ur+1 ⋯ ]
⋯ 0 0 ⋯ 0 Tn ⎦ σ1 ⋯ 0 ⎤ ⎤
= [u1 ⋯ ur ur+1 ⋯ n] ⋮
0 ⋯ 0
⎣vTr ⎦
⎦
⎡σ1 ⋯ 0
= [u1 ⋯ ur] ⋮ ⋱ ⋮ ⎣ 0 ⋯ σ
r
= ∑σiuivTi
i=1
Thus, we can say that {u1,⋯,ur} and {v1,⋯ are the left and the right singular matrices respectively.
Claim: We can choose the set {v1,⋯,vr} such that they are the eigenvectors of AT A.
Proof: As AT A is a symmetric matrix we can use spectral theorem and say that AT A is

diagonalizable, and we can write it as
where V is the matrix of eigenvectors of of AT A and V is an orthogonal matrix.

is the diagonal matrix of eigenvalues As rank(A) = rank(AT A), we take the eigenvectors corresponding to the non-zero eigenvalues of AT A and normalize them to get the set {v1,⋯,vr}.
□
Now, we have defined our right singular values as eigenvectors of AT A, which are orthogonal to each other. Thus, we can say that vTi vj = 0 for i ≠ j.
Finding the dot product of left singular vectors
⟨ui,uj⟩ ⟩
vTi AT Avj
jvj jvTi vj
= {0 i ≠ j σλiσjj i = j
Thus, the left singular vectors are also orthogonal to each other.
□
Question 3
a) Let A ∈ Rm×n and x ∈ Rn
⎡a11 a12 ⋯ a1n ⎤ a21 a22 ⋯ a2n
A =
⋮ ⋮ ⋱ ⋮
⎣
am1 am2 ⋯ amn⎦
⎡x1⎤
x2
x =
⋮
⎣xn⎦
n ⎤
a1ixi i=1
⎡ a11x1 + a12x2 + ⋯ + a1nxn ⎤ ∑n
a21x1 + a22x2 + ⋯ + a2nxn a2ixi
Ax == i=1
⋮
⎣
am1x1 + am2x2 + ⋯ + amnxn⎦ ⋮
n
∑
amixi⎦
i=1
1
∂y ∂
a a
A
m
xi ⎤
xi x x x x
xi⎦
=1
j
aijxixj
j j
x
∂x Ax
∥Ax − b∥2 = ⟨Ax − b⟩⟨Ax − b⟩
= (Ax − b)T (Ax − b)
= (Ax)T Ax + (Ax)T (−b) + (−b)T (Ax) + (−b)T (−b)
= xT AT Ax − xT AT b − bT Ax + bTb
Differentiating w.r.t x, and equating to 0, we get:
(ATA + (ATA)T)x − ATb − (bTA)T = 0
⟹ x = (ATA)−1ATb
The same result can also be obtained from the following differentiation:
xT(ATA + (ATA)T) − (ATb)T − bTA = 0
⟹ xT = bTA(ATA)−1
⟹ x = (ATA)−1ATb