Chapter7-Eigenvalues and singular values

Eigenvalues and Singular Values

Gauss of Eigenvalues

Gershgorin theorem

Gershgorin theorem 2

example of eigenvalues guess using Gershaorin theorem

Example

Power Iteration

The motivation behind Power Iteration is that multiplication by a matrix tends to move vectors toward the dominant eigenvector direction.

Power Iteration is essentially a fixed-point iteration with normalization at each step. Like FPI, it converges linearly at rate of $|\frac{{\lambda }_2}{{\lambda }_1}|$

Let A be an $n\times n$ matrix with real eigenvalues ${\lambda }_1,\cdots ,{\lambda }_n$ satisfying ${\lambda }_1⩾{\lambda }_2,\cdots ,⩾{\lambda }_n$ . Assume that the eigenvectors of $A$ $(v_1,v_2,\cdots ,v_n)$ span ${\mathbb{R}}^n$ .

For almost every initial vector, Power Iteration converges linearly to an eigenvector associated to ${\lambda }_1$ with convergence rate constant $S=|\frac{{\lambda }_2}{{\lambda }_1}|$ .

$$\begin{array}{rl}{x}_k& =A^k{x}_0=A^k\left(c_1{v}_1+c_2{v}_2\cdots +c_n{v}_n\right)\\ & ={\lambda }_1^k\left[c_1{v}_1+{\left(\frac{{\lambda }_2}{{\lambda }_1}\right)}^k{c}_2{v}_2+\cdots +{\left(\frac{{\lambda }_n}{{\lambda }_1}\right)}^k{c}_n{v}_n\right]\end{array}$$

1. $|{\lambda }_1|>|{\lambda }_2|\ge \cdots \ge |{\lambda }_n|$

$$\begin{array}{rl}\underset{k\to \infty }{\lim }{x}_k& ={\lambda }_1^k\left[c_1{v}_1+{\left(\frac{{\lambda }_2}{{\lambda }_1}\right)}^k{c}_2{v}_2\right],c_1\ne 0\\ x_k& \approx {\lambda }_1{x}_{k-1}\\ S& ⩽|{\lambda }_2/{\lambda }_1|\end{array}$$

2. $|{\lambda }_1|=|{\lambda }_2|>\cdots \ge |{\lambda }_n|,{\lambda }_1=-{\lambda }_2$

$$\begin{array}{rl}\underset{k\to \infty }{\lim }{x}_k& ={\lambda }_1^k\left[\underset{w}{\underbrace{c_1{v}_1+(-1{)}^k{c}_2{v}_2}}+{\left(\frac{{\lambda }_3}{{\lambda }_1}\right)}^k{c}_3{v}_3\right],w\ne 0\\ x_k& \approx {\lambda }_1^2{x}_{k-2}\\ S& ⩽|{\lambda }_3/{\lambda }_1|\end{array}$$

example of Power iteration method

Suppose we have matrix $A$ in which we want to get its max eigenvalue：

$$A=\left[\begin{array}{ccc}4& -1& 1\\ -1& 3& -2\\ 1& -2& 3\end{array}\right]$$

Firstly, choose a initial guess vector ${\mathbf{x}}^{(0)}$ ，Say ${\mathbf{x}}^{(0)}=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]$ 。

The power iteration method:：

1. Compute ${\mathbf{y}}^{(k)}=A{\mathbf{x}}^{(k-1)}$
2. Compute ${\lambda }^{(k)}=\frac{{\mathbf{y}}^{(k)}}{{\mathbf{x}}^{(k-1)}}$
3. Normalization ${\mathbf{x}}^{(k)}=\frac{{\mathbf{y}}^{(k)}}{\Vert {\mathbf{y}}^{(k)}\Vert }$

Repeat the following step until it satisfies some rule. (For example， $\Vert {\mathbf{x}}^{(k)}-{\mathbf{x}}^{(k-1)}\Vert <TOL$ )

Choose a initial guess vector: ${\mathbf{x}}^{(0)}=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]$ 。

Step 1

$${\mathbf{y}}^{(1)}=A{\mathbf{x}}^{(0)}=\left[\begin{array}{ccc}4& -1& 1\\ -1& 3& -2\\ 1& -2& 3\end{array}\right]\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]=\left[\begin{array}{c}4\\ 0\\ 2\end{array}\right]$$

Step 2

$${\lambda }^{(1)}=\frac{{\mathbf{y}}^{(1)}}{{\mathbf{x}}^{(0)}}=\frac{\left[\begin{array}{c}4\\ 0\\ 2\end{array}\right]}{\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]}=4$$

Step 3 Normalization ${\mathbf{x}}^{(1)}=\frac{{\mathbf{y}}^{(1)}}{\Vert {\mathbf{y}}^{(1)}\Vert }=\frac{\left[\begin{array}{c}4\\ 0\\ 2\end{array}\right]}{\sqrt{4^2+0^2+2^2}}=\left[\begin{array}{c}\frac{2}{\sqrt{5}}\\ 0\\ \frac{1}{\sqrt{5}}\end{array}\right]$

Repeat:

$${\mathbf{y}}^{(2)}=A{\mathbf{x}}^{(1)}=\left[\begin{array}{ccc}4& -1& 1\\ -1& 3& -2\\ 1& -2& 3\end{array}\right]\left[\begin{array}{c}\frac{2}{\sqrt{5}}\\ 0\\ \frac{1}{\sqrt{5}}\end{array}\right]=\left[\begin{array}{c}\frac{6}{\sqrt{5}}\\ \frac{2}{\sqrt{5}}\\ \frac{4}{\sqrt{5}}\end{array}\right]$$ $${\lambda }^{(2)}=\frac{{\mathbf{y}}^{(2)}}{{\mathbf{x}}^{(1)}}=\frac{\left[\begin{array}{c}\frac{6}{\sqrt{5}}\\ \frac{2}{\sqrt{5}}\\ \frac{4}{\sqrt{5}}\end{array}\right]}{\left[\begin{array}{c}\frac{2}{\sqrt{5}}\\ 0\\ \frac{1}{\sqrt{5}}\end{array}\right]}=5$$

Normalization ${\mathbf{x}}^{(2)}=\frac{{\mathbf{y}}^{(2)}}{\Vert {\mathbf{y}}^{(2)}\Vert }=\frac{\left[\begin{array}{c}\frac{6}{\sqrt{5}}\\ \frac{2}{\sqrt{5}}\\ \frac{4}{\sqrt{5}}\end{array}\right]}{\sqrt{{\left(\frac{6}{\sqrt{5}}\right)}^2+{\left(\frac{2}{\sqrt{5}}\right)}^2+{\left(\frac{4}{\sqrt{5}}\right)}^2}}=\left[\begin{array}{c}\frac{3}{\sqrt{15}}\\ \frac{1}{\sqrt{15}}\\ \frac{2}{\sqrt{15}}\end{array}\right]$

Repeat step above until it stops. Finally the maximum eigenvalue is $\lambda =5$ ，its corresponding eigenvector $\mathbf{x}=\left[\begin{array}{c}\frac{3}{\sqrt{15}}\\ \frac{1}{\sqrt{15}}\\ \frac{2}{\sqrt{15}}\end{array}\right]$

Other Kinds of Power Iteration

Other Kinds of Power Iteration

example of 位移逆幂法

假设我们要求解矩阵

$$A=\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right]$$

的最大特征值和对应的特征向量。

具体步骤如下：

1. 初始化一个初始向量 $x^{(0)}$，可以是任意非零向量。

2. 对于每一次迭代 $k$，计算位移矩阵 $B=A-\mu I$，其中 $\mu$ 是一个位移量，通常选择接近所求特征值的值。

3. 解线性方程组 $B{x}^{(k+1)}=x^{(k)}$，得到新的迭代向量 $x^{(k+1)}$。

4. 归一化迭代向量 $x^{(k+1)}$，即 $x^{(k+1)}=\frac{x^{(k+1)}}{\Vert x^{(k+1)}\Vert }$。

5. 判断迭代是否收敛，如果满足收敛条件（如 $|x^{(k+1)}-x^{(k)}|<ϵ$），则停止迭代，否则返回步骤 2。

下面我们以 $\mu =10$ 为例，进行迭代计算。

首先，选择一个初始向量 $x^{(0)}=[1,1,1{]}^T$。

迭代计算如下：

$$\begin{array}{rl}k=0:& B=A-\mu I=\left[\begin{array}{ccc}-9& 2& 3\\ 4& -5& 6\\ 7& 8& -1\end{array}\right],x^{(1)}=B^{-1}{x}^{(0)}={\left[\begin{array}{ccc}-0.081& -0.027& 0.108\end{array}\right]}^T\\ k=1:& B=A-\mu I=\left[\begin{array}{ccc}-9& 2& 3\\ 4& -5& 6\\ 7& 8& -1\end{array}\right],x^{(2)}=B^{-1}{x}^{(1)}={\left[\begin{array}{ccc}-0.058& -0.086& 0.142\end{array}\right]}^T\\ k=2:& B=A-\mu I=\left[\begin{array}{ccc}-9& 2& 3\\ 4& -5& 6\\ 7& 8& -1\end{array}\right],x^{(3)}=B^{-1}{x}^{(2)}={\left[\begin{array}{ccc}-0.039& -0.112& 0.187\end{array}\right]}^T\\ & ⋮\end{array}$$

请注意，迭代过程中需要对迭代向量进行归一化，以保证迭代结果的正确性。

Rayleigh Power Iteration

The Rayleigh quotient can be used in conjunction with Inverse Power Iteration. We know that it converges to the eigenvector associated to the eigenvalue with the smallest distance to the shift s, and that convergence is fast if this distance is small. If at any step along the way an approximate eigenvalue were known, it could be used as the shift s, to speed convergence.

Procedure of Rayleigh Power Iteration

Given initial vector $x_0$

$$\begin{array}{rl}forj& =1,2,3,\cdots \\ u_{j-1}& =x_{j-1}/\Vert x_{j-1}\Vert \\ {\lambda }_{j-1}& =u_{j-1}^{\top }A{u}_{j-1}\\ Solve(A-{\lambda }_{j-1}I)x_j& =u_{j-1}\\ end& .\\ u_j=x_j/\Vert x_j{\Vert }_2& \end{array}$$

If A is real symmetric matrix, then Rayleigh power iteration’s convergence speed is $S⩽|{\lambda }_2/{\lambda }_1{|}^2$

QR Decomposition

The goal of this section is to develop methods for finding all eigenvalues at once. We begin with a method that works for symmetric matrices, and later supplement it to work in general. Symmetric matrices are easiest to handle because their eigenvalues are real and their unit eigenvectors form an orthonormal basis of ${\mathbb{R}}^n$ . This motivates applying Power Iteration with $n$ vectors in parallel, where we actively work at keeping the vectors orthogonal to one another.

Reduced QR Decomposition

If matrix $A$ whose column vectors $x_1,x_1,x_3,\cdots ,x_n$ is linear independent, then we can apply Gram-Schmidt Orthogonalization.

Gram-Schmidt Orthogonalization

$$x_1,x_2,x_3,\cdots ,x_n\stackrel{\text{ schmidt }}{⟶}\{\begin{array}{c}{v}_1=x_1\\ v_2=x_2-\frac{x_2\cdot v_1}{v_1\cdot v_1}{v}_1\\ v_3=x_3-\frac{x_3\cdot v_1}{v_1\cdot v_1}{v}_1-\frac{x_3\cdot v_2}{v_2\cdot v_2}{v}_2\\ ⋮\\ v_n=x_n-\frac{x_n\cdot v_1}{v_1\cdot v_1}{v}_1-\cdots -\frac{x_n\cdot v_{n-1}}{v_{n-1}\cdot v_{n-1}}{v}_{n-1}\end{array}$$

Then rewrite it in matrix form:

$$\begin{array}{rl}A& =QR\\ \left[\begin{array}{cccc}{x}_1& x_2& \cdots & x_n\end{array}\right]& =\left[\begin{array}{cccc}{v}_1& v_2& \cdots & v_n\end{array}\right]\left[\begin{array}{ccccc}1& \frac{x_2\cdot v_1}{v_1\cdot v_1}& \frac{x_3\cdot v_1}{v_1\cdot v_1}& \cdots & \frac{x_n\cdot v_1}{v_1\cdot v_1}\\ & 1& \frac{x_2\cdot v_2}{v_2\cdot v_2}& \cdots & \frac{x_n\cdot v_2}{v_2\cdot v_2}\\ & & 1& \ddots & \frac{x_n\cdot v_3}{v_3\cdot v_3}\\ & & & \ddots & 1\end{array}\right]\end{array}$$

Actually, to avoid swamping as we talk in Chapter 3 -System of Equation, one alternative is to normalize the orthogonal vectors. See the example below.

Example of QR factorization

$$A=\left[\begin{array}{cc}1& -4\\ 2& 3\\ 2& 2\end{array}\right]$$

1. $y_1=A_1=[1,2,2{]}^T,r_{11}={\Vert y_1\Vert }_2=3,q_1=\frac{y_1}{{\Vert y_1\Vert }_2}={\left[\frac{1}{3},\frac{2}{3},\frac{2}{3}\right]}^T$
2. $r_{12}=q_1^T{A}_2=2,y_2=A_2-r_{12}{q}_1=\left[\begin{array}{c}-4\\ 3\\ 2\end{array}\right]-2\left[\begin{array}{c}\frac{1}{3}\\ \frac{2}{3}\\ \frac{2}{3}\end{array}\right]=\left[\begin{array}{c}-\frac{14}{3}\\ \frac{5}{3}\\ \frac{2}{3}\end{array}\right]$
3. $r_{22}={\Vert y_2\Vert }_2=5,q_2=\frac{y_2}{{\Vert y_2\Vert }_2}={\left[-\frac{14}{15},\frac{1}{3},\frac{2}{15}\right]}^T$

$$A=\left[\begin{array}{cc}\frac{1}{3}& -\frac{14}{15}\\ \frac{2}{3}& \frac{1}{3}\\ \frac{2}{3}& \frac{2}{15}\end{array}\right]\left[\begin{array}{ll}3& 2\\ 0& 5\end{array}\right]=QR$$

Full QR Decomposition

Difference between the two QR factorization

The modified row and column can be add by adding new linearly independent unit vector and np.zeros rows to the matrix $R$ :

Example of Full QR Factorization.

Full QR Factorization

Modified Gram-Schmidt Orthogonalization

The Classical Gram-Schmidt Orthogonalization may encounter some problem in real world problems such as:

1. Not suitable for sparse matrix;
2. There will be a lot of errors in the ill-conditioned matrix with finite precision;
3. The whole matrix must be saved during the loop, which leads to high memory overhead.

See the Example below:

Example When Classical Gram-Schmidt Orthogonalization Failed

The case of ill-conditioned matrix

The main improvement of MGS is to select a vector as the first datum, and then project it and all the vectors into the orthogonal space of the datum, the first datum is then perpendicular to all the vectors in the orthogonal space. So, after that, we just have to do the same thing for the rest of the vectors in the orthogonal space, and then all the vectors are orthogonal to each other.

MGS

MGS Procedure

Householder Transformation

Since the transformation matrix $H$ in Householder transformation is symmetric orthogonal matrix, then we can replace $Q$ with $H$ . See the example below.

Householder transformation in QR factorization.

Use Householder transformation to apply QR factorization.

Householder Transformation

QR Algorithm

The way the QR algorithm finds eigenvalues of a matrix A is to locate a similar matrix whose eigenvalues are obvious. An example of the latter is real Schur form.

Real Schur form: A matrix $T$ has real Schur form if it is upper triangular, except possibly for $2\times 2$ blocks on the main diagonal. For example, a matrix of the form

$$\left[\begin{array}{ccccc}x& x& x& x& x\\ & x& x& x& x\\ & & x& x& x\\ & & & & x\end{array}\right]$$

Has real Schur form.

Theorems about QR algorithm

Let’s consider the matrix A:

$$A=\left[\begin{array}{ccc}2& 1& 0\\ 1& 3& 1\\ 0& 1& 2\end{array}\right]$$

To find the eigenvalues of $A$ using the QR algorithm, we follow these steps:

1. Start by initializing $A_0$ as the given matrix $A$.

2. Compute the QR decomposition of $A_0$. Let $Q_0$ and $R_0$ be the resulting orthogonal and upper triangular matrices, respectively.

3. Update $A_1=R_0\cdot Q_0$ .

4. Repeat steps 2 and 3 until convergence or a desired number of iterations. Let $A_k$ be the matrix at the k-th iteration.

5. The eigenvalues of A are the diagonal elements of the final upper triangular matrix $A_k$.

Let’s go through the steps for our example:

Step 1:

$$A_0=\left[\begin{array}{ccc}2& 1& 0\\ 1& 3& 1\\ 0& 1& 2\end{array}\right]$$

Step 2: Compute the QR decomposition of $A_0$: $A_0=Q_0\cdot R_0$

Step 3: Update $A_1=R_0\cdot Q_0$

Step 4 : Repeat steps 2 and 3 until convergence or a desired number of iterations.

After a few iterations, we obtain the following matrices:

$$A_1=\left[\begin{array}{ccc}3.317& 2.317& 1.317\\ 0& 1.317& 0.317\\ 0& 0& -0.634\end{array}\right]$$ $$A_2=\left[\begin{array}{ccc}2.585& 1.585& 0.585\\ 0& 1.585& 0.585\\ 0& 0& -0.17\end{array}\right]$$ $$A_3=\left[\begin{array}{ccc}2.414& 1.414& 0.414\\ 0& 1.414& 0.414\\ 0& 0& -0.17\end{array}\right]$$

Step 5: The eigenvalues of A are the diagonal elements of the final upper triangular matrix $A_k$. In this case, the eigenvalues are:

$${\lambda }_1=2.414,{\lambda }_2=1.414,{\lambda }_3=-0.17$$

So, these are the eigenvalues of the given matrix $A$ using the QR algorithm.