Page 400 - Understanding Machine Learning

Linear Algebra
382

values. Then,
r

A = σ i u i v .
i
i=1
It follows that if U is a matrix whose columns are the u i ’s, V is a matrix whose columns
are the v i ’s, and D is a diagonal matrix with D i,i = σ i ,then

A = UDV .

Proof. Any right singular vector of A must be in the range of A (otherwise, the
singular value will have to be zero). Therefore, v 1 ,...,v r is an orthonormal basis
n
of the range of A. Let us complete it to an orthonormal basis of R by adding
r

σ
the vectors v r+1 ,...,v n . Define B = i=1 i u i v . It suffices to prove that for all i,
i
Av i = Bv i . Clearly, if i > r then Av i = 0and Bv i = 0 as well. For i ≤ r
we have
r

Bv i = σ j u j v v i = σ i u i = Av i ,
j
j=1
where the last equality follows from the definition.

The next lemma relates the singular values of A to the eigenvalues of A A
and AA .

Lemma C.4. v,u are right and left singular vectors of A with singular value σ iff
2
v is an eigenvector of A A with corresponding eigenvalue σ and u = σ −1 Av is an

2
eigenvector of AA with corresponding eigenvalue σ .

n
Proof. Suppose that σ is a singular value of A with v ∈ R being the corresponding
right singular vector. Then,
2

A Av = σ A u = σ v.
Similarly,
2

AA u = σ Av = σ u.

For the other direction, if λ = 0 is an eigenvalue of A A,with v being the cor-
responding eigenvector, then λ> 0 because A A is positive semidefinite. Let

√
σ = λ,u = σ −1 Av. Then,
√ Av
σu = λ√ = Av,
λ
and
1 λ

A u = A Av = v = σv.
σ σ

Finally, we show that if A has rank r then it has r orthonormal singular vectors.