1 Singular values - University of California, Berkeley

1 Notes on Singular value decomposition for Math 54 Recall that ifAis a symmetricn nmatrix, thenAhas real eigenvalues 1,.., n(possibly repeated), andRnhas an orthonormal basisv1,..,vn,where each vectorviis an eigenvector ofAwith eigenvalue i. ThenA=PDP 1wherePis the matrix whose columns arev1,..,vn, andDis the diagonalmatrix whose diagonal entries are 1,.., n. Since the vectorsv1,..,vnareorthonormal, the matrixPis orthogonal, , so we can alternatelywrite the above equation asA=PDPT.(1)A Singular value decomposition (SVD) is a generalization of this whereAis anm nmatrix which does not have to be symmetric or even Singular valuesLetAbe anm nmatrix.

2 Before explaining what a Singular value decom-position is, we first need to define the Singular values the matrixATA. This is a symmetricn nmatrix, so itseigenvalues are is an eigenvalue ofATA, then an eigenvector ofATAwith eigenvalue . We compute that Ax 2= (Ax) (Ax) = (Ax)TAx=xTATAx=xT( x) = xTx= x Ax 2 0, it follows from the above equation that x 2 0. Since x 2>0 (as our convention is that eigenvectors are nonzero), we deducethat 1,.., ndenote the eigenvalues ofATA, with repetitions. Orderthese so that 1 2 n 0.

3 Let i= i, so that 1 2 n numbers 1 2 n 0 defined above arecalled thesingular number of nonzero Singular values ofAequals therank rank of any square matrix equals the number of nonzero eigen- values (with repetitions), so the number of nonzero Singular values ofAequals the rank ofATA. By a previous homework problem,ATAandAhave the same kernel. It then follows from the rank-nullity theorem thatATAandAhave the same particular, ifAis anm nmatrix withm < n, thenAhas at mostmnonzero Singular values , because rank(A) Singular values ofAhave the following geometric anm nmatrix.

4 Then the maximum value of Ax , wherexranges over unit vectors inRn, is the largest Singular value 1, and this is achieved whenxis an eigenvector ofATAwith eigenvalue ,..,vnbe an orthonormal basis forRnconsisting of eigenvec-tors ofATAwith eigenvalues 2i. Ifx Rn, then we can expandxin thisbasis asx=c1v1+ +cnvn(2)for scalarsc1,..,cn. Sincexis a unit vector, x 2= 1, which (since thevectorsv1,..,vnare orthonormal) means thatc21+ +c2n= the other hand, Ax 2= (Ax) (Ax) = (Ax)T(Ax) =xTATAx=x (ATAx).By (2), sinceviis an eigenvalue ofATAwith eigenvalue 2i, we haveATAx=c1 21v1+ +cn the dot prodoct with (2), and using the fact that the vectorsv1.

5 ,vnare orthonormal, we get Ax 2=x (ATAx) = 21c21+ + 1is the largest Singular value , we get Ax 2 21(c21+ +c2n).Equality holds whenc1= 1 andc2= =cn= 0. Thus the maximumvalue of Ax 2for a unit vectorxis 21, which is achieved whenx= can similarly show that 2is the maximum of Ax wherexrangesover unit vectors that are orthogonal tov1(exercise). Likewise, 3is themaximum of Ax wherexranges over unit vectors that are orthogonal tov1andv2; and so Definition of Singular value decompositionLetAbe anm nmatrix with Singular values 1 2 n the number of nonzero Singular values ofA, or equivalently therank value decompositionofAis a factorizationA=U VTwhere: Uis anm morthogonal matrix.

6 Vis ann northogonal matrix. is anm nmatrix whoseithdiagonal entry equals theithsingularvalue ifori= 1,..,r. All other entries of are symmetric, let 1,.., nbe the eigenval-ues ofA, ordered so that| 1| | 2| | n|. The Singular values ofAare given by i=| i|(exercise). Letv1,..,vnbe orthonormal eigenvectorsofAwithAvi= ivi. We can then takeVto be the matrix whose columnsarev1,..,vn. (This is the matrixPin equation (1).) The matrix isthe diagonal matrix with diagonal entries| 1|,..,| n|. (This is almost thesame as the matrixDin equation (1), except for the absolute value signs.)

7 ThenUmust be the matrix whose columns are v1,.., vn, where the signnext toviis + when i 0, and when i<0. (This is almost the sameasP, except we have changed the signs of some of the columns.)3 How to find a SVDLetAbe anm nmatrix with Singular values 1 2 n 0, andletrdenote the number of nonzero Singular values . We now explain how tofind a SVD ,..,vnbe an orthonormal basis ofRn, whereviis an eigenvectorofATAwith eigenvalue (a) Avi = i.(b) Ifi6=jthenAviandAvjare compute(Avi) (Avj) = (Avi)T(Avj) =vTiATAvj=vTi 2jvj= 2j(vi vj).

8 Ifi=j, then since vi = 1, this calculation tells us that Avi 2= 2j,which proves (a). Ifi6=j, then sincevi vj= 0, this calculation shows that(Avi) (Avj) = anm nmatrix. ThenAhas a (not unique) Singular value decompositionA=U VT, whereUandVare as follows: The columns ofVare orthonormal eigenvectorsv1,..,vnofATA,whereATAvi= 2ivi. Ifi r, so that i6= 0, then theithcolumn ofUis 1iAvi. ByLemma , these columns are orthonormal, and the remaining columnsofUare obtained by arbitrarily extending to an orthonormal basis just have to check that ifUandVare defined as above, thenA=U VT.

9 Ifx Rn, then the components ofVTxare the dot productsof the rows ofVTwithx, soVTx= v1 xv2 x .Then VTx= 1v1 x 2v2 rvr .When we multiply on the left byU, we get the sum of the columns ofU,weighted by the components of the above vector, so thatU VTx= ( 1v1 x) 11Av1+ + ( rvr x) 1rAvr= (v1 x)Av1+ + (vr x) 0 fori > rby Lemma (a), we can rewrite the above asU VTx= (v1 x)Av1+ + (vn x)Avn=Av1vT1x+ +AvnvTnx=A(v1vT1+ vnvTn)x= the last line, we have used the fact that if{v1,..,vn}is an orthonormalbasis forRn, thenv1vT1+ +vnvTn=I(exercise).

10 Example (from Lay s book)Find a Singular value decomposition ofA=(4 11 1487 2).Step first need to find the eigenvalues ofATA. We compute thatATA= 8010040100 170 14040140 200 .We know that at least one of the eigenvalues is 0, because this matrix canhave rank at most 2. In fact, we can compute that the eigenvalues are 1= 360, 2= 90, and 3= 0. Thus the Singular values ofAare 1= 360 = 6 10, 2= 90 = 3 10, and 3= 0. The matrix in a singularvalue decomposition ofAhas to be a 2 3 matrix, so it must be =(6 100003 10 0).