• No extension will be provided, unless for serious documented reasons.
• Start early!
• Study the material taught in class, and feel free to do so in small groups, but the solutions should be a product of your own work.
• This is not a multiple choice homework; reasoning, and mathematical proofs are required before giving your final answer.
1 [15 points]
Let A ∈ Rm×n be a real m × n matrix.
1. (5pts) Prove that the eigenvalues of AAT and ATA are real and non-negative.
2. (5pts) Prove that the two matrices have the same set of non-negative eigenvalues.
3. (5pts) How does this set of eigenvalues relates to the set of singular values? What about the left, right singular vectors with respect to the eigenvectors of the matrices
AAT and ATA?
2 [20 points]
1. (5 pts) Let An×n be a real square matrix. Suppose the rows of A are orthonormal. Prove that the columns have to be orthonormal. Is this statement true when the matrix is not square?
2. (5 pts) Prove that a linear system Ax = b is consistent if and only if rank(A) = rank([A|b]). Comment on the geometric interpretation of equation rank(A) = rank([A|b]).
3. (5 pts + 5 pts) What is the SVD of the matrix M = [0,1,2]1×3? Compute it in two ways:
(a) Using exercise 1.3.
(b) By “eyeballing” M.
Hint: Understand the subspaces spanned by the columns and rows in order to decide the left and singular vectors.
1 of 2
CS365 Spring ’23
Foundations of Data Science
Prof. C.E. Tsourakakis Assignment 8
3 SVD for least squares [20 points]
Suppose you are given a system of linear equations Am×nxn×1 = bm×1 where the number of rows m is greater than the number of columns n (overdetermined system of linear equations). Given that the number of equations m is greater than the number of unknowns maybe there is no x that satisfies the linear system. Thus it is natural to try to find an x that minimizes the error ||Ax − b|| .
1. (10 pts) Assume that A is full rank, i.e., rank(A) = n < m. Prove that the unique minimizer x⋆ = (ATA)−1ATb. Be explicit about where you use the assumption that A is full rank and the objective value ||Ax⋆ − b||2.
2. (10 pts) Solve the same optimization problem when A is rank deficient.
Hint: Use the SVD decomposition
4 Coding [30 points]
Check the Jupyter notebook on our Git repo.
