Understanding Machine Learning: From Theory to Algorithms

432 Linear Algebra

lemmaC.3 LetA∈Rm,nbe a matrix of rankr. Assume thatv 1 ,...,vris an

orthonormal set of right singular vectors ofA,u 1 ,...,uris an orthonormal set

of corresponding left singular vectors ofA, andσ 1 ,...,σrare the corresponding

singular values. Then,

A=

∑r

i=1

σiuiv>i.

It follows that ifUis a matrix whose columns are theui’s,Vis a matrix whose

columns are thevi’s, andDis a diagonal matrix withDi,i=σi, then

A=UDV>.

Proof Any right singular vector ofAmust be in the range ofA>(otherwise,

the singular value will have to be zero). Therefore,v 1 ,...,vris an orthonormal

basis of the range ofA. Let us complete it to an orthonormal basis ofRnby

adding the vectorsvr+1,...,vn. DefineB=

∑r

i=1σiuiv

>i. It suffices to prove

that for alli,Avi=Bvi. Clearly, ifi > rthenAvi= 0 andBvi= 0 as well.

Fori≤rwe have

Bvi=

∑r

j=1

σjujv>jvi=σiui=Avi,

where the last equality follows from the definition.

The next lemma relates the singular values ofAto the eigenvalues ofA>A

andAA>.

lemmaC.4 v,uare right and left singular vectors ofAwith singular valueσ

iffvis an eigenvector ofA>Awith corresponding eigenvalueσ^2 andu=σ−^1 Av

is an eigenvector ofAA>with corresponding eigenvalueσ^2.

Proof Suppose thatσis a singular value ofAwithv∈Rnbeing the corre-

sponding right singular vector. Then,

A>Av=σA>u=σ^2 v.

Similarly,

AA>u=σAv=σ^2 u.

For the other direction, ifλ 6 = 0 is an eigenvalue ofA>A, withvbeing the

corresponding eigenvector, thenλ >0 becauseA>Ais positive semidefinite. Let

σ=

√

λ,u=σ−^1 Av. Then,

σu=

√

λ

A√v

λ

=Av,

and

A>u=

1

σA

>Av=λ

σv=σv.