[Linear Algebra] Matrix Decomposition

---

 

Cholesky Decomposition

숄레스키 분해의 이해를 위해 실수에서 간단한 예시를 들면 다음과 같다. $9 = 3 \times 3$

Theorem

행렬 $\mathbf{A}$가 $\text{symmetric, positive definite matrix}$일 때, $\bf {A} = LL^T$
($\mathbf{L}$ is a lower-triangular matrix with positive diagonals [하삼각행렬, 양수 대각성분])
$\mathbf{L}$은 유일하며, A의 Cholesky factor라 한다.

Determinant

• 숄레스키 분해를 사용하면 determinant 계산이 쉬워진다.

$$det(\mathbf A) = det(\mathbf L)det(\mathbf L^T) = det(\mathbf L^2), \ where \ det(\mathbf L) = \Pi_i \mathbf {I}_{ii}$$

$$Thus, \ det(\mathbf A) = \Pi_i \mathbf {I}_{ii}$$

행렬 $\mathbf A$를 숄레스키 분해를 통해 $\mathbf {LL^T}$로 분해하면, $det(\mathbf A)$는 대각성분의 곱의 제곱과 같다.

Cholesky Decomposition을 이용하여 determinant 계산을 쉽게 할 수 있다.
그 이상의 여러 행렬 연산들을 쉽게 할 수 있는 다른 Decomposition 방법에 대해 알아보자.

---

Eigendecomposition

Diagonal Matrix

• 대각성분을 제외한 모든 성분이 0인 행렬.
  ex)
  $$\mathbf {D} = \begin{bmatrix}d_1 & \cdots & 0 \cr \vdots & \ & \vdots \cr 0 & \cdots & d_n\end{bmatrix}$$
• 대각행렬은 제곱 연산, determinant 계산 등 다양한 연산에 용이하다.
  $$\mathbf {D^k} = \begin{bmatrix}d_1^k & \cdots & 0 \cr \vdots & \ & \vdots \cr 0 & \cdots & d_n^k\end{bmatrix}$$
  $$det(\mathbf D) = d_1d_2\cdots d_n$$

Diagonalizable

• Definition
  대각행렬 $\mathbf D$에 대하여 $\bf D=P^{-1}AP$인 대각행렬 $\bf D$와 가역행렬 $P \in \Reals^{n \times n}$이 존재할 때, $\mathbf A \in \Reals^{n \times n}$은 diagonalizable하다. (대각화 가능하다.)

$\bf D=P^{-1}AP$이면, $\bf A = PDP^{-1}$이고, $\bf A^2 = PDP^{-1}PDP^{-1} = PD^2P^{-1}$
제곱, determinant 연산이 편해진다.
$$\bf A^k = PD^kP^{-1}$$
$$det(\mathbf A) = det(\mathbf P)det(\mathbf D)det(\mathbf P^{-1}) = det(\mathbf D) = \Pi_i d_{ii}$$

이때, $\mathbf P$가 orthogonal이면 ($\bf P^{-1} = P^T$ $\bf PP^T = I$) $\bf A$는 orthogonally diagonalizable하다고 한다.
$$\bf D=P^{-1}AP = P^TAP$$

Orthogonally Diagonaliable and Symmetric Matrix

$\bf A$가 symmetric이면 orthogonally diagonalizable이다.

Spectral Theorem에 의해, $\bf A$가 symmetric이면,

• 모든 eigenvalue는 실수이고,
• eigenvector들은 모두 수직하며,
• orthogonal eigenbasis가 존재한다.

$\bf P$는 orthogonal matrix이므로, $\bf P^T = P^{-1}$이고, $\bf A = PDP^T$

---

SVD [Singular Value Decomposition]

$\bf A$가 symmetric하지 않은 non-square matrix일 경우, Eigendecomposition을 사용하지 못한다.
SVD가 그에 대한 해결책으로, 일반적인 모든 행렬에 대해 Decomposition을 수행한다.

Background

행렬 $\mathbf A \in \Reals^{\m \times n}$에 대하여, $\bf S := A^TA \in \Reals^{n \times n}$은 항상 symmetric하며, 항상 positive semidefinite이다. (모든 eignevalue는 0 이상이다.)

S는 symmetric으로 Eigendecomposition이 가능하다. 이것을 $\bf A$에 대한 Decomposition에 활용하는 것이 SVD

Singular Value Decomposition

$\bf A \in \Reals^{m \times n}$에 대하여, $\bf A$의 SVD는 다음과 같다.
$$\bf A = U\Sigma V^T \quad \text{(U, V는 항상 Orthogonal Matrix)}, \quad \bf UU^T = VV^T = I$$
$\bf U$의 행벡터를 left singular vector, $\bf V$의 열벡터를 right singular vector라 한다.