## 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

## Reviews

There are no reviews yet.