Computing multiple eigenvalues

The power iteration is great for computing a single eigenvalue, but how can we obtain the other eigenvalues as well?

We will now assume that

$$|{\lambda }_1|>|{\lambda }_2|>\cdots >|{\lambda }_n|$$

We will see a modification later to address situations when this is not true. A shift of the eigenvalues will be required.

Recall that

$$A^k={\lambda }_1^k{\mathbf{x}}_1{\mathbf{y}}_1^T+\cdots +{\lambda }_n^k{\mathbf{x}}_n{\mathbf{y}}_n^T$$

As we multiply by $A$, the vector qk converges to x1. What happens if we apply a projection orthogonal to x1?

That is, let’s run the power iteration for $PA$ with

$$P=I-x_1{x}_1^H$$

with $\Vert x_1{\Vert }_2=1$.

We use the Schur decomposition of $A$.

$$PA=PQT{Q}^H=\sum _{k\ge 2}{q}_{,k}[T{Q}^H{]}_{k,}=\sum _{k\ge 2}{q}_{,k}{t}_{k,}{Q}^H$$

Define $\tilde{T}$ such that its first row is 0

$${\tilde{T}}_{1,}=0$$

and

$${\tilde{T}}_{i,}=T_{i,}$$

when $i\ge 2$. Then:

$$PA=\sum _{k\ge 1}{q}_{,k}{\tilde{t}}_{k,}{Q}^H=Q\tilde{T}{Q}^H$$

This is the Schur decomposition of $PA$. The eigenvalues of $PA$ are on the diagonal of $\tilde{T}$ and are equal to 0, ${\lambda }_2$, …, ${\lambda }_n$. So the largest eigenvalue of $PA$ is ${\lambda }_2$. Its eigenvector is $q_2$.

Therefore, the power iteration applied to $PA$ yields ${\lambda }_2$ and $q_2$.

We can generalize this process and get all the eigenvalues. To get ${\lambda }_{i+1}$ we need to apply the power iteration to:

$$P_{\{q_1,q_2,\dots ,q_i{\}}^{\perp }}A$$

The largest eigenvalue is now ${\lambda }_{i+1}$ and its eigenvector is $q_{i+1}$.

This is a nice algorithm, but it is fairly complicated. You need to calculate $q_1$, then $q_2$, $q_3$, etc. We will see later on a faster and simpler way to perform this calculation.