Singular Value Decomposition

Singular value decomposition The singular value decomposition of a matrix is usually referred to as the SVD. This is the final and best factorization of a matrix: A = UΣV T where U is orthogonal, Σ is diagonal, and V is orthogonal. In the decomoposition A = UΣV T , A can be any matrix. We know that if A is symmetric positive definite its eigenvectors are orthogonal and we can write A = QΛQ T . This is a special case of a SVD, with U = V = Q. For more general A, the SVD requires two different matrices U and V. We’ve also learned how to write A = SΛS−1 , where S is the matrix of n distinct eigenvectors of A. However, S may not be orthogonal; the matrices U and V in the SVD will be. How it works We can think of A as a linear transformation taking a vector v1 in its row space to a vector u1 = Av1 in its column space. The SVD arises from finding an orthogonal basis for the row space that gets transformed into an orthogonal basis for the column space: Avi = σi ui . It’s not hard to find an orthogonal basis for the row space – the GramSchmidt process gives us one right away. But in general, there’s no reason to expect A to transform that basis to another orthogonal basis. You may be wondering about the vectors in the nullspaces of A and A T . These are no problem – zeros on the diagonal of Σ will take care of them. Matrix language The heart of the problem is to find an orthonormal basis v1 , v2 , ...vr for the row space of A for which � � � � A v1 v2 · · · vr = σ1 u1 σ2 u2 · · · σr ur ⎡ ⎤ σ1 ⎥ σ2 � �⎢ ⎢ ⎥ = u1 u2 · · · ur ⎢ ⎥, . .. ⎣ ⎦ σr with u1 , u2 , ...ur an orthonormal basis for the column space of A. Once we add in the nullspaces, this equation will become AV = UΣ. (We can complete the orthonormal bases v1 , ...vr and u1 , ...ur to orthonormal bases for the entire space any way we want. Since vr+1 , ...vn will be in the nullspace of A, the diagonal entries σr+1 , ...σn will be 0.) The columns of U and V are bases for the row and column spaces, respec­ tively. Usually U �= V, but if A is positive definite we can use the same basis for its row and column space! Calculation � Suppose A is the invertible matrix 4 −3 4 3 � . We want to find vectors v1 and v2 in the row space R2 , u1 and u2 in the column space R2 , and positive numbers σ1 and σ2 so that the vi are orthonormal, the ui are orthonormal, and the σi are the scaling factors for which Avi = σi ui . This is a big step toward finding orthonormal matrices V and U and a di­ agonal matrix Σ for which: AV = UΣ. Since V is orthogonal, we can multiply both sides by V −1 = V T to get: A = UΣV T . Rather than solving for U, V and Σ simultaneously, we multiply both sides by A T = VΣ T U T to get: A T A = VΣU −1 UΣV T = VΣ2 V T ⎡ 2 σ1 ⎢ σ22 ⎢ =V⎢ ⎣ ⎤ .. . σn2 ⎥ ⎥ T ⎥V . ⎦ This is in the form QΛQ T ; we can now find V by diagonalizing the symmetric positive definite (or semidefinite) matrix A T A. The columns of V are eigenvec­ tors of A T A and the eigenvalues of A T A are the values σi2 . (We choose σi to be the positive square root of λi .) To find U, we do the same thing with AA T . SVD example � We return to our matrix A = T 4 −3 � . We start by computing � 4 4 � 25 7 7 25 A A= = 4 3 −3 3 �� 4 4 −3 3 � � . The eigenvectors of this matrix will give us the vectors vi , and the eigenvalues will gives us the numbers σi . � � � � 1 1 Two orthogonal eigenvectors of A T A are and . To get an or­ 1 −1 √ � � � √ � 1/√2 1/√2 thonormal basis, let v1 = and v2 = . These have eigen­ 1/ 2 −1/ 2 values σ12 = 32 and σ22 = 18. We now have: � A � 4 4 −3 3 U � � � = T √ Σ √ V √ � � � 4 2 1/√2 1/√2 √0 . 0 3 2 1/ 2 −1/ 2 We could solve this for U, but for practice we’ll find U by finding orthonor­ mal eigenvectors u1 and u2 for AA T = UΣ2 U T . � �� � 4 4 4 −3 T AA = −3 3 4 3 � � 32 0 = . 0 18 � � 1 Luckily, AA T happens to be diagonal. It’s tempting to let u1 = and u2 = 0 � � � � 0 0 √ , as Professor Strang did in the lecture, but because Av2 = we 1 −3 2 � � � � 0 1 0 instead have u2 = and U = . Note that this also gives us a −1 0 −1 chance to double check our calculation of σ1 and σ2 . Thus, the SVD of A is: � A � 4 4 −3 3 U � = 1 0 0 −1 � � T √ Σ √ V √ � � � 4 2 1/√2 1/√2 √0 . 0 3 2 1/ 2 −1/ 2 Example with a nullspace � Now let A = 4 8 3 6 � . This has a one dimensional nullspace and one dimen­ sional row and column spaces. � 4 3 � The row space of A consists of the multiples of . The column space � � 4 of A is made up of multiples of . The nullspace and left nullspace are 8 perpendicular to the row and column spaces, respectively. � � Unit basis vectors of the row and column spaces are v1 = .8 .6 and u1 = � √ � 1/√5 . To compute σ1 we find the nonzero eigenvalue of A T A. 2/ 5 AT A = = � 4 3 � 80 60 8 6 �� 60 45 4 8 3 6 � � . Because this is a rank 1 matrix, one eigenvalue must be 0. The other must equal the trace, so σ12 = 125. After finding unit vectors perpendicular to u1 and v1 (basis vectors for the left nullspace and nullspace, respectively) we see that the SVD of A is: � � � � � √ � � � 4 3 1 2 .8 .6 125 0 = √1 . 5 2 −1 .6 −.8 8 6 0 0 A U Σ VT The singular value decomposition combines topics in linear algebra rang­ ing from positive definite matrices to the four fundamental subspaces. v1 , v2 , ...vr u1 , u2 , ...ur vr+1 , ...vn ur+1 , ...um is an orthonormal basis for the row space. is an orthonormal basis for the column space. is an orthonormal basis for the nullspace. is an orthonormal basis for the left nullspace. These are the “right” bases to use, because Avi = σi ui .