Chapter 7 TheSingularValueDecomposition(SVD)

1 Chapter 7 The Singular Value Decomposition (SVD) 1 The SVD produces orthonormal bases of v s and u s for the four fundamental Using those bases, A becomes a diagonal matrix and Avi= iui: i= singular The two-bases diagonalization A = U VToften has more information than A = X X U VTseparates A into rank-1 matrices 1u1vT1+ + rurvTr. 1u1vT1is the largest! Bases and Matrices in the SVDThe Singular Value Decomposition is a highlight of linear algebra. A is any m by n matrix,square or rectangular. Its rank is r. We will diagonalize this A, but not by X eigenvectors in X have three big problems: They are usually not orthogonal, thereare not always enough eigenvectors, and Ax = x requires A to be a square matrix.

2 Thesingular vectors of A solve all those problems in a perfect me describe what we want from the SVD : the right bases for the four I will write about the steps tofind those bases in order of price we pay is to have two sets of singular vectors, u s and v s. The u s are inRmand the v s are in Rn. They will be the columns of an m by m matrix U and an n byn matrix V . I willfirst describe the SVD in terms of those basis vectors. Then I can alsodescribe the SVD in terms of the orthogonal matrices U and V .(using vectors) The u s and v s give bases for the four fundamental subspaces :u1.

3 , uris an orthonormal basis for the column spaceur+1, .. , umis an orthonormal basis for the left nullspace N(AT)v1, .. , vris an orthonormal basis for the row spacevr+1, .. , vnis an orthonormal basis for the nullspace N(A).381382 Chapter 7. The Singular Value Decomposition (SVD)More than just orthogonality, these basis vectors diagonalize the matrix A : A is diagonalized Av1= 1u1Av2= 2u2..Avr= rur(1)Those singular values 1to rwill be positive numbers: iis the length of s go into a diagonal matrix that is otherwise zero. That matrix is .(using matrices) Since the u s are orthonormal, the matrix U with those r columns hasUTU = I.

4 Since the v s are orthonormal, the matrix V has VTV = I. Then the equationsAvi= iuitell us column by column that AVr= Ur r:(m by n)(n by r)AVr= Ur r(m by r)(r by r)A v1 vr = u1 ur 1 r . (2)This is the heart of the SVD, but there is more. Those v s and u s account for the rowspace and column space of A. We have n r more v s and m r more u s, from thenullspace N(A) and the left nullspace N(AT). They are automatically orthogonal to thefirst v s and u s (because the whole nullspaces are orthogonal). We now include all thev s and u s in V and U, so these matrices become square.

5 We still have AV = U .(m by n)(n by n)Av equals U (m by m)(m by n)A v1 vr vn = u1 ur um 1 r . (3)The new is m by n. It is just the r by r matrix in equation (2) with m r extra zerorows and n r new zero columns. The real change is in the shapes of U and V . Thoseare square orthogonal matrices. So AV = U can become A = U VT. This is theSingular Value Decomposition. I can multiply columns ui ifrom U by rows of VT:SVDA = U VT= u1 1vT1+ + ur rvTr.(4)Equation (2) was a reduced SVD with bases for the row space and column (3) is the full SVD with nullspaces included.

6 They both split up A into the samer matrices ui ivTiof rank one: column times will see that each 2iis an eigenvalue of ATA and also AAT. When we put thesingular values in descending order, 1 2 .. r> 0, the splitting in equation (4)gives the r rank-one pieces of A in order of importance. This is 1 When is = U VT(singular values) the same as X X 1(eigenvalues)?SolutionA needs orthonormal eigenvectors to allow X = U = V . A also needseigenvalues 0 if = . So A must be a positive semidefinite (or definite) symmetricmatrix. Only then will A = X X 1which is also Q QTcoincide with A = U Bases and Matrices in the SVD383 Example 2If A = xyT(rank 1) with unit vectors x and y, what is the SVD of A?

7 SolutionThe reduced SVD in (2) is exactly xyT, with rank r = 1. It has u1= x andv1= y and 1= 1. For the full SVD, complete u1= x to an orthonormal basisof u s, and complete v1= y to an orthonormal basis of v s. No new s, only 1= of the SVDWe need to show how those amazing u s and v s can be constructed. The v s will beorthonormal eigenvectors of ATA. This must be true because we are aiming forATA = (U VT)T(U VT) = V TUTU VT= V T VT.(5)On the right you see the eigenvector matrix V for the symmetric positive (semi) definitematrix ATA. And ( T ) must be the eigenvalue matrix of (ATA) : Each 2is (ATA) !

8 Now Avi= iuitells us the unit vectors u1to ur. This is the key equation (1).The essential point the whole reason that the SVD succeeds is that those unit vectorsu1to urare automatically orthogonal to each other (because the v s are orthogonal):Key stepuTiuj= Avi i T Avj j =vTiATAvj i j= 2j i jvTivj= zero. (6)The v s are eigenvectors of ATA (symmetric). They are orthogonal and now the u s arealso orthogonal. Actually those u s will be eigenvectors of we complete the v s and u s to n v s and m u s with any orthonormal basesfor the nullspaces N(A) and N(AT). We have found V and and U in A = U Example of the SVDHere is an example to show the computation of three matrices in A = U 3 Find the matrices U, , V for A = 3 04 5.

9 The rank is r = rank 2, this A has positive singular values 1and 2. We will see that 1is largerthan max= 5, and 2is smaller than min= 3. Begin with ATA and AAT:ATA = 25 2020 25 AAT= 9 1212 41 Those have the same trace (50) and the same eigenvalues 21= 45 and 22= 5. The squareroots are 1= 45 and 2= 5. Then 1 2= 15 and this is the determinant of key step is tofind the eigenvectors of ATA (with eigenvalues 45 and 5) : 25 2020 25 11 = 45 11 25 2020 25 11 = 5 11 Then v1and v2are those (orthogonal!) eigenvectors rescaled to length 7. The Singular Value Decomposition (SVD)Right singular vectors v1=1 2 11 v2=1 2 11.

10 Ui= left singular compute Av1and Av2which will be 1u1= 45 u1and 2u2= 5 u2:Av1=3 2 13 = 451 10 13 = 1u1Av2=1 2 31 = 51 10 31 = 2u2 The division by 10 makes u1and u2orthonormal. Then 1= 45 and 2= 5as expected. The Singular Value Decomposition is A = U VT:U =1 10 1 33 1 = 45 5 V =1 2 1 11 1 . (7)U and V contain orthonormal bases for the column space and the row space (both spacesare just R2). The real achievement is that those two bases diagonalize A : AV equals U .Then the matrix UTAV = is matrix A splits into a combination of two rank-one matrices, columns times rows : 1u1vT1+ 2u2vT2= 45 20 1 13 3 + 5 20 3 3 1 1 = 3 04 5 = Extreme MatrixHere is a larger example, when the u s and the v s are just columns of the identity the computations are easy, but keep your eye on the order of the columns.