SVD Handout - Homework Solutions

SVD Handout - Homework Solutions 1. Exercises 1, 2 p. 481: Find the singular values of the matrices below:     1 0 −5 0 0 −3 0 0 √ SOLUTION: Recall that the singular values are σi = λi , where the λ0 s are the eigenvalues of either AAT or AT A (remember that the non-zero eigenvalues are the same for both). In each case, the matrix is symmetric meaning that AT A = A2 = AAT :   1 0 T 2 A A=A = ⇒ σ1 = 3, σ2 = 1 0 9 (They should be in order from largest to smallest)   √ 5 0 T 2 A A=A = ⇒ σ1 = 5, σ2 = 0 0 0 2. Exercises 7, 9 p. 481: Construct the SVD of each matrix below (by hand):     7 1 2 −1  0 0  2 2 5 5 Side note: As a disclaimer, these are textbook problems. I would have made the numbers work out more nicely for problems we do by hand... SOLUTIONS: As an outline, we compute either AT A or AAT to start, then compute the eigenvalues and eigenvectors. From there, we can also compute the eigenvectors to the other matrix product. In these examples, I’ll compute the expansion for AT A first, but this is not necessary. • For the first matrix,  T A A= 8 2 2 5  λ2 − 13λ + 36 = 0 λ = 4, 9 For λ = 4, we have T  4 2 2 1 (A A − 4I) =   ⇒ v= −1 2  Similarly, for λ = 9, we have T (A A − 9I) =  −1 2 2 −4 1   ⇒ v= 2 1  Also, we can construct u = Av:      2 −1 −1 −4 u= = , 2 2 2 2  u= 2 −1 2 2  2 1   = 3 6  These vectors haven’t been scaled appropriately yet- Now we put it all together:       1 1 2 −1 1 −2 3 0 U=√ Σ= V =√ 2 1 0 2 5 1 5 2 • For the second matrix,   74 32 T A A= 32 26 λ2 − 100λ + 900 = 0 λ = 10, 90 For λ = 10, we have T  (A A − 10I) = 64 32 32 16   ⇒ v= −1 2  Similarly, for λ = 90, we have T  (A A − 90I) = −16 32 32 −64   ⇒ (It was a coincidence that this matrix V is the same we can construct u = Av:       7 1  −5 7 −1      0 , u= 0 0 = u= 0 2 5 5 5 5 v= 2 1  as the previous one!) Also,    1   15 2 0  = 0  1 5 15 In this problem, for the full SVD, we’ll also need the eigenspace λ = 0:      50 0 40 1 0 0 AAT =  0 0 0  ⇒  0 0 1  ⇒ u =  40 0 50 0 0 0 for AAT , where  0 1  0 (Looking back, we could have guessed this!) These vectors haven’t been scaled appropriately yet- Now we put it all together. Remember that Σ has the same size as A, so it is 3 × 2, U is 3 × 3 and V is 2 × 2. √  √   √    90 √ 0 1/ 2 −1 2 0 1 2 −1  V =√ U =  √0 Σ= 0 10  √0 1 1 2 5 0 0 1 2 1/ 2 0 3. Suppose A = U ΣV T is the (full) SVD. 2 (a) Suppose A is square and invertible. Find the SVD of the inverse. SOLUTION: A−1 = V Σ−1 U T (b) If A is square, show that |det(A)| is the product of the singular values. SOLUTION: Take the determinant of the SVD product. Remember that in this case, all the matrices must be square for this to be defined. det(A) = det(U ΣV T ) = det(U )det(Σ−1 )det(V T ) Since U is an orthogonal matrix, then U U T = I. This makes the determinant easy: det(U T U ) = (det(U ))2 = 1 ⇒ det(U ) = ±1 Similarly, det(V ) = ±1. Finally, the determinant of Σ is the product of the diagonal elements (since Σ is a diagonal matrix). Therefore, det(A) = ±σ1 σ2 · · · σn so that the absolute value of the determinant is the product of the singular values. (c) If A itself is symmetric, show that U = V so that the SVD gives the eigenvalueeigenvector factorization: P DP T . This actually comes from the Spectral Theorem. 4. Let A, b be as defined below. Use the SVD to write b = b̂ + z, where b̂ ∈ Col(A) and z ∈ Null(A).     1 2 1  3   2  4   A= b=  1  3  1  1 −1 4 Also write in Matlab how you would check to see if b̂ is actually in the column space of A (using the output of the SVD). TYPO: Did you notice? z can’t be in the null(A), it has to be in the null(AT ) since b is in IR4 . SOLUTION: The idea is to use the orthonormal bases for the colum and null space of A that we get from the SVD. First, in Matlab, we’ll compute the SVD (and because the columns of A are linearly independent, the rank is 2): A=[1 2;3 4;1 1;1 -1]; b=[1;2;3;4]; [U,S,V]=svd(A); b_hat=U(:,1:2)*U(:,1:2)’*b; z=U(:,3:4)*U(:,3:4)’*b; %Test: b_hat+z 3 To check the projection, recall that the projecting the projection doesn’t change the vector. So you could see if B̂ is the same as U(:,1:2)*U(:,1:2)’*b_hat. 5. (Exercise 12, 6.5) Given the data below, and the model equation β0 + β1 ln(w) = p form a linear systems of equations to find the constants β0 , β1 , and find them by computing the pseudoinverse (using an appropriate SVD). w 48 61 81 113 131 p 91 98 103 110 112 SOLUTION: w=[48;61;81;113;131]; p=[91;98;103;110;112]; n=length(w); A=[ones(n,1) log(w)]; %log is ln on Matlab [U,S,V]=svd(A); invS=[1/S(1,1),0; 0, 1/S(2,2)]; pinvA=V(:,1:2)*invS*U(:,1:2)’; beta=pinvA*p 6. Consider the matrix A below. We have two algorithms that will produce a basis for the column space- Gram-Schmidt and the SVD. Use Matlab to get both, then compare and contast the two bases. Hint: What vector comes first? Can we compare one, two or three dimensional subspaces?   1 3 5  1 1 0   A=  1 1 2  1 3 3 SOLUTION: First, do the decompositions: A=[1 3 5; 1 1 0; 1 1 2; 1 3 3]; %Gram-Schmidt on the columns of A comes from QR: [Q,R]=qr(A); [U,S,V]=svd(A); %A has rank 3, so compare the three cols of Q with U To compare subspaces, consider using the RREF of the matrix [Q|U ]. If we do that, we get: 4 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0.8663 -0.4554 0.2055 -0.0000 -0.4082 -0.4082 0.8165 -0.0000 0.2879 0.7912 0.5396 0 0 0 0 1.0000 You might notice that Q is 4 × 4, where if we computed it manually, it would be 4 × 3You’ll also note that the fourth columns of Q and U are the same- The single column vector is in the null(AT ). Therefore, the first three coumns of Q and U form different bases for the column space of A, but we see that they are the same space. 7. (Using the matrix A from the previous problem) Here is some data in IR4 that we organize in an array   1 2 3 4 X= 1 −1 1 −1 Find the projection of this data into the space spanned by the first two columns of the matrix U from the SVD of A. It is OK to write only two significant digits if you’re copying the output by hand. SOLUTION: A bit of a typo, but this is recoverable if we consider this to be two vectors in IR4 (so the matrix is transposed). The projection onto the space spanned by the first two columns of U is given by the following, where X has been entered as a 4 × 2 matrix rather than as a 2 × 4 matrix as given. U(:,1:2)*U(:,1:2)’*X 8. We want to find a matrix P so that, given matrix A and vector y, then P y is the projection of y into the column space of A (orthogonal projection). We know that we could do this with the SVD, but using the normal equations and assuming that A is full rank, show that the matrix is: P = A(AT A)−1 AT (Hint: Start by writing Ax = b and get the normal equation. SOLUTION: Ax = b ⇒ AT Ax = AT b ⇒ x = (AT A)−1 AT b Now this is actually x̂, and we know that Ax̂ = b̂. Therefore, multiply both sides of your equation by A: b̂ = Ax̂ = A(AT A)−1 AT b = P b 9. Work through the movie example from the text- Be sure to run it in Matlab. 5