1
$\begingroup$

Suppose that $a$ is in $C^{n\times n}$ and has $n$ distinct eigenvalues $|\lambda_1| \geq \cdots \geq |\lambda_n|$, corresponding to unit eigenvectors $V = \{V_1, \cdots, V_n\}$.

Further suppose that $S$ is a $k$-dimensional subspace spanned by the ordered set $\{ \sum_i \alpha_{i, 1}V_i, \cdots, \sum_i \alpha_{i, k}V_i \} = \{ W_1, \cdots, W_k \} = W$.

After $r$ subspace iterations, the subspace $a^rS$ is spanned by $\{ \sum_i \lambda_i^r \alpha_{i, 1}V_i, \cdots, \sum_i \lambda_i^r \alpha_{i, k} V_i \} = \{ W^r_1, \cdots, W^r_k \} = W^r$.

The claim is that these subspaces approach the subspace spanned by the dominant $k$ eigenvectors: $S^\infty = \operatorname{span}(W^\infty) = \operatorname{span}\{V_1, \cdots, V_k \}$.

I understand why this is true in an intuitive way: if you keep multiplying by $a$ and then orthonormalizing, you get convergence of $\hat{W^r_1}$ to $V_1$ from simple power iteration, and consecutive unit vectors in the spanning set are orthogonal, so they have to converge to the dominant eigenvector of the space obtained by removing the previous eigenspaces.

However, I'm having trouble formally deriving the convergence of $W^r$ to an $a$-invariant flag, from which I also want to derive an expression for the rate of convergence. What would be the best way to go about doing this?

Edit: After some further thinking I've arrived at this proof for the convergence of $S^r$ to $\operatorname{span}\{ V_1, \cdots, V_k\}$:

First, we lay out $W^r$ as a $k \times n$ matrix: $$\begin{matrix} \lambda_1^r \alpha_{1, 1} & \dots & \lambda_1^r \alpha_{1, k}\\ \vdots & \ddots & \vdots\\ \lambda_k^r \alpha_{k, 1} & \dots & \lambda_k^r \alpha_{k, k}\\ \vdots & \ddots & \vdots\\ \lambda_n^r \alpha_{n, 1} & \dots & \lambda_n^r \alpha_{n, k} \end{matrix}$$.

Next we column reduce to get: $$\begin{matrix} 1 & \dots & 0\\ \vdots & \ddots & \vdots\\ 0 & \dots & 1\\ (\lambda_{k+1}/\lambda_1)^r \beta_{1, 1} & \dots & (\lambda_{k+1}/\lambda_k)^r \beta_{1, k}\\ \vdots & \ddots & \vdots\\ (\lambda_n/\lambda_1)^r \beta_{n-k, 1} & \dots & (\lambda_n/\lambda_k)^r \beta_{n-k, k} \end{matrix}$$.

Now this clearly converges to $$\begin{matrix} I_k\\0_{k\times (n-k)} \end{matrix}$$ when $|\lambda_k| > |\lambda_{k+1}|$, since the entries below the identity block are individually converging to $0$ with a rate of at least $|\lambda_{k+1}|/|\lambda_k|$.

Can we say then that $S^r$ converges to $\operatorname{span}\{V_1, \cdots, V_k\}$ with a rate of $|\lambda_{k+1}|/|\lambda_k|$?

To be more formal, we can equip the space of $k$-dimensional subspaces with the metric obtained by column-reducing candidate spanning sets of $S$ and $T$ to matrices $a_S$ and $a_T$ as above, and taking the maximum norm of $a_S-a_T$ to be the distance between $S$ and $T$; in this metric, the above convergence rate does indeed hold... But is this a practical metric for numerical practice, or is there a more useful one to use?

It remains to show that $W^\infty$ is an invariant flag; in particular if $k=n$, the above trivially shows that $S^r = \operatorname{span}(V)$ for any $r$, since both span the entire space.

Edit 2: Here's my attempt at a proof for invariance:

We proceed by induction on the dimension of $S$.

When $k=1$, $S^\infty = \operatorname{span}\{V_1\}$, which is indeed $a$-invariant, and $\{W^\infty_1\}$ is a trivial flag.

Now suppose that $w'^\infty = \{W^\infty_1, \cdots, W^\infty_{k-1}\}$ is an $a$-invariant flag and that $\operatorname{span}(W'^\infty) = \operatorname{span}\{V_1, \cdots, V_{k-1}\}$.

In particular, we necessarily have that $\operatorname{span}(W^\infty) = \operatorname{span}(W'^\infty) \oplus \operatorname{span}\{W^\infty_k\}$.

This shows that $\operatorname{span}(W^\infty)$ properly contains $\operatorname{span}(W'^\infty)$, which is what is needed for $W^\infty$ to be a flag.

$a$-invariance is also preserved since $S^\infty = \operatorname{span}\{V_1, \cdots, V_k\}$ is an invariant subspace.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.