In class we used the Courant-Fischer theorem to prove that the best low-rank approximation to any...

 

Transcribed Image Text:

In class we used the Courant-Fischer theorem to prove that the best low-rank approximation to any matrix X Rnxd is given by XVV where Vk Rdxk contains the top k eigenvectors of XX (i.e., the top k singular vectors of X). Here you will prove this from scratch, using just the basic properties of projection matrices and eigenvectors. 1. (2 points) Let X E Rnxd be any matrix and B Rnxd be any rank-k matrix with SVD B = WSZT for orthonormal W Rnk, Z Rdxk, and diagonal S Rkxk. Prove that ||X - B|| = ||XZZ B||/ + ||X XZZT||2. Hint: Use the Pythagorean theorem. 2. (2 points) Use part (1) to show that if B = || ||X-M|| then we have XZZ = B. arg min M:rank (M)=k 3. (2 points) Using a similar argument as above, one can show that if B is an optimal rank-k approximation of X then WWTX = B. Use this and part (2) to show that: XZ = WS and WTX = SZT. 4. (2 points) Use part (3) to show that if B is an optimal rank-k approximation of X then XXZ = ZS and use this to argue that each column of Z is an eigenvector of XTX. 5. (2 points) Complete the proof, showing that the best low-rank approximation of X is given ows by XVV where V contains the top k eigenvectors of XTX. Go to Settings to activate In class we used the Courant-Fischer theorem to prove that the best low-rank approximation to any matrix X Rnxd is given by XVV where Vk Rdxk contains the top k eigenvectors of XX (i.e., the top k singular vectors of X). Here you will prove this from scratch, using just the basic properties of projection matrices and eigenvectors. 1. (2 points) Let X E Rnxd be any matrix and B Rnxd be any rank-k matrix with SVD B = WSZT for orthonormal W Rnk, Z Rdxk, and diagonal S Rkxk. Prove that ||X - B|| = ||XZZ B||/ + ||X XZZT||2. Hint: Use the Pythagorean theorem. 2. (2 points) Use part (1) to show that if B = || ||X-M|| then we have XZZ = B. arg min M:rank (M)=k 3. (2 points) Using a similar argument as above, one can show that if B is an optimal rank-k approximation of X then WWTX = B. Use this and part (2) to show that: XZ = WS and WTX = SZT. 4. (2 points) Use part (3) to show that if B is an optimal rank-k approximation of X then XXZ = ZS and use this to argue that each column of Z is an eigenvector of XTX. 5. (2 points) Complete the proof, showing that the best low-rank approximation of X is given ows by XVV where V contains the top k eigenvectors of XTX. Go to Settings to activate