A Fresh Approach to the Singular Value Decomposition 마지막

원문: 1998, Colm Mucahy and John Rossi, A Fresh Approach to the Singular Value Decomposition

선행개념: 행렬, 대각행렬, 전치행렬, 역행렬, 직교행렬, 고윳값, 고유벡터, 대각화, 직교대각화.

목차

1. 소개
2. 복소수의 극형식과 행렬의 극분해(Polar Decomposition)
3. 특이값 분해(Singular Value Decomposition)
4. 의사 역행렬(Pseudo-inverse)
5. Solving All Systems

항이 실수인 행렬만 다루며, 여기서는 4~5의 주제를 다룬다.

연결된 포스팅 링크: 1부(주제1,2), 2부(주제3), 3부(주제4,5)

---

이전 포스팅에서 다루었던 SVD를 이용하면 모든 행렬에 대해서 역행렬을 구할 수 있게 된다. 비가역이거나 정사각행렬이 아니어도 된다.

4. Pseudo inverses

원리는 간단하다. 모든 $m \times n$ 행렬 $A$에 대해 은 $A=UDV^T$꼴로 나타낼 수 있고 행렬 $U,V$는 직교행렬이므로 역행렬이 존재하고 각각 $U^{-1}=U^T, \, {V^T}^{-1}=V$이 된다.(직교행렬의 정의)
행렬 $D$는 $m \times n$ 인 대각행렬이므로 $D^{+}$을 $n \times m$꼴로 0이 아닌 대각선의 항을 역수로 놓으면 $D D^{-1}=I_m, \, D^{-1} D=I_n$ ($I_k$는 $k \times k$인 단위행렬)이 된다. 이상을 정리하면 다음과 같다.

$\mathbf{Theorem}$. 모든 행렬은 가역이다.(역행렬이 존재한다.)
$m \times n$ 행렬 A에 대해 의사 역행렬(일반화된 역행렬, Pseudo Inverse)는 다음과 같이 정의된다.
$$A^{+} = V D^{+} U^T$$
$D^{+}$는 $D^T$의 0이 아닌 항을 역수한 행렬이다.

의사역행렬(Pseudo-inverses)은 아래와 같은 성질을 만족한다.

1. $A A^{+} = I_m, \, A^{+} A = I_n$
2. $A A^{+}, \, A^{+} A$ 은 서로 대칭이다.
3. $A A^{+} A = A$
4. $A^{+} A A^{+} = A^{+}$
5. $(A^{+})^{+}=A$
6. $A^{+}$은 유일하게 결정된다.

예1. 가역행렬

$A= \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix}$
$A= \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix} ^T$
$A^{-1} = \begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} \frac{1}{3} & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{bmatrix}^T = \begin{bmatrix} -\frac{1}{3} & \frac{2}{3} \\ \frac{2}{3} & -\frac{1}{3} \end{bmatrix}$

예2. 역행렬이 존재하지 않는 행렬

$A= \begin{bmatrix} -1&2 \\ 2&-4 \end{bmatrix}$

$A = \begin{bmatrix} -\frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}} \\ \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{5}} \end{bmatrix} \begin{bmatrix} 5 & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} -\frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}} \\ \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{5}} \end{bmatrix}^T$

$A^{+} = \begin{bmatrix} -\frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}} \\ \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{5}} \end{bmatrix} \begin{bmatrix} \frac{1}{5} & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} -\frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}} \\ \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{5}} \end{bmatrix}^T = \begin{bmatrix} -\frac{1}{25} & \frac{2}{25} \\ \frac{2}{25} & -\frac{4}{25} \end{bmatrix}$

예3. 정사각행렬이 아닌 경우

$A = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$

$A = \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} \sqrt{2} \\ 0 \end{bmatrix} \begin{bmatrix} 1 \end{bmatrix}^T$

$A^{+} = \begin{bmatrix} 1 \\ 1 \end{bmatrix} ^+ = \begin{bmatrix} 1 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & 0 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{bmatrix}^T$

---

5. Solving All Systems

$\mathbf{Theorem}$. 모든 선형구조의 문제는 풀 수 있다.

$Proof$. 모든 선형구조는 선형방정식 $A \mathbf{x} = b$ 의 꼴로 나타낼 수 있다. 행렬 $A$는 $m \times n$ 행렬이고 $\mathbf{x}$ 는 n개의 미지수로 이루어진 열벡터이다. 위의 정리에 의해 의사역행렬 $A^+$이 존재해 $w = A^+ b$이 해가 됨을 알 수 있다.

엄밀히 말하면 정확하게 해가 존재하는 것은 아니다. 이런 형태의 해를 관찰하면 최소제곱법으로 구한 결과와 같음을 알 수 있다. 또한 SVD를 이용하면 충분히 작은 고윳값들을 버려 데이터의 차원을 축소할 수 있다. 공분산을 이용한 PCA방법과 정확히 일치하는데 SVD가 훨씬 연산에서 빠르다. 가능하다면 이 부분에 대해 추후 다른 포스팅에서 다뤄보도록 하겠다.