The Decomposition Theorems - Lecture Note

5 The Decomposition Theorems 5.1 The Eigenvector/Eigenvalue Decomposition 1. Definition: Let A be an n × n matrix. Then an eigenvector-eigenvalue pair is v 6= 0, λ where Av = λv ⇒ (A − λI)v = 0 (4) 2. Remark: If Equation (4) has a nontrivial solution, then det (A − λI) = 0 which leads to solving for the roots of a polynomial of degree n. This polynomial is called the characteristic polynomial. 3. Remark: We solve for the eigenvalues first, then solve for the nullspace of (A − λi I) by solving (A − λi I)x = 0 4. Remark: Note that it is possible that one eigenvalue is repeated. This may or may not correspond with the same number of eigenvectors. 5. Definition: If eigenvalue λ is repeated k times, then the algebraic multiplicity of λ is k. 6. Definition: If eigenvalue λ has k associated independent eigenvectors, λ has geometric multiplicity k. 7. Example: Compute the eigenvalues and eigenvectors for: (i) the 2 × 2 identity matrix, (ii) The matrix (in Matlab notation): [1 2;0 1] 8. Theorem: If aλ is the algebraic multiplicity of λ and gλ is the geometric multiplicity, then aλ ≥ gλ We won’t prove this here. 9. Definition: If, for some eigenvalue λ of A, we have that aλ > gλ , A is said to be defective. 10. Definition: The set of independent eigenvectors associated with an eigenvector λ, together with 0 forms a vector space. This space is called the eigenspace, and is denoted by Eλ . 11. Theorem: If X is square and invertible, then A and X −1 AX have the same eigenvalues. 12. Exercise: Prove the previous theorem. 11 13. Remark: One method of characterizing eigenvalues in terms of the determinant and trace of a matrix: det(A) = Πni=1 λi trace(A) = ∞ X λi i=1 14. Remark: We will be especially interested in symmetric matrices. The rest of this section is devoted to them. 15. Definition: A matrix A is orthogonally diagonalizeable if there is an orthogonal matrix Q and diagonal matrix D so that so that A = QDQT . 16. The Spectral Theorem: If A is an n × n symmetric matrix, then: (a) A has n real eigenvalues (counting multiplicity). (b) For all λ, aλ = gλ . (c) The eigenspaces are mutually orthogonal. (d) A is orthogonally diagonalizeable, with D = diag(λ1 , λ2 , . . . , λn ). Some remarks about the Spectral Theorem: • We assume that inside each eigenspace, we have an orthonormal basis of eigenvectors. This is not a restriction, since we can always construct such a basis using Gram-Schmidt. • If a matrix is real and symmetric, the Spectral Theorem says that its eigenvectors form an orthonormal basis for IRn . • The first part is somewhat difficult to prove in that we would have to bring in more machinery than we would like. If you would like to see a proof, it comes from the Schur Decomposition, which is given, for example, in “Matrix Computations” by Golub and Van Loan. 17. The following is a proof of part (c). Supply justification for each step: Let v 1 , v 2 be eigenvectors from distinct eigenvalues, λ1 , λ2 . We show that v 1 · v 2 = 0: λ1 v 1 · v 2 = (Av 1 )T v 2 = v T1 AT v 2 = v T1 Av 2 = λ2 v 1 · v 2 Now, (λ1 − λ2 )v 1 · v 2 = 0. 18. The Spectral Decomposition: Since A is orthogonally diagonalizable, then  T   q1 λ1 0 . . . 0  0 λ2 . . . 0   q T2     A = (q 1 q 2 . . . q n )  . .. . . ..   ..     .. . . . .  0 12 0 ... λn q Tn so that:    A = (λ1 q 1 λ2 q 2 . . . λn q n )   q T1 q T2 .. . q Tn      so finally: A = λ1 q 1 q T1 + λ2 q 2 q T2 + . . . + λn q n q Tn That is, A is a sum of n rank one matrices, each of which is a projection matrix. 19. Matlab Exercise: Verify the spectral decomposition for a symmetric matrix. Type the following into Matlab (the lines that begin with a % denote comments that do not have to be typed in). %Construct a random, symmetric, 6 x 6 matrix: for i=1:6 for j=1:i A(i,j)=rand; A(j,i)=A(i,j); end end %Compute the eigenvalues of A: [Q,L]=eig(A); %NOTE: A = Q L Q’ %L is a diagonal matrix %Now form the spectral sum S=zeros(6,6); for i=1:6 S=S+L(i,i)*Q(:,i)*Q(:,i)’; end max(max(S-A)) Note that the maximum of S − A should be a very small number! (By the spectral decomposition theorem). 5.2 The Singular Value Decomposition There is a special matrix factorization that is extremely useful, both in applications and in proving theorems. This is mainly due to two facts, which we shall investigate in this section: (1) We can use this factorization on any matrix, (2) The factorization defines explicitly the rank of the matrix, and all four matrix subspaces. In what follows, assume that A is an m × n matrix (so A maps IRn to IRm ). 13 1. Remark: Although A itself is not symmetric, AT A is n × n and symn metric. Therefore, it is orthogonally diagonalizable. Let {λi }i=1 and V = [v 1 , v 2 , . . . , v n ] be the eigenvalues and orthonormal eigenvectors. 2. Exercise: Show that λi ≥ 0 for i = 1..n by showing that kAv i k22 = λi . 3. Definition: We define the singular values of A by: p σ i = λi where λi is an eigenvalue of AT A. 4. Remark: In the rest of the section, we will assume any list (or diagonal matrix) of eigenvalues of AT A (or singular values of A) will be ordered from highest to lowest: λ1 ≥ λ2 ≥ . . . ≥ λn . 5. Exercise: Prove that, if v i and v j are distinct eigenvectors of AT A, then their corresponding images, Av i and Av j , are orthogonal. 6. Exercise: Prove that, if x = α1 v 1 + . . . αn v n , then kAxk2 = α12 λ1 + . . . + αn2 λn n 7. Exercise: Let W be the subspace generated by the basis {v j }j=k+1 , where v j are the eigenvectors associated with the zero eigenvalues of AT A (therefore, we are assuming that the first k eigenvalues are NOT zero). Show that W = Null(A). 8. Exercise: Prove that if the rank of AT A is r, then so is the rank of A. 9. Remark: Define ui = 1 1 Av i = Av i kAv i k2 σi and let U be the matrix whose ith column is ui . 10. Remark: This definition only makes sense sense for the first r vectors v (otherwise, Av i = 0). Thus, we’ll have to extend the basis to span all of IRm . 11. Exercise: Sketch how you might do this. 12. Exercise: Show that ui is an eigenvector of AAT whose eigenvalue is also λi . 13. Exercise: Show that AT ui = σi v i 14. Remark: So far, we have shown how to construct two matrices, U and V given a matrix A. That is, the matrix V is constructed by the eigenvectors of AT A, and the matrix U can be constructed using the v’s or by finding the eigenvectors of AAT . 14 15. Exercise: Let A be m × n. Define the m × n matrix Σ = diag(σ1 , . . . , σn ) where σi is the ith singular value of the matrix A. Show that AV = U Σ 16. The Singular Value Decomposition (SVD) Let A be any m × n matrix of rank r. Then A = U ΣV T where U, Σ, V are the matrices defined in the previous exercises. That is, U is an orthogonal m × m matrix, Σ is a diagonal m × n matrix, and V is an orthogonal n × n matrix. The u’s are called the left singular vectors and the v’s are called the right singular vectors. 17. Remark: Keep in mind the following relationship between the right and left singular vectors: Av i = σ i ui T = σi v i A ui 18. Computing The Four Subspaces to a matrix A. Let A = U ΣV T be the SVD of A which has rank r. Be sure that the singular values are ordered from highest to lowest. Then: r (a) A basis for the columnspace of A, R(A) is {ui }i=1 n (b) A basis for nullspace of A, N (A) is {v i }i=r+1 r (c) A basis for the rowspace of A, R(AT ) is {v i }i=1 m (d) A basis for the nullspace of AT , N (AT ) is {ui }i=r+1 19. We can also visualize the right and left singular values as in Figure 2. We think of the v i as a special orthogonal basis in Rn (Domain) that maps to the ellipse whose axes are defined by σi ui . 20. The SVD is one of the premier tools of linear algebra, because it allows us to completely reveal everything we need to know about a matrix mapping: The rank, the basis of the nullspace, a basis for the column space, the basis for the nullspace of AT , and of the row space. This is depicted in Figure 3. 21. Lastly, the SVD provides a decomposition of any linear mapping into two “rotations” and a scaling. This will become important later when we try to deduce a mapping matrix from data (See the section on signal separation). 15 Figure 2: The geometric meaning of the right and left singular vectors of the SVD decomposition. Note that Av i = σi ui . The mapping x → Ax will map the unit circle on the left to the ellipse on the right. Col(AT ) v1 u1 v2 .. . vk u2 .. . ⇐⇒ Col(A) uk =⇒ N(A) 0 vk+1 .. . vn 0 ⇐= IRn uk+1 .. . N(AT ) um IRm Figure 3: The SVD of A ([U,S,V]=svd(A)) completely and explicitly describes the 4 fundamental subspaces associated with the matrix, as shown. We have a one to one correspondence between the rowspace and columnspace of A, the remaining v’s map to zero, and the remaining u’s map to zero (under AT ). 16 22. Exercise: Compute the SVD by hand of the following matrices:     0 2 1 1  0 0  0 0 0 0 23. Remark: If m or n is very large, it might not make sense to keep the full matrix U and V . 24. The Reduced SVD Let A be m × n with rank r. Then we can write: A = Ũ Σ̃V˜T where Ũ is an m × r matrix with orthogonal columns, Σ̃ is an r × r square matrix, and Ṽ is an n × r matrix. 25. Theorem: (Actually, this is just another way to express the SVD). Let A = U ΣV T be the SVD of A, which has rank r. Then: A= r X σi ui v Ti i=1 Therefore, we can approximate A by the sum of rank one matrices. 26. Matlab and the SVD Matlab has the SVD built in. The function specifications are: [U,S,V]=svd(A) and [U,S,V]=svd(A,0) where the first function call returns the full SVD, and the second call returns a reduced SVD- see Matlab’s help file for the details on the second call. 27. Matlab Exercise: Image Processing and the SVD. First, in Matlab, load the clown picture: load clown This loads a matrix X and a colormap, map, into the workspace. To see the clown, type: image(X); colormap(map) We now perform a Singular Value Decomposition on the clown. Type in: [U,S,V]=svd(X); How many vectors are needed to retain a good picture of the clown? Try performing a k−dimensional reconstruction of the image by typing: H=U(:,1:k)*S(1:k,1:k)*V(:,1:k)’; image(H) for k = 5, 10, 20 and 30. What do you see? 17 5.2.1 Generalized Inverses Let a matrix A be m × n with rank r. In the general case, A does not have an inverse. Is there a way of restricting the domain and range of the mapping y = Ax so that the map is invertible? We know that the columnspace and rowspace of A have the same dimensions. Therefore, there exists a 1-1 and onto map between these spaces, and this is our restriction. To “solve” y = Ax, we replace y by its orthogonal projection to the columnspace of A, ŷ. This gives the least squares solution, which makes the problem solvable. To get a unique solution, we replace x by its projection to the rowspace of A, x̂. The problem ŷ = Ax̂ now has a solution, and that solution is unique. We can rewrite this problem now in terms of the reduced SVD of A: x̂ = V V T x, ŷ = U U T y Now we can write: U U T y = U ΣV T V V T x so that
V Σ−1 U T y = V V T x (Exercise: Verify that these computations are correct!) Given an m × n matrix A, define its pseudoinverse, A† by: A† = V Σ−1 U T We have shown that the least squares solution to y = Ax is given by: x̂ = A† y where x̂ is in the rowspace of A, and its image, Ax̂ is the projection of y into the columnspace of A. Geometrically, we can understand these computations in terms of the four fundamental subspaces. T 6R(A ) Ax = y - 6R(A) qy - N (A) IRn - N (AT ) IRm 18 In this case, there is no value of x ∈ IRn which will map onto y, since y is outside the columnspace of A. To get a solution, we project y onto the columnspace of A as shown below: T 6R(A ) 6R(A) ŷ = U U T y qy - N (A) - N (AT ) Now it is possible to find an x that will map onto ŷ, but if the nullspace of A is nontrivial, then all of the points on the dotted line will also map to ŷ T 6R(A ) x̂ = V V T xr 6R(A) rx ŷ - N (A) qy - N (AT ) Finally, we must choose a unique value of x for the mapping- We choose the x inside the rowspace of A. This is a very useful idea, and it is one we will explore in more detail later. For now, notice that to get this solution, we analyzed our four fundamental subspaces in terms of the basis vectors given by the SVD. Exercises 1. Consider  2 1 3 1 −1 2     x1  x2  = 5 1 x3  (a) Before solving this problem, what are the dimensions of the four fundamental subspaces? (b) Use Matlab to compute the SVD of the matrix A, and solve the problem by computing the pseudoinverse of A directly. 19 (c) Check your answer explicitly and verify that x̂ and ŷ are in the rowspace and columnspace. (Hint: If a vector x is already in the rowspace, what is V V T x?) 2. Consider        2 1 −1 3  x1 −1 0 1 −2    x2  7 2 −5 12    x3  −3 −2 0 −4 x4 4 1 −3 7      =    5 1 0 −2 6       (a) Find the dimensions of the four fundamental subspaces by using the SVD of A (in Matlab). (b) Solve the problem. (c) Check your answer explicitly and verify that x̂ and ŷ are in the rowspace and columnspace. 3. Write the following in Matlab to reproduce Figure 2: theta=linspace(0,2*pi,30); z=exp(i*theta); X=[real(z);imag(z)]; %The domain points m=1/sqrt(2); A=(m*[1,1;1,-1])*[1,0;0,3]; Y=A*X; %The image of the circle t=linspace(0,1); vec1=[0;0]*(1-t)+[0;1]*t; vec2=[0;0]*(1-t)+[1;0]*t; %The basis vectors v Avec1=A*vec1; Avec2=A*vec2; %Image of the basis vectors figure(1) %The domain plot(X(1,:),X(2,:),’k’,vec1(1,:),vec1(2,:),’k’, vec2(1,:),vec2(2,:),’k’); axis equal figure(2) %The image plot(Y(1,:),Y(2,:),’k’,Avec1(1,:),Avec1(2,:),’k’, Avec2(1,:),Avec2(2,:),’k’); axis equal 4. In the previous example, what was the matrix A? The vectors v? The vectors u? The singular values σ1 , σ2 ? Once you’ve written these down from the program, perform the SVD of A in Matlab. Are the vectors the same that you wrote down? NOTE: These show that the singular vectors are not unique- they vary by ±v, or ±u. 20 6 Interactions Between Subspaces and the SVD Suppose that a matrix A is p×n and B is q ×n. Then we have four fundamental subspaces for each of A, B. In particular, the row spaces and null spaces of A and B are all in IRn . Note that this interpretation is looking at the matrix A as containing p sample data points from IRn , and the matrix B as containing q sample data points from IRn . It is natural to ask about the interaction of these subspaces of IRn , which are enumerated below: • The rowspace of A separate from B. This is also the intersection of the rowspace of A with the nullspace of B. • The rowspace of B separate from A. This is also the intersection of the rowspace of B with the nullspace of A. • The intersection of the rowspaces of A and B. • The intersection of the nullspaces of A and B. How can we obtain a basis for the intersection of nullspaces? This is in fact fairly easy as long as p, q are relatively small. We construct a new matrix Z that is p + q × n:   A Z= B and find the nullspace of this via the SVD of Z. Exercise: Prove that, if v ∈ IRn , and Zv = 0, then v ∈ Null(A) ∩ Null(B). Exercise: Prove directly that, if v ∈ IRn , and Zv 6= 0, then v ∈ Row(A) ∪ Row(B). Note that the first exercise proves the second in that: c (Null(A) ∩ Null(B)) = Null(A)c ∪ Null(B)c = Row(A) ∪ Row(B) where c is the complement of the set. We can find bases for the Row(A) and Row(B) directly- Let us define the two reduced SVDs: A = UA ΣA VAT , B = UB ΣB VBT Then the columns of VA , VB form a basis for the rowspace of A and the rowspace of B respectively. Before continuing further in the discussion, lets consider the idea of distance and angles between two subspaces. 21 6.1 Angles Between Subspaces As in Golub and Van Loan, let F, G be two subspaces of IRm . Without loss of generality, assume: p = dim(F ) ≥ dim(G) = q ≥ 1   The principal angles θ1 , . . . , θq ∈ 0, π2 between F and G are defined recursively by: cos(θk ) = max max uT v = uTk vk u∈F v∈G subject to the additional constraints that u, v be unit length and they are orthogonal to the previously found vectors u1 , . . . , uk−1 and v1 , . . . vk−1 . The vectors u1 , . . . uq and v1 , . . . , vq are called the principal vectors between subspaces F and G. Some remarks about this definition: • Since u, v are normalized, the maximum value of uT v is 1, corresponding to θ = 0. Thus, principal vectors associated with this value of θ are the same. These vectors will also give the an orthonormal basis for the intersection of F, G. • Since θ is restricted, the smallest value of uT v is zero, corresponding to θ = π/2. The corresponding vectors of F and G will be orthogonal. • We can define the distance between subspaces F and G if p = q by using the largest principal angle, θp : q dist(F, G) = 1 − cos2 (θp ) = sin(θp ) For example, if F and G are the same subspace, then θk = 0 for k = 1, . . . , p, and the distance between them is 0. On the other extreme, if F and G are orthogonal, then θk = π/2 for k = 1, . . . , p and the distance between them is 1. 6.2 Computing the principal angles and vectors. Here we give an intuitive idea behind the algorithm; for a more details see Golub and Van Loan (Chapter 12). Given two sets of orthonormal basis vectors for subspaces F and G (we’ll use VA and VB found earlier), we can write: uT v = y T VAT VB z so that u = VA y and v = VB z. Thus, if U, V are the matrices whose columns are the principal vectors, then U T V = Y T (VAT VB )Z = diag(cos(θ1 ), . . . , cos(θq )) = D 22 Notice that this is the SVD of VAT VB : VAT VB = Y DZ T Note again that we have not proven anything- this was just an observation. For a proof, we would need additional facts about the SVD of a matrix that would take us too far afield. Example: Let F, G be subspaces of IR3 , where F is the x − y plane and G is the x − z plane. Clearly, there is a one-dimensional intersection. We show this using the computations in the previous discussion.         0  0   1  1 F = span  0  ,  1  , G = span  0  ,  0      0 0 0 1 We can use these basis vectors as VA , VB respectively. Now,      1 0  1 0 1 0 0 T   0 0 = V A VB = 0 0 0 1 0 0 1 Since this matrix is already in diagonal form,     cos(θ1 ) 0 1 0 IT =I 0 cos(θ2 ) 0 0 so that Y = Z = I and U = V A I = VA , V = VB I = VB Therefore, u1 = v1 corresponding to the subspace intersection, and the distance between the subspaces is 1. We also see that there is no nontrivial intersection between the nullspaces of F, G. We would see this if we took the SVD of [VAT VBT ]T as suggested at the beginning of this section, since there would be no zero singular values. Similarly, we can find the intersection of F with G⊥ . In this case,      0  0 1 0 0   1 = = Y · 1 · 1 = Y · 1 · ZT VAT VB = 1 0 1 0 0 Since this “matrix” is already in diagonal form,     0 0 V = VB · 1 =  1  U = VA Y =  1  , 0 0 23