Eigen decomposition

If $A$ is Digonalizable,

A = V D V^{- 1}

Linear Transformation compute

Linear Combination에서의 computing을 줄이기 위해 Eigendecomposition을 고려할 필요가 있다.
$A x = V D V^{- 1} x$ 로 linear Combination을, 3번에 걸쳐 나누어 계산한다. linear combination은 늘어나지만, $x$ 를 eigenvector로 분리해 계산하여서 연산 횟수는 줄인다.

steps

$V D V^{- 1} = V (D (V^{- 1} x))$

$y = V^{- 1} x$ : Eigenvector basis에 곱해질, coefficient를 찾는 과정이 된다.
$z = Dy$ : 대각행렬의 계산은, 단순하다. 대각 성분과 vector를 곱하기만 하면 되므로 computing이 줄어들게 된다. 이 과정은, eigenvalue를 구하는 과정이 된다. Diagonalization에서, $V^{- 1}$ 을 먼저 계산해 eigenvalue를 찾는 것과 같다.
$T (x) = V z$ : $z$ 는 eigenvector basis에 기반한 coordinate이므로, 이를 다시 original standarad basis로 돌리는 과정이 된다.

mutiple Linear Transformation

$A^{k} = (V D V^{- 1}) (V D V^{- 1}) \dots (V D V^{- 1}) = V D^{k} V^{- 1}$

이 때, $D^{k}$ 는 간단하게 계산된다. $D^{k} = λ_{1}^{k} 0 ⋮ 0 0 λ_{2}^{k} ⋱ \dots \dots ⋱ ⋱ 0 0 ⋮ 0 λ_{n}^{k}$

similarity matrix: for symmetric positive(semi-)definite matrix

$A^{⊤} A$ : similarity matrix between all pairs of items, similarity is computed as an inner product. $A A^{⊤}$ : similarity matrix between all pairs of features, indicating a kind of correlations between featrues.