2

I am trying to self learn the Power Iteration algorithm for computing the largest eigen vector and eigen value.

I understood that the algorithm works as follows. Assume we are trying to find the largest eigen vector of matrix $A$ of dimention $M\times M$. Then

1- We pick any initial vector ${\bf u^{(0)}}$ of dimension $M\times 1$ then

for $ 1 \leq s \leq N$

2- Find the vector which is the product of ${\bf z}^{(s)}= A {\bf u}^{(s-1)}$

3- extract the element of ${\bf z}$ having the largest amplitude --> $$m^{(s)}= argmax \,\, |z_i^{(s)}|$$

4- then we have that $u^{(s)}=\frac{{\bf z^{(s)}}}{m^{s}}$

I am having hard time understanding why step 3 is needed. Any general intuition on this method will help.

Thanks

Henry
  • 1,204

1 Answers1

1

This process gives us an eigenvector. But since we multiply the initial vector by $A$ repeatedly, the magnitude of the eigenvector might increase unboundedly. For example:

$$A=\begin{pmatrix}1.5&0.5\\0.5&1.5\end{pmatrix}, \vec{u}_0=\begin{pmatrix}0\\1\end{pmatrix}$$

We can easily calculate the first several iterations, without your step 3. We will get: $$\vec{u}_1=\begin{pmatrix}0.5\\1.5\end{pmatrix}\\ \vec{u}_2=\begin{pmatrix}1.5\\2.5\end{pmatrix}\\ \vec{u}_3=\begin{pmatrix}3.5\\4.5\end{pmatrix}$$

You can imagine the numbers will be bigger and bigger. Since the magnitude of the eigenvector does not matter, we normalize the vector in each iteration by step 3, which is to divide the vector by its largest component. So the vector will always have infinity norm $1$. This also makes finding the eigenvalue convenient.

To find the eigenvalue sequences, we perform this: $$\lambda_n=\frac{(A\vec{u}_{n+1})_p}{(A\vec{u}_n)_p}$$

where $p$ means the $p$-th component of the vector. Since each time we divide the vector by its largest component, this component becomes $1$. So we can set $p$ as this component. In this case it becomes $$\lambda_n=(A\vec{u}_{n+1})_p$$

KittyL
  • 16,965