1 Singular values

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

2 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. 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. 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 .

3 ,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,..,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.

4 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.)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.

5 (b) Ifi6=jthenAviandAvjare compute(Avi) (Avj) = (Avi)T(Avj) =vTiATAvj=vTi 2jvj= 2j(vi vj).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. 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.}

6 ,vn}is an orthonormalbasis forRn, thenv1vT1+ +vnvTn=I(exercise).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).Step find a matrixVthat we can use, we need to solve for anorthonormal basis of eigenvectors ofATA. One possibility isv1= 1/32/32/3 , v2= 2/3 1/32/3 , v3= 2/3 2/31/3 .(There are seven other possibilities in which some of the above vectors aremultiplied by 1.) ThenVis the matrix withv1,v2,v3as columns, that isV= 1/3 2/32/32/3 1/3 2/32/32/31/3.

7 5 Step now find the matrixU. The first column ofUis 11Av1=16 10(186)=(3/ 101/ 10).The second column ofUis 12Av2=13 10(39)=(1/ 10 3/ 10).SinceUis a 2 2 matrix, we do not need any more columns. (IfAhad onlyone nonzero Singular value, then we would need to add another column toUto make it an orthogonal matrix.) ThusU=(3/ 101/ 101/ 10 3/ 10).To conclude, we have found the Singular value decomposition(4 11 1487 2)=(3/ 101/ 101/ 10 3/ 10)(6 100003 10 0) 1/3 2/32/32/3 1/3 2/32/32/31/3 ApplicationsSingular values and Singular value decompositions are important in analyz-ing simple example of this is rank estimation . Suppose that we havendata pointsv1,..,vn, all of which live inRm, wherenis much largerthanm. LetAbe them nmatrix with columnsv1,..,vn. Suppose thedata points satisfy some linear relations, so thatv1,..,vnall lie in anr-dimensional subspace ofRm. Then we would expect the matrixAto haverankr. However if the data points are obtained from measurements witherrors, then the matrixAwill probably have full rankm.

8 But onlyrof thesingular values ofAwill be large, and the other Singular values will be closeto zero. Thus one can compute an approximate rank ofAby countingthe number of Singular values which are much larger than the others, andone expects the measured matrixAto be close to a matrixA such that therank ofA is the approximate rank example, consider the matrixA = 12 23 40123 21 5 6 The matrixA has rank 2, because all of its columns are points in thesubspacex1+x2+x3= 0 (but the columns do not all lie in a 1-dimensionalsubspace). Now suppose we perturbA to the matrixA= This matrix now has rank 3. But the eigenvalues ofATAare 21 , 22 , 23 , 24= two of the Singular values are much larger than the others, this suggeststhatAis close to a rank 2 more discussion of how SVD is used to analyze data, see Lay Exercises (some from Lay s book)1. (a) Find a Singular value decomposition of the matrixA=(2 122).(b) Find a unit vectorxfor which Ax is Find a Singular value decomposition ofA=(3 222 3 2).

9 3. (a) Show that ifAis ann nsymmetric matrix, then the singularvalues ofAare the absolute values of the eigenvalues ofA.(b) Give an example to show that ifAis a 2 2 matrix which isnot symmetric, then the Singular values ofAmight not equal theabsolute values of the eigenvalues LetAbe anm nmatrix with Singular values 1 2 n an eigenvector ofATAwith eigenvalue 21. Show that 2isthe maximum value of Ax wherexranges over unit vectors inRnthat are orthogonal Show that if{v1,..,vn}is an orthonormal basis forRn, thenv1vT1+ +vnvTn= LetAbe anm nmatrix, and letPbe an orthogonalm thatPAhas the same Singular values