|
|
Line 1: |
Line 1: |
| == Eigen Decomposition == | | == Eigen Decomposition == |
| Eigen Decomposition or, sometimes, Eigenvalue Decomposition (shortcut EVD) | | Eigen Decomposition or, sometimes, Eigenvalue Decomposition (shortcut EVD) |
− | * is a way of diagonalizing a square $n \times n$ matrix $A$ | + | * is a way of [[Diagonalization|diagonalizing]] a square $n \times n$ matrix $A$ |
− | | + | * We can turn a matrix into a diagonal one by using eigenvectors |
− | | + | |
− | We can turn a matrix into a diagonal one by using eigenvectors | + | |
− | * $A$ is square
| + | |
| | | |
| | | |
Line 13: |
Line 10: |
| ** (a matrix $A$ is similar to $B$ if there exists an invertible $M$ s.t. $B = M^{-1} A \, M$) | | ** (a matrix $A$ is similar to $B$ if there exists an invertible $M$ s.t. $B = M^{-1} A \, M$) |
| * $A$ is diagonalizable if there exists [[Inverse Matrices|invertible matrix]] $P$ s.t. $P^{-1} A \, P$ is diagonal | | * $A$ is diagonalizable if there exists [[Inverse Matrices|invertible matrix]] $P$ s.t. $P^{-1} A \, P$ is diagonal |
− |
| |
| | | |
| | | |
Line 23: |
Line 19: |
| | | |
| | | |
− | Diagonalization: | + | === [[Diagonalization]] === |
| + | We can diagonalize $A$: |
| * $S^{-1} A S = \Lambda$ | | * $S^{-1} A S = \Lambda$ |
− | * $\Lambda = \text{diag } (\lambda_1, \ ... \ , \lambda_n)$ | + | * $\Lambda = \text{diag} (\lambda_1, \ ... \ , \lambda_n)$ |
| | | |
| | | |
Line 149: |
Line 146: |
| ** thus $\lambda_1$ controls everything | | ** thus $\lambda_1$ controls everything |
| * and we can approximate $F_{100} \approx c_1 \lambda_1^{100}$ | | * and we can approximate $F_{100} \approx c_1 \lambda_1^{100}$ |
− |
| |
| | | |
| | | |
Line 157: |
Line 153: |
| * http://en.wikipedia.org/wiki/Diagonalizable_matrix | | * http://en.wikipedia.org/wiki/Diagonalizable_matrix |
| * Strang, G. Introduction to linear algebra. | | * Strang, G. Introduction to linear algebra. |
| + | * [[Matrix Computations (book)]] |
| | | |
| | | |
| [[Category:Linear Algebra]] | | [[Category:Linear Algebra]] |
| [[Category:Matrix Decomposition]] | | [[Category:Matrix Decomposition]] |
Latest revision as of 16:59, 28 June 2017
Eigen Decomposition
Eigen Decomposition or, sometimes, Eigenvalue Decomposition (shortcut EVD)
- is a way of diagonalizing a square $n \times n$ matrix $A$
- We can turn a matrix into a diagonal one by using eigenvectors
Eigenvalue decomposition is a decomposition of a matrix into a "canonical form"
- we want to constrict a diagonal matrix from a given one
- a matrix $A$ is diagonalizable if it's similar to a diagonal matrix
- (a matrix $A$ is similar to $B$ if there exists an invertible $M$ s.t. $B = M^{-1} A \, M$)
- $A$ is diagonalizable if there exists invertible matrix $P$ s.t. $P^{-1} A \, P$ is diagonal
Why can we do it?
- if all eigenvalues $\lambda_1, \ ... \ , \lambda_n$ are different
- then all eigenvalues $\mathbf x_1, \ ... \ , \mathbf x_n$ are linearly independent
- so any matrix with distinct eigenvalues can be decomposed by eigenvalue decomposition
- see proof in Eigenvalues and Eigenvectors
We can diagonalize $A$:
- $S^{-1} A S = \Lambda$
- $\Lambda = \text{diag} (\lambda_1, \ ... \ , \lambda_n)$
Eigenvalue Decomposition:
- if $A$ is symmetric, then there exists $S$ and $\Lambda$ s.t.
- $A = S \Lambda S^T$
- because for symmetric $A$ the eigenvectors in $S$ are orthonormal, so $S$ is Orthogonal
Intuition
Suppose we have $n$ linearly independent eigenvectors $\mathbf x_i$ of $A$
- let's put them in columns of a matrix $S$ - eigenvector matrix
- [math]S = \begin{bmatrix}
| & & | \\
\mathbf x_1 & ... & \mathbf x_n \\
| & & | \\
\end{bmatrix}[/math]
Now what if we multiply $AS$?
- since all these $\mathbf x_i$ are eigenvectors, $A \mathbf x_i = \lambda_i \mathbf x_i$
- thus, [math]AS = A \begin{bmatrix}
| & | & & | \\
\mathbf x_1 & \mathbf x_2 & ... & \mathbf x_n \\
| & | & & | \\
\end{bmatrix} = \begin{bmatrix}
| & | & & | \\
\lambda_1 \, \mathbf x_1 & \lambda_2 \, \mathbf x_2 & ... & \lambda_m \, \mathbf x_n \\
| & | & & | \\
\end{bmatrix}[/math]
- ok, now let's take the $\lambda_i$'s out: [math]\begin{bmatrix}
| & & | \\
\lambda_1 \, \mathbf x_1 & \lambda_2 \, \mathbf x_2 & ... & \lambda_m \, \mathbf x_n \\
| & & | \\
\end{bmatrix} = \begin{bmatrix}
| & | & & | \\
\mathbf x_1 & \mathbf x_2 & ... & \mathbf x_n \\
| & | & & | \\
\end{bmatrix}
\begin{bmatrix}
\lambda_1 & 0 & \cdots & 0 \\
0 & \lambda_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \lambda_n \\
\end{bmatrix}[/math]
- let's call this diagonal matrix [math]\Lambda = \begin{bmatrix}
\lambda_1 & 0 & \cdots & 0 \\
0 & \lambda_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \lambda_n \\
\end{bmatrix}[/math]
- so $AS = S \Lambda$
Decomposition
- if $S$ is invertible (or all $\mathbf x_i$ are independent), then
- $\Lambda = S^{-1} A \, S$ - this is called diagonalization of $A$
- and $A = S \Lambda S^{-1}$ - another factorization of $A$
- if $A$ is diagonal, then $\Lambda = A$, but if it's triangular, we still need to calculate $\Lambda$
For symmetric $A$
- its eigenvalues are orthonormal,
- so the matrix $S$ is orthogonal
- thus, $A = S \Lambda S^{-1} = S \Lambda S^T$
- So we write $A = Q \Lambda Q^T$, where $Q$ is orthogonal
Use Cases
Calculating Powers: $A^k$
- if $A \mathbf x = \lambda \mathbf x$ then
- $A^2 \mathbf x = \lambda A \mathbf x = \lambda^2 \mathbf x$
- so $\lambda$s are squared when $A$ is squared
same for diagonalizable matrices:
- $A^2 = A A = (S \Lambda S^{-1}) (S \Lambda S^{-1}) = S \Lambda^2 S^{-1}$
- and $A^k = S \Lambda^k S^{-1}$
- so this factorization is better for powers than LU Factorization
This is useful for calculating the steady state probabilities of Markov Chains - by calculating the powers of Stochastic Matrices - matrix representation of a Markov Chain
Suppose you are given a vector $\mathbf u_0$ and a recurrent formula $\mathbf u_{k+1} = A \mathbf u_{k}$
- how would you find $\mathbf u_{100}$?
- can repeat it 100 times
- or, note that $\mathbf u_{100} = A \mathbf u_{99} = A^2 \mathbf u_{98} = \ ... \ = A^{100} \mathbf u_{0}$
- Suppose $A$ is invertible.
- Then one possible basis for $A$ is its eigenvectors $\mathbf v_i$
- let's express $\mathbf u_0$ in this basis: $\mathbf u_0 = c_1 \mathbf v_1 + \ ... \ + c_n \mathbf v_n = S \mathbf c$
- now let's multiply both parts by $A$:
- $A \mathbf u_0 = A c_1 \mathbf v_1 + \ ... \ + A c_n \mathbf v_n = A S \mathbf c$
- $A \mathbf u_0 = c_1 \lambda_1 \mathbf v_1 + \ ... \ + c_n \lambda_n \mathbf v_n = \Lambda S \mathbf c$
- then $\mathbf u_{100} = c_1 \lambda_1^{100} \mathbf v_1 + \ ... \ + c_n \lambda_n^{100} \mathbf v_n = \Lambda^{100} S \mathbf c$
- Fibonacci numbers is a sequence 0, 1, 1, 2, 3, 5, 8, 13...
- $F_{k + 2} = F_{k+ 1} + F_{k}$
- it's a second order Recurrence Equation
- Let's build a system: [math]\begin{cases}
F_{k+2} = F_{k+1} + F_{k} \\
F_{k+1} = F_{k+1} \\
\end{cases}[/math]
- so let $\mathbf u_k = \begin{bmatrix} F_{k+1} \\ F_{k} \end{bmatrix}$,
- then $\mathbf u_{k + 1} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{k+1} \\ F_{k} \end{bmatrix} = A \, \mathbf u_k$
- so we have the recurrence equation $\mathbf u_{k+1} = A \mathbf u_k$
- note that $A$ is symmetric, so it's diagonalizable
- let's find eigenvalues:
- [math]| A - \lambda I | = \begin{vmatrix}
1 - \lambda & 1 \\
1 & -\lambda
\end{vmatrix} = \lambda^2 - \lambda - 1 = 0[/math]
- or $\lambda_{1,2} = \cfrac{1 \pm \sqrt{1+4}}{2} = \cfrac{1 \pm \sqrt{5}}{2}$
- $\lambda_1 = 0.5 \, (1 + \sqrt{5}) \approx 1.618$
- $\lambda_1 = 0.5 \, (1 - \sqrt{5}) \approx -0.618$
- so, $\mathbf u_{100} = c_1 \lambda_1^{100} \mathbf v_1 + c_2 \lambda_2^{100} \mathbf v_2$
- $\lambda_1 > 1$ so powers of it grow faster, and $|\lambda_2| < 1$, so its powers decay
- thus $\lambda_1$ controls everything
- and we can approximate $F_{100} \approx c_1 \lambda_1^{100}$
Sources