## CSE P521: HW #5

Out: Saturday, Feb 18

Due: Saturday, Feb 25 at midnight (in the dropbox)

### Assignment

You should use the guidelines for HW#3, stated in slide 2 here. In particular, you may work with a partner on this homework.

#### Part I: Theory questions

1. See the proof of Theorem 2 (analysis of the power method) in these notes. Now suppose that the matrix $$A$$ has eigenvalues $$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$$, and that $$\lambda_1=\lambda_2=\cdots=\lambda_k$$, but $$\lambda_{k+1} < \lambda_k$$. Give a formal analysis of the power method in this setting, analogous to the statement of Theorem 2. Be careful to specify what replaces the vector $$\mathbf{v}_1$$. One cannot specify a single vector ahead of time. Make sure you explain why.

2. Suppose that $$A=X^T X$$ is an $$n\times n$$ symmetric matrix with real entries formed from an $$m \times n$$-dimensional matrix of data points $$X$$. Let $$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$$ denote the eigenvalues of $$A$$.

• Show that all the eigenvalues of $$A$$ are non-negative.

• In class, we argued that if we have an algorithm to find the top component $$\mathbf{v}_1$$ of $$A$$, then we can use this recursively to find the top $$k$$ components. State formally an algorithm that achieves this (assuming a function that computes the top component).

Under the assumption that all the eigenvalues of $$A$$ are distinct, use induction to prove that your algorithm works.

#### Part II: Analysis

You should do only Part I from this homework assignment.

If you attempt the bonus questions, I will also assign some extra credit value to your answers.

Resources: The data set from the 1000 genomes project.