1. Let A be an m d matrix, and let X = AAT . Assume that X has d distinct, non-zero eigenvalues. Assume that m d. In order to find the eigendecomposition of X, we will need to find the eigendecomposition of an m m matrix. Since m is much larger than d, this is slow. Give an algorithm for finding the eigenvectors and eigenvalues of X that only requires computing the eigendecomposition of a d d matrix. You can use simple matrix operations and assume that you have an eigendecomposition black box subroutine, but avoid using the SVD as a black box.
