Power method - deflation

Power 迭代法目錄:

  1. 基本概念

    Power iteration; inverse power method; shifted inver power method

  2. 找第二大的 eigenvalue

    deflation

  3. Rayleigh Quotient 迭代及其收斂性

    Power method with Rayleigh Quotient


Deflation

對一方陣 $A$, 假設我們以 power iteration 找到了一組 eigenvalue/eigenvector, $\lambda$ and $v$, 使得 $Av = \lambda v$. 那要怎麼找下一組呢?

1. Matrix tranformation

假設能找到一個向量 $x$ 使 $x^T v = 1$, 則我們定義 $$ \tag{1} B = A - \lambda v x^T, $$ 並且以 $B$ 來找 eigenvalue/eigenvector. 那 $A$ 與 $B$ 之間有什麼關係呢?

  1. $B$ 的一組 eigenvalue/eigenvector 為 $0$ 與 $v$, 滿足 $Bv = 0v$.
  2. $B$ 其他所有的 eigenvalues 都跟 $A$ 一樣.

pf of 1:

$$ Bv = (A - \lambda v x^T)v = Av - \lambda v (x^Tv) = Av - \lambda v=0. $$

pf of 2:

假設 $w$ 是 $A$ 的 left-eigenvector, 其 eigenvalue 為 $\lambda_2\ne \lambda$, 滿足 $w^TA = \lambda_2w^T$, 則我們知道 $w^Tv=0$, 並且 $$ w^TB = w^T(A - \lambda v x^T) = w^TA - \lambda (w^Tv)x^T = w^TA = \lambda_2w^T. $$ 因此 $\lambda_2$ 亦為 $B$ 的 eigenvalue.


所以我們會利用找 $B$ 的 eigenvalue 來找 $A$ 的 eigenvalue.


那假設我們找到 $B$ 的 eigenvalue 跟 eigenvector 了, 稱之為 $\lambda_2$ 以及 $u_2$, 那我們知道 $\lambda_2$ 也是 $A$ 的 eigenvalue, 不過其相對應的 eigenvector 是誰呢?

若 $B$ 有 eigenvalues $0,\lambda_2, \cdots, \lambda_n$ 以及 eigenvectors $v, u_2, u_3, \cdots, u_n$, 則 $$ \tag{2} v_i = (\lambda_i-\lambda) u_i + \lambda (x^T u_i) v, \quad i=2,\cdots, n, $$ 並且 $Av_i = \lambda_i v_i$.

pf

因為 $u_i$ 是 $B$ 的 eigenvector, 所以 $$ \lambda_i u_i = Bu_i = (A - \lambda v x^T)u_i = Au_i - \lambda(x^Tu_i)v. $$ 因此 $$ Au_i = \lambda_i u_i +\lambda(x^Tu_i)v. $$ 那麼 $$ \begin{align} Av_i &= (\lambda_i-\lambda) Au_i + \lambda (x^T u_i) Av \\
&= (\lambda_i-\lambda)(\lambda_i u_i +\lambda(x^Tu_i)v) + \lambda^2 (x^T u_i) v\\
&= \lambda_i((\lambda_i-\lambda) u_i + \lambda (x^T u_i) v) \\
&=\lambda_i v_i. \end{align} $$


因此, 對 (1) 做 power iteration 可以找出下一個 eigenvalue, 並且利用 (2) 可以得到其 eigenvector.


接下來我們介紹兩種 看起來似乎可以使用 的 deflation 作法. 不過實際使用起來有一些問題!


2. Eigen-decomposition

對一個方陣, 如果我們可以找到所有的 eigenvalues 跟 eigenvectors, 並且有以下關係 $$ A V = V\Lambda \quad \longleftrightarrow \quad A = V\Lambda V^{-1} $$ 並且我們將 $V$, $\Lambda$, $V^{-1}$ 記為 $$ V = [v_1, v_2, \cdots, v_n], \quad \Lambda = \text{diag}\{\lambda_1, \lambda_2, \cdots, \lambda_n\},\quad V^{-1} = \begin{bmatrix} w^T_1 \\ w^T_2 \\ \vdots \\ w^T_n\end{bmatrix}. $$ 則 $$ A = \lambda_1 v^1w^T_1 + \lambda_2 v^2w^T_2 + \cdots + \lambda_n v^nw^T_n. $$

有趣的是, 若我們定義 $$ \tag{3} B = A-\lambda_1 v^1w^T_1, $$ 則可以很輕易地看出 $B$ 的 eigenvectors 與 $A$ 的完全一樣, 而 eigenvalues 也幾乎完全一樣, 只有 $\lambda_1$ 被移到 $0$ 去了.


因此, 若我們知道一個 eigenvalue, 以及其相對應的 left and right eigenvectors, 則可以用 (3) 來做 power iteration 找出下一個 eigenvalue, 並且它的 eigenvector 就會是 $A$ 的 eigenvector.

Note: 不過實務上 left eigenvector 比較難找, 需要先找出 linear operator 的 adjoint operator (也就是 $A^T$) 才有辦法做矩陣-向量乘法, 因此這個方法除了對稱的情況外幾乎不會被使用.

Note: 當 $A$ 是 symmetric, 則可以選擇 $v_i$ 使得 $w_i = v_i$, 在這時候我們就可以輕易地使用 (3) 來找下一組了.


3. Annihilation

給定 $A$ 為一個 $n\times n$ 方陣. 我們做以下兩個假設

  1. 它的 eigenvalues 滿足 $$ |\lambda_1| > |\lambda_2| > |\lambda_3| \cdots |\lambda_n|. $$
  2. 相對應的 eigenvectors, $\{v_1, v_2, \cdots, v_n\}$, 會構成 $R^n$ 的一組基底.

Observation

如果初始向量我們選擇 $y$ 使得 $$ \tag{4} y = \sum_{i=2}^n c_iv_i, $$ 也就是沒有 $v_1$ 的分量, 則 power iteration 會找到 $\lambda_2$ 以及 $v_2$.

當然, 任意給一個向量並無法滿足 (4) 這個條件, 不過若我們定義 $$ \tag{5} y = A x - \lambda_1 x, $$ 則對任意一個向量 $x$, 這個 $y$ 就會滿足 (4).

pf

Let $x = \sum^{n}_{i=1} c_iv_i$, then

$$ \begin{aligned} y &= A x - \lambda_1 x \\
&= \sum^n_{i=1} (c_iAv_i - c_i\lambda_1v_i) \\
&= \sum^n_{i=2} c_i(\lambda_i-\lambda_1)v_i. \end{aligned} $$


因此, 若我們知道一個 eigenvalue, 則可以任取一個向量 $x$ 再用 (5) 來做出 power iteration 的初始值, 這樣就可以找出下一個 eigenvalue, 並且它的 eigenvector 就會是 $A$ 的 eigenvector.

Note: 不過實際在做的時候, 由於 $\lambda_1$ 有數值誤差, 因此 (5) 並不會完全滿足 (4), 在設計 power iteration 的時候要小心這件事.


Avatar
Te-Sheng Lin (林得勝)
Associate Professor

The focus of my research is concerned with the development of analytical and computational tools, and further to communicate with scientists from other disciplines to solve engineering problems in practice.

Related