1. 고유값 분해

어떠한 시스템 $\mathbf{A}\mathbf{x}=\mathbf{b}$가 주어졌을 때, 행렬 $\mathbf{A}$가 다음과 같이 대각행렬로 주어지면 시스템의 풀이가 간편해진다.

이러한 관점에서 어떤 행렬이 주어졌을 때 위와 같은 대각행렬로 바꿀 수 있다면, 그 행렬이 나타내는 시스템의 해석이나 풀이가 간단해질 수 있으며, 이를 대각화라고 한다.

$\mathbf{A}\mathbf{x}=\mathbf{b}$가 주어졌을 때, $\mathbf{A}$를 대각화하기 위해서 $\mathbf{P^{-1}}\mathbf{A}\mathbf{P}$와 같은 닮음 변환을 많이 사용하는데, 이러한 닮음 변환은 여러 성질을 갖기 때문이다.

$\mathbf{B}=\mathbf{P^{-1}}\mathbf{A}\mathbf{P}$ 이라고 할 때, $\mathbf{A}, \mathbf{B}$는 서로 닮음이며 다음과 같은 성질을 갖는다.

1. $rank(\mathbf{A})=rank(\mathbf{B})$
2. $nullity(\mathbf{A})=nullity(\mathbf{B})$
3. $\mathbf{A}$와 $\mathbf{B}$의 고유값이 값음

이때 사용된 용어 및 앞으로 사용될 차원정리는 이전 글에 설명되어 있으며, 이제 위의 3가지 성질을 증명해보자.

---

1번 성질을 증명하기 위해 먼저 어떤 가역행렬 $\mathbf{P}$에 대해 $rank(\mathbf{P}\mathbf{A})=rank(\mathbf{A})$임을 보이자. 차원 정리에 의해 $nullity(\mathbf{P}\mathbf{A})=nullity(\mathbf{A})$임을 보이면 된다. 이는 $\mathbf{P}\mathbf{A}, \mathbf{A}$의 null space이 같을 경우 성립할 수 있다. 먼저, $\mathbf{v} \in ker(\mathbf{P}\mathbf{A}) \rightarrow \mathbf{P}\mathbf{A}\mathbf{v}=0 \rightarrow \mathbf{A}\mathbf{v}=\mathbf{A^{-1}} \cdot 0 \rightarrow \mathbf{A}\mathbf{v}= 0$ 이므로 $\mathbf{v} \in ker(\mathbf{A})$ 이며, $\mathbf{v} \in ker(\mathbf{A}) \rightarrow \mathbf{A}\mathbf{v}=0 \rightarrow \mathbf{P}\mathbf{A}\mathbf{v}=\mathbf{P} \cdot 0 \rightarrow \mathbf{P}\mathbf{A}\mathbf{v}= 0$ 이므로 $\mathbf{v} \in ker(\mathbf{P}\mathbf{A})$ 이다. 따라서 $\mathbf{P}\mathbf{A}, \mathbf{A}$의 null space이 같고, $nullity(\mathbf{P}\mathbf{A})=nullity(\mathbf{A})$이므로, 어떤 가역행렬 $\mathbf{P}$에 대해 $rank(\mathbf{P}\mathbf{A})=rank(\mathbf{A})$이다.

같은 방법으로 $rank(\mathbf{A}\mathbf{P})=rank(\mathbf{A})$을 보일 수 있으며, 이 보조정리를 이용하여 1번 성질을 다음과 같이 구할 수 있다.

---

2번 성질은 1번 성질이 성립할 경우 차원정리에 의해 쉽게 도출이 가능하다.

---

3번 성질은 고유값을 구하는 특성방정식에서 유도할 수 있다.

---

이제 닮음 변환을 이용하여 행렬 $\mathbf{A}$를 대각화해보자. 목표는 $\mathbf{P^{-1}}\mathbf{A}\mathbf{P}=\Lambda$인 대칭행렬 $\Lambda$과 가역행렬 $\mathbf{P}$를 찾는 것이다. $\mathbf{P^{-1}}\mathbf{A}\mathbf{P}=\Lambda$일 경우, $\mathbf{A}\mathbf{P}=\mathbf{P}\Lambda$이며, 이를 풀어쓰면 다음과 같다.

위의 식은 고유값, 고유벡터의 정의와 같으며, 따라서 우리는 고유값을 대각 성분으로 하는 대각행렬 $\Lambda$와 그에 해당하는 고유벡터로 이루어진 가역행렬 $\mathbf{P}$로 대각화를 할 수 있다. 이때 고유값을 이용하므로 행렬 $\mathbf{A}$는 $n \times n$의 정방행렬이어야 한다. 고윳값 분해를 위해 주어진 행렬은 정방행렬이어야 하며, 고유값이 $n$개 존재해야 한다.

특히 $\mathbf{P}$가 $\mathbf{P^T}=\mathbf{P^{-1}}$인 직교행렬이라면 $\mathbf{P^{-1}}\mathbf{A}\mathbf{P}=\mathbf{P^T}\mathbf{A}\mathbf{P}=\Lambda$이고, 이를 직교대각화라고 한다. 이때, $\mathbf{A}$가 실수로 이루어진 대칭행렬인 것과 $\mathbf{A}$가 대칭대각화 가능인 것은 동치이다. 그 증명은 다음과 같다.

---

1. $\mathbf{A}$가 대칭대각화 가능이면, $\mathbf{A}$는 대칭행렬

   $\mathbf{P^T}\mathbf{A}\mathbf{P}=\Lambda$를 만족하는 행렬 $\mathbf{P}$가 존재하며, $\mathbf{A}=\mathbf{P}\Lambda\mathbf{P^T}$이다($\mathbf{P^T}=\mathbf{P^{-1}}$). 따라서 $\mathbf{A^T}=(\mathbf{P}\Lambda\mathbf{P^T})^T=\mathbf{P}\Lambda\mathbf{P^T}=\mathbf{A}$ 이므로 $\mathbf{A}$는 대칭행렬이다($(\mathbf{A}\mathbf{B})^T=\mathbf{B}^T\mathbf{A}^T$).

---

2. $n \times n$행렬 $\mathbf{A}$가 실수로 이루어진 대칭행렬이면, $\mathbf{A}$는 대칭대각화 가능

• $n=1$인 경우, 위 명제가 성립 ($\mathbf{A}=[a], P=[1], \mathbf{P^T}\mathbf{A}\mathbf{P}=\Lambda$)

• $n=k$인 경우, 위 명제가 성립한다고 가정.

• $n=k+1$인 경우, 위 명제가 성립함을 보여 수학적 귀납법을 완성해보자.

  먼저, 실수로 이루어진 $n \times n$ 대칭행렬 $\mathbf{A}$가 주어질 경우, $\mathbf{A}$의 모든 고유값은 실수이다. 먼저, 행렬의 고유값을 구하는 특성방정식 $det(\lambda \mathbf{I}- \mathbf{A})=0$을 풀어보면 결국 n차 다항식이 나오고, 실수와 복소수를 포함하면 고유값은 언제나 n개가 존재한다. 이제 $\mathbf{A^*}, \mathbf{v^*}$를 행렬 또는 벡터 $\mathbf{A}, \mathbf{v}$의 켤레전치라고 하자(켤레: 복소수 $a \pm bi$의 켤래는 $a \mp bi$, 전치:transpose, 즉 켤레전치는 주어진 벡터 또는 행렬의 원소를 모두 켤레로 바꾸고 전치를 취한 것, $(\mathbf{A}\mathbf{B})^*=\mathbf{B}^*\mathbf{A}^*$, $(\mathbf{A_1}\cdots\mathbf{A_n})^*=\mathbf{A_n}^*\cdots\mathbf{A_1}^*, (c\mathbf{A})^* = \bar{c}\mathbf{A}^*$, $c$는 스칼라). 이때 $\mathbf{v}, \lambda$ 가 주어진 행렬 $\mathbf{A}$의 임의의 고유벡터, 고유값이라고 하면, $\mathbf{v^*}\mathbf{A}\mathbf{v}=\mathbf{v^*}\lambda\mathbf{v}=\lambda\mathbf{v^*}\mathbf{v}$ 이다. 여기서 $\mathbf{v^*}\mathbf{v}$는 $1 \times 1$이 되어 $\mathbf{d}\mathbf{I_{1 \times 1}}$로 쓸 수 있는데 서로 켤레관계인 복소수를 곱하면 양수인 실수가 되므로, $\mathbf{d}$는 양수인 실수이다. 따라서 $\mathbf{v^*}\mathbf{A}\mathbf{v}=\lambda\mathbf{d}\mathbf{I_{1 \times 1}} \rightarrow \frac{1}{\mathbf{d}}\mathbf{v^*}\mathbf{A}\mathbf{v}=\lambda\mathbf{I_{1 \times 1}}$ 이며, 양변의 켤레전치를 구하면 $(\frac{1}{\mathbf{d}}\mathbf{v^*}\mathbf{A}\mathbf{v})^*=(\lambda\mathbf{I_{1 \times 1}})^* \rightarrow \frac{1}{\mathbf{d}}\mathbf{v^*}\mathbf{A}\mathbf{v}=\bar{\lambda}\mathbf{I_{1 \times 1}}$ 이다(실수의 켤레는 자기 자신과 같음, $\mathbf{A}$는 실수로 이루어진 대칭행렬). 이는 고유값 $\lambda$의 결레는 자기자신과 같음을 의미하며, 따라서 실수로 이루어진 $n \times n$ 대칭행렬 $\mathbf{A}$의 고유값 $\lambda$는 실수이다.

  이제 실수로 이루어진 $n \times n$ 대칭행렬 $\mathbf{A}$에서 실수 고유값 $\lambda_1, \cdots, \lambda_n$을 구할 수 있으며, 이에 대한 고유벡터 $\mathbf{v_1}, \cdots, \mathbf{v_n}$을 구할 수 있고, 그람-슈미트 방법 등을 통해 정규직교기저화 할 수 있다. 이렇게 얻은 정규직교기저들 $\mathbf{v_1}, \cdots, \mathbf{v_n}$을 이용하여 행렬 $\mathbf{U}$를 만들면 다음과 같다.

  $\begin{aligned} \mathbf{U}^T\mathbf{A}\mathbf{U} & = \mathbf{U}^T\mathbf{A} \left( \begin{array}{c|c} \mathbf{v_1} & \mathbf{v_2} & \cdots & \mathbf{v_n}\\ \end{array} \right) \;\;\;\;\;\;\; \cdots \;\;블록행렬 \\ & = \mathbf{U}^T\mathbf{A} \left( \begin{array}{c|c} \mathbf{v_1} & \mathbf{v'} \\ \end{array} \right) \\ & = \mathbf{U}^T \left( \begin{array}{c|c} \mathbf{A}\mathbf{v_1} & \mathbf{A}\mathbf{v'} \\ \end{array} \right) \\ & = \mathbf{U}^T \left( \begin{array}{c|c} \lambda_1\mathbf{v_1} & \mathbf{A}\mathbf{v'} \\ \end{array} \right) \\ & = \begin{pmatrix} \mathbf{v_1}^T\\ \hline \mathbf{v'}^T \end{pmatrix} \left( \begin{array}{c|c} \lambda_1\mathbf{v_1} & \mathbf{A}\mathbf{v'} \\ \end{array} \right) \\ & = \left( \begin{array}{c|c} \lambda_1\mathbf{v_1}^T\mathbf{v_1} & \mathbf{v_1}^T\mathbf{A}\mathbf{v'} \\ \hline \lambda_1\mathbf{v'}^T\mathbf{v_1} & \mathbf{v'}^T\mathbf{A}\mathbf{v'} \end{array} \right) \\ & = \left( \begin{array}{c|c} \lambda_1 & 0 \\ \hline 0 & \mathbf{v'}^T\mathbf{A}\mathbf{v'} \end{array} \right) \\ & = \left( \begin{array}{c|c} \lambda_1 & 0 \\ \hline 0 & \mathbf{B} \end{array} \right) \end{aligned}$

  이때, 마지막 단계에서 $\mathbf{v_i}$들은 서로 정규직교하기 때문에 $\mathbf{v_1}^T\mathbf{v_1}=1$이며, $\mathbf{v'}^T\mathbf{v_1}=0$ ($\mathbf{v'}$에는 $\mathbf{v_1}$가 없기 때문), $\mathbf{U}^T\mathbf{A}\mathbf{U}$는 $(\mathbf{U}^T\mathbf{A}\mathbf{U})^T=\mathbf{U}^T\mathbf{A}\mathbf{U}$인 대칭행렬이므로 대칭성을 보이기 위해 오른쪽 위의 $\mathbf{v_1}^T\mathbf{A}\mathbf{v'}$ 또한 0이다.

  또한 $\mathbf{U}^T\mathbf{A}\mathbf{U}$는 대칭행렬이므로 오른쪽 아래의 $\mathbf{B}$ 또한 대칭행렬이며, 위에서 $n=k$인 경우, 명제가 성립한다고 가정하였으므로 $\mathbf{Q}^T\mathbf{B}\mathbf{Q}=\mathbf{\Lambda_B}$와 같이 대칭대각화가 가능하다. 이를 이용하여 다음과 같이 생각하면 $n=k+1$인 경우에도 대칭대각화가 가능함을 보일 수 있어 수학적 귀납법에 의해 위 명제는 성립한다.

  $\begin{aligned} \left( \begin{array}{c|c} 1 & 0 \\ \hline 0 & \mathbf{Q}^T \end{array} \right) \left( \begin{array}{c|c} \lambda_1 & 0 \\ \hline 0 & \mathbf{B} \end{array} \right) \left( \begin{array}{c|c} 1 & 0 \\ \hline 0 & \mathbf{Q} \end{array} \right) & = \left( \begin{array}{c|c} \lambda_1 & 0 \\ \hline 0 & \mathbf{Q}^T\mathbf{B}\mathbf{Q} \end{array} \right) \\ & = \left( \begin{array}{c|c} \lambda_1 & 0 \\ \hline 0 & \mathbf{\Lambda_B} \end{array} \right) \;\;\;\;\;\;\;\; \cdots \;\;대각행렬\\ & = \left( \begin{array}{c|c} 1 & 0 \\ \hline 0 & \mathbf{Q}^T \end{array} \right) \mathbf{P}^T\mathbf{A}\mathbf{P} \left( \begin{array}{c|c} 1 & 0 \\ \hline 0 & \mathbf{Q} \end{array} \right) \\ & = \mathbf{T}^T\mathbf{U}^T\mathbf{A}\mathbf{U}\mathbf{T} \\ & = \mathbf{P}^T\mathbf{A}\mathbf{P} \\ & = \mathbf{\Lambda} \end{aligned}$

  여기서 $\mathbf{T}, \mathbf{U}$는 둘 다 직교 행렬이므로 $\mathbf{T}^T\mathbf{U}^T, \mathbf{U}\mathbf{T}$또한 직교이며, $\mathbf{U}\mathbf{T}=\mathbf{P}\;\;(\mathbf{T}^T\mathbf{U}^T=\mathbf{P}^T)$라고 쓰면 $\mathbf{P}^T\mathbf{A}\mathbf{P}= \mathbf{\Lambda}$라고 할 수 있다.

  따라서 실수로 이루어진 $n \times n$행렬 $\mathbf{A}$는 직교 대각화가 가능하다.

---

우리는 실수로 이루어진 $n \times n$ 대칭행렬 $\mathbf{A}$에서 실수 고유값 $\lambda_1, \cdots, \lambda_n$을 구할 수 있으며, 이에 대한 고유벡 $\mathbf{v_1}, \cdots, \mathbf{v_n}$을 구할 수 있고, 그람-슈미트 방법 등을 통해 정규직교기저화 할 수 있다. 이렇게 얻은 정규직교기저들 $\mathbf{v_1}, \cdots, \mathbf{v_n}$을 이용하여 행렬 $\mathbf{P}$를 만들 수 있고, 우리는 위에서 고유값과 고유벡터를 통해 $\mathbf{P^{-1}}\mathbf{A}\mathbf{P}=\Lambda$같이 대각화 할 수 있음을 보였다. 다만 여기서 만든 행렬 $\mathbf{P}$는 정규직교기저들로 이루어져 있으므로 $\mathbf{P}$는 직교행렬이고 $\mathbf{P^{-1}}\mathbf{A}\mathbf{P}=\mathbf{P}^T\mathbf{A}\mathbf{P}=\Lambda$ 이며, 직교대각화 역시 고유값과 고유벡터의 정규직교기저들로 수행할 수 있다.

특히 $\mathbf{P}^T\mathbf{A}\mathbf{P}=\Lambda \rightarrow \mathbf{A}=\mathbf{P}\Lambda\mathbf{P}^T$를 풀어쓰면 다음과 같다.

만약 고유값 $\lambda_i$를 크기 순으로 정렬할 수 있다면 작은 고유값에 해당하는 term은 0으로 무시할 수 있고($\mathbf{v_i}$ 또한 크기가 1인 벡터이므로 원소들이 그리 크지 않음), 이를 통해 행렬 $\mathbf{A}$를 압축할 수 있다.

2. 특이값 분해

위에서 고유값 분해를 통해 행렬 $\mathbf{A}$를 $\mathbf{A}=\mathbf{P}\mathbf{\Lambda}\mathbf{P}^{-1}$와 같이 대각행렬을 포함한 행렬들의 곱으로 분해할 수 있었으며, 특히 대각행렬 $\mathbf{\Lambda}$의 대각 성분은 $\mathbf{A}$의 고유값들, 행렬 $\mathbf{P}$의 열백터들은 각 고유값에 해당하는 고유벡터들이었다. 하지만 이러한 고유값 분해는 $\mathbf{A}$의 고유값을 사용해야하기 때문에 $\mathbf{A}$가 정방행렬이어야 한다거나, 혹은 직교대각화를 위해 대칭행렬이어야 한다라는 조건이 붙는다. 특이값 분해(SVD, Singular Value Decomposition)는 이러한 조건 없이 임의의 $m \times n$ 행렬 $\mathbf{A}$를 다음과 같이 분해하는 방법이다.

이때, $\mathbf{A}$는 임의의 $m \times n$ 행렬, $\mathbf{U}$는 $m \times m$의 직교행렬, $\mathbf{V}$는 $n \times n$의 직교행렬, $\mathbf{\Sigma}$는 $m \times n$의 대각행렬이다. 특이값 분해에서도 각 행렬의 구성은 고유값, 고유벡터들과 깊은 연관이 있다. $\mathbf{V}^T$는 $n \times n$의 직교행렬이므로 $\mathbf{A} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^T \rightarrow \mathbf{A}\mathbf{V} = \mathbf{U}\mathbf{\Sigma}$로 쓸 수 있다. 이제 이러한 식을 만족하는 행렬 $\mathbf{U},\mathbf{\Sigma},\mathbf{V}$를 찾을 것이다.

먼저, $\mathbf{A}^T\mathbf{A}$를 생각해보면, $(\mathbf{A}^T\mathbf{A})^T=\mathbf{A}^T\mathbf{A}$이므로 대칭행렬임을 알 수 있다. 따라서 위에서 보았듯이 $\mathbf{A}^T\mathbf{A}=\mathbf{V}\mathbf{D}\mathbf{V}^T$와 같이 직교 대각화가 가능하다. $\mathbf{A}^T\mathbf{A}$의 각 고유값 $\lambda_i$에 대해서 $\mid \mathbf{A}\mathbf{x} \mid ^2 = \mathbf{A}\mathbf{x} \cdot \mathbf{A}\mathbf{x} = \mathbf{x}\cdot\mathbf{A}^T\mathbf{A}\mathbf{x}= \mathbf{x}\cdot\lambda_i\mathbf{x}=\lambda_i(\mathbf{x} \cdot \mathbf{x})=\lambda_i\mid \mathbf{x} \mid ^2$이며, 양변이 양수가 되어야 하므로 고유값 $\lambda_i$는 양수가 되어야 한다 (대칭행렬의 고유값이므로 실수이다).

그리고 $rank(\mathbf{A}^T\mathbf{A})=rank(\mathbf{A})$인데, $null(\mathbf{A}^T\mathbf{A}) \sube null(\mathbf{A}), null(\mathbf{A}) \sube null(\mathbf{A}^T\mathbf{A})$ 각각을 보이면 $\mathbf{A}^T\mathbf{A}, \mathbf{A}$의 null space가 동일함을 보일 수 있고, 차원 정리에 의해 $rank(\mathbf{A}^T\mathbf{A})=rank(\mathbf{A})$가 성립한다. 어떤 벡터 $\mathbf{x} \in null(\mathbf{A})$에 대해 $\mathbf{A}^T\mathbf{A}\mathbf{x}=\mathbf{A}^T\mathbf{0}=\mathbf{0}$이므로 $null(\mathbf{A}^T\mathbf{A}) \sube null(\mathbf{A})$이고, $\mathbf{x} \in null(\mathbf{A}^T\mathbf{A})$에 대해 $\mathbf{A}^T\mathbf{A}\mathbf{x}=\mathbf{0} \rightarrow \mathbf{x} \cdot\mathbf{A}^T\mathbf{A}\mathbf{x}=\mathbf{0} \rightarrow \mathbf{A}\mathbf{x} \cdot \mathbf{A}\mathbf{x}=\mathbf{0} \rightarrow \mid \mathbf{A}\mathbf{x} \mid ^2 =\mathbf{0}$이므로 $null(\mathbf{A}) \sube null(\mathbf{A}^T\mathbf{A})$이다.

따라서 다음과 같이 쓸 수 있다.

위에서 보였던 고유값 $\lambda_i$는 양수가 되어야 한다는 점에서 대각행렬 $\mathbf{D}$의 고유값은 $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq 0$이며(큰 순으로 정렬이 가능하다), $rank(\mathbf{D})=k$라는 점에서 $\lambda_{k+1}, \cdots, \lambda_{n}=0$이 되어야 한다($rank(\mathbf{D})=k$이면 $\mathbf{D}$ 열백터 중 $k$개만 선형독립이어야 하며, $\mathbf{D}$는 대각행렬임).

행렬 $\mathbf{V}$은 $(\mathbf{v_1}, \cdots, \mathbf{v_n})$이며, 0이 아닌 고유값에 대한 단위고유벡터들은 $(\mathbf{v_1}, \cdots, \mathbf{v_k})$로 쓸 수 있다. 이때, $\mathbf{V}$는 $\mathbf{A}^T\mathbf{A}$를 직교대각화 한 것으로 각 $\mathbf{v_i}$는 서로 직교하며, $\mathbf{A}\mathbf{v_i} \cdot \mathbf{A}\mathbf{v_j}=\mathbf{v_i} \cdot \mathbf{A}^T\mathbf{A}\mathbf{v_j}=\mathbf{v_i} \cdot \lambda_j\mathbf{v_j} =\lambda_j(\mathbf{v_i} \cdot \mathbf{v_j})=0$이 되어 $\mathbf{A}\mathbf{v_i}$들도 서로 직교한다. 또한 $\mid \mathbf{A}\mathbf{v_i} \mid^2=\mathbf{A}\mathbf{v_i} \cdot \mathbf{A}\mathbf{v_i} = \lambda_i(\mathbf{v_i} \cdot \mathbf{v_i})=\lambda_i \rightarrow \mid \mathbf{A}\mathbf{v_i} \mid =\sqrt{\lambda_i}$이고(고유값들은 실수이며 양수), 이를 이용하면 $(\frac{1}{\sqrt{\lambda_1}}\mathbf{A}\mathbf{v_1}, \cdots, \frac{1}{\sqrt{\lambda_k}}\mathbf{A}\mathbf{v_k})=(\mathbf{u_1}, \cdots, \mathbf{u_k})$와 같은 새로운 정규직교기저들을 구성할 수 있다. 이들이 SVD 결과 식에 나오는 행렬 $\mathbf{U}$를 구성하는 벡터들이 되는데, $\mathbf{U}$는 $m \times m$행렬이므로 $m-k$개의 벡터가 부족하지만 $\mathbf{u_1}, \cdots, \mathbf{u_k}$로부터 $m-k$개의 정규직교기저를 생성하는 방법이 존재한다.

예를들어 $\mathbf{u_1}^T, \cdots, \mathbf{u_k}^T$들을 행벡터로 하는 행렬 $\mathbf{B}$를 만들면 이는 $k \times m$ 행렬이고, 차원정리에 의해 $rank(\mathbf{B})+nullity(\mathbf{B})=m$이다. 이때, $rank(\mathbf{B})=dim(row(\mathbf{B}))=k$이며, $nullity(\mathbf{B})=m-k$이므로 행렬 $\mathbf{B}$의 null space는 $m-k$개의 기저를 포함하고 있음을 알 수 있다. $\mathbf{B}$의 null space는 $\mathbf{B}\mathbf{x}=\mathbf{0}$의 해가 이루는 공간이며, $\mathbf{B}\mathbf{x}=(\mathbf{u_1} \cdot \mathbf{x}, \cdots, \mathbf{u_k} \cdot \mathbf{x})^T=\mathbf{0}$이므로 $\mathbf{x}$들이 $\mathbf{u_1}, \cdots, \mathbf{u_k}$들과 직교함을 알 수 있다. 따라서 $null(\mathbf{B})$의 단위기저벡터 $\mathbf{w}_1, \cdots \mathbf{w}_{m-k}$를 구함으로써, $\mathbf{u_1}, \cdots, \mathbf{u_k}, \mathbf{w}_1, \cdots \mathbf{w}_{m-k}$와 같이 총 $m$개의 정규직교기저를 생성할 수 있다.

이렇게 생성한 정규직교기저 $\mathbf{u_1}, \cdots, \mathbf{u_k}, \mathbf{w}_1, \cdots \mathbf{w}_{m-k}$를 이용하여 행렬 $\mathbf{U}$를 구성하고 다음과 같은 행렬 $\mathbf{\Sigma}$를 생각해보자.

행렬 $\mathbf{\Sigma}$는 대각성분이 $\mathbf{A}^T\mathbf{A}$의 고유값의 제곱근 및 0으로 이루어진 대각행렬이며, 결과적으로 $\mathbf{U}\mathbf{\Sigma} = \mathbf{A}\mathbf{V} \rightarrow \mathbf{U}\mathbf{\Sigma}\mathbf{V}^T = \mathbf{A}$가 되어 SVD가 수행된다. 여기서 $\sqrt{\lambda_i}=\sigma_i$라고 쓰며 이 값들을 특이값이라고 하고, 그에 대응되는 $\mathbf{U},\mathbf{V}^T$의 벡터들, $\mathbf{u_1}, \cdots, \mathbf{u_k}$ 및 $\mathbf{v_1}^T, \cdots, \mathbf{v_k}^T$ 들을 왼쪽, 오른쪽 특이벡터라고 한다.

또한 위의 전개에서 $\mathbf{w}_1, \cdots \mathbf{w}_{m-k}$ 및 $\mathbf{v}_{k+1}, \cdots \mathbf{v}_{n}$은 0과 곱해져 사라지므로 다음과 같이 $m \times k$의 직교행렬 $\mathbf{U'}$, $k \times n$의 직교행렬 $\mathbf{V'}^T$, $k \times k$의 대각행렬 $\mathbf{\Sigma'}$로 다음과 같이 축소된 SVD 또한 가능하다.

여기서 고유값분해에서와 마찬가지로 작은 고유값에 해당하는 term을 0으로 두어 데이터 압축에도 활용할 수 있다.

3. 특이값 분해의 활용

3.1. 최소제곱법

특이값 분해는 임의의 임의의 $m \times n$ 행렬 $\mathbf{A}$를 $\mathbf{A} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^T = \mathbf{U'}\mathbf{\Sigma'}\mathbf{V'}^T$와 같이 분해할 수 있다는 점에서 다양한 활용성을 갖는다. 특히 $\mid \mathbf{A}\mathbf{x}-\mathbf{b} \mid$가 최소가 되는 $\mathbf{x}$를 찾는 최소제곱문제에도 적용 가능하다.

$\mathbf{A}$가 가역행렬일 경우 $\mathbf{A}^{-1}=(\mathbf{U'}\mathbf{\Sigma'}\mathbf{V'}^T)^{-1}=\mathbf{V'}\mathbf{\Sigma'}^{-1}\mathbf{U'}^T$으로 최소제곱문제가 쉽게 해결된다. 가역행렬이 아닐 경우 $\mathbf{V'}\mathbf{\Sigma'}^{-1}\mathbf{U'}^T$가 $\mathbf{A}$의 역행렬은 아니지만 여전히 최소제곱문제의 해를 도출하는데, $\mathbf{V'}\mathbf{\Sigma'}^{-1}\mathbf{U'}^T$를 $\mathbf{A}$의 유사역행렬(pseudo inverse)라고 한다.

이제 $\mathbf{V'}\mathbf{\Sigma'}^{-1}\mathbf{U'}^T$가 정말 최소제곱문제의 해를 도출하는지 살펴보자. 예상되는 최소제곱문제의 해는 $\mathbf{\hat{x}}=\mathbf{V'}\mathbf{\Sigma'}^{-1}\mathbf{U'}^T\mathbf{b}$이다.

위의 식은 QR decomposition에서 최소제곱문제가 해결됨을 보이기 위해 전개했던 식과 유사하다. $\mathbf{U'}\mathbf{U'}^T\mathbf{b}$는 QR decomposition에서 설명했듯이 column space $Col(\mathbf{U'})$로의 $\mathbf{b}$의 투영 $\mathbf{b}^{\parallel Col(\mathbf{U'})}$이며, $Col(\mathbf{U'})=Col(\mathbf{A})$이므로 $\mathbf{U'}\mathbf{U'}^T\mathbf{b}=\mathbf{b}^{\parallel Col(\mathbf{U'})}=\mathbf{b}^{\parallel Col(\mathbf{A}) }$이 되어 계산된 벡터 $\mathbf{\hat{x}}$가 주어진 최소제곱문제의 최적해가 된다 ($Col(\mathbf{A})$가 곧 $\mathbf{A}\mathbf{x}$의 공간이다).

여기서 $Col(\mathbf{U'})=Col(\mathbf{A})$인 것과 더불어 $Row(\mathbf{V'^T})=Row(\mathbf{A})$인데, 이는 SVD 정의 식을 전개함으로써 도출이 가능하다.

$rank(\mathbf{A}) = dim(Row(\mathbf{A}))$인데, 위 전개에서 행렬 $\mathbf{A}$의 행들은 $\mathbf{v_1}^T, \cdots, \mathbf{v_k}^T$의 선형결합으로 이루어져 있으므로 $Row(\mathbf{A}) \sube Row(\mathbf{V'^T})$라고 할 수 있다. 그런데 $rank(\mathbf{A}^T\mathbf{A})=rank(\mathbf{A})=k$이고, $\mathbf{v_1}^T, \cdots, \mathbf{v_k}^T$ 각각은 선형독립이므로, $rank(\mathbf{V'^T})=dim(Row(\mathbf{V'^T}))=k$이다. 따라서 $Row(\mathbf{A}) \sube Row(\mathbf{V'^T}), \; dim(Row(\mathbf{A})) = dim(Row(\mathbf{V'^T}))$가 되어 $Row(\mathbf{A})=Row(\mathbf{V'^T})$이다. 이와 비슷하게 행렬 $\mathbf{A}$의 열들은 행들은 $\mathbf{u_1}, \cdots, \mathbf{u_k}$의 선형결합으로 이루어져 있으므로 $Col(\mathbf{U'})=Col(\mathbf{A})$이다.

위에서는 $\mid \mathbf{A}\mathbf{x}-\mathbf{b} \mid$를 최소로 만드는 최소제곱법을 살펴보았지만, 사실 $\mathbf{A}\mathbf{x}=\mathbf{0}$이라는 문제를 해결하기 위해 $\mid \mathbf{A}\mathbf{x} \mid$를 최소로 만드는 최소제곱법 또한 많이 활용된다(물론 영벡터라는 자명한 해를 구하고자 함은 아니기 때문에 보통 $\mid \mathbf{x} \mid=1$라는 제약조건이 붙음). 만약 $\mathbf{A}$에 어떤 오른쪽 특이벡터를 곱한다면, $\mathbf{V}$는 직교행렬이므로 $\mathbf{A}\mathbf{v_i}=\mathbf{\sigma_i}\mathbf{u_i}$의 형태가 된다. 이때, 0인 특이값이 있다면 $\mathbf{A}\mathbf{x}=\mathbf{0}$를 만족하는 정확한 해를 찾을 수 있고, 만약 0인 특이값이 없어 정확한 해를 찾을 수 없다면 최소의 특이값에 대응되는 오른쪽 특이벡터가 $\mid \mathbf{A}\mathbf{x} \mid$를 최소로 만드는 해이다. 이에 대한 증명은 아래에서 소개한다(아래에서 기술될 내용을 이용하면 쉽게 파생되어 이 글에서는 아래 내용을 이용하지만, 이 최소제곱법 해만을 증명하려고 한다면 굳이 아래와 같이 복잡하게 할 필요는 없음).

3.2. Rank-r 근사

SVD를 통해 찾아낸 특이값과 특이벡터 들을 활용하면 어떤 행렬 $\mathbf{A}$에 대한 Rank-$r$ 근사 ($r \leq k,\;\; rank(\mathbf{A})=k$)를 찾을 수 있다. 이는 주어진 행렬 $\mathbf{A}$의 rank보다 작은 rank를 가지는 행렬 $\mathbf{A'}$로 $\mathbf{A}$를 근사하는 것이며, 근사는 $\mathbf{A'}$와 $\mathbf{A}$ 사이의 차이에 대한 norm을 최소로 한다는 것을 의미한다. 어떤 행렬에 대한 norm $\left| \mathbf{A} \right|$를 정의하는 방법은 여러가지가 있지만 여기서는 다음과 같은 Frobenius norm을 사용한다.

이때, $A_{ij}$는 행렬 $\mathbf{A}$의 성분들이다. 원래의 rank보다 작은 rank로 근사할 경우 행렬의 크기를 줄일 수 있고, 주요 성분 만이 남아 행렬의 분석에도 도움이 될 수 있다. 예를 들어 rank가 1인 행렬의 경우 $m \times n$ 크기의 행렬을 벡터곱 $\mathbf{u}\mathbf{v}^T$($\mathbf{u}$: 길이 $m$, $\mathbf{v}$: 길이 $n$)으로 표현이 가능하며, 이때 사용되는 원소는 $m+n$개뿐이다.

$\mathbf{A'}$을 $\mathbf{A}$에 대한 최적의 Rank-$r$ 근사 ($r \leq k,\;\; rank(\mathbf{A})=k$)라고 해보자. 이는 $\left| \mathbf{A}- \mathbf{A'} \right|_F^2$가 최소가 됨을 의미하며, 위의 norm의 정의에 의해 $\left| \mathbf{A}- \mathbf{A'} \right|_F^2=$($\mathbf{A}- \mathbf{A'}$의 첫번째 행벡터) + ... + ($\mathbf{A}- \mathbf{A'}$의 m번째 행벡터) 이다. Rank-$r$ 행렬 $\mathbf{A'}$가 포함하는 $r$개의 기저는 어떠한 공간 $V$를 생성하며, $\mathbf{A'}$의 행은 공간 $V$에 포함되어 있다. 따라서 $\left| \mathbf{A}- \mathbf{A'} \right|_F^2$를 최소로 하기 위해서 $\mathbf{A'}$의 행벡터들은 다음과 같이 결정되어야 한다.

이때 어떤 벡터 $\mathbf{a}$는 어떤 공간 $V$에 대해 $\mathbf{a}=\mathbf{a}^{\perp V}+\mathbf{a}^{\parallel V}$와 같이 표현될 수 있고, 공간 $V$에서 $\mathbf{a}$에 가장 가까운 벡터는 $\mathbf{a}^{\parallel V}$, 공간 $V$과 벡터 $\mathbf{a}$ 사이의 거리는 $\left| \mathbf{a}^{\perp V} \right|$이다. 따라서 $\left| \mathbf{A}- \mathbf{A'} \right|_F^2=$($\mathbf{a_1}$에서 공간 $V$ 사이의 거리)$^2$+ ... + ($\mathbf{a_m}$에서 공간 $V$ 사이의 거리)$^2$이 된다.

따라서 주어진 $\left| \mathbf{A}- \mathbf{A'} \right|_F^2$는 $\mathbf{A}$의 각 행들에서 공간 $V$ 사이의 거리의 제곱의 합으로 주어지며, 이러한 공간 $V$는 $\mathbf{A}$로부터 계산되는 $r$개의 특이벡터들이 span하는 공간이다. 또한 $\left| \mathbf{A}- \mathbf{A'} \right|_F^2$는 특이벡터들에 대응되는 특이값을 이용하여 $\left| \mathbf{A}- \mathbf{A'} \right|_F^2=\left| \mathbf{A} \right|_F^2-\sigma_1-\cdots-\sigma_r$이다(아래에서 증명함).

$\mathbf{a_i}^{\parallel V}=\mathbf{a_i}^{\parallel \mathbf{v_1}}+\cdots+\mathbf{a_i}^{\parallel \mathbf{v_r}}=(\mathbf{a_i} \cdot \mathbf{v_1})\mathbf{v_1} + \cdots + (\mathbf{a_i} \cdot \mathbf{v_r})\mathbf{v_r}$로 쓸 수 있으며, 행렬 $\mathbf{A}$에 대한 Rank-$r$ 근사 $\mathbf{A'}$은 다음과 같이 쓸 수 있다.

즉, 행렬 $\mathbf{A}$에 대한 Rank-$r$ 근사는 행렬 $\mathbf{A}$의 SVD에서 일부의 특이값 및 특이벡터만 취한 것으로 볼 수 있으며, 앞에서 설명한 SVD 활용 데이터 압축과도 연관지어 생각할 수 있다.

위에서 $(\mathbf{a_i} \cdot \mathbf{v_i})\mathbf{v_i}^T$들로 표현된 행렬이 갑자기 $\sigma_i, \mathbf{u_i}$로 표현되었으나, 이는 SVD 유도과정에서 $\mathbf{U}\mathbf{\Sigma}=\mathbf{A}\mathbf{V}$ 를 전개해보면 알 수 있다.

---

이제 앞에서 생략한 증명을 살펴보자.

• 먼저 어떤 공간 $V$의 정규직교기저가 $\mathbf{v_1}, \cdots, \mathbf{v_r}$이고, $\mathbf{a_1}, \cdots, \mathbf{a_m}$이 행렬 $\mathbf{A}$의 행이라고 할 때, ($\mathbf{a_1}$에서 공간 $V$ 사이의 거리)$^2$+ ... + ($\mathbf{a_m}$에서 공간 $V$ 사이의 거리)$^2$=$\left| \mathbf{A} \right|_F^2- \left| \mathbf{A}\mathbf{v_1} \right|^2-\left| \mathbf{A}\mathbf{v_2} \right|^2-\cdots-\left| \mathbf{A}\mathbf{v_r} \right|^2$임을 보인다.

  $\mathbf{a_i}=\mathbf{a_i}^{\perp V}+\mathbf{a_i}^{\parallel V}$이며, 피타고라스 정리에 의해 $\left| \mathbf{a_i}^{\perp V} \right|^2 = \left| \mathbf{a_i} \right|^2-\left| \mathbf{a_i}^{\parallel V} \right|^2$이다. 따라서 구하고자 하는 $\mathbf{a_i}$ 부터 공간 $V$ 사이의 제곱 거리의 합은 다음과 같이 쓸 수 있다.

• 이제 $\mathbf{a_1}, \cdots, \mathbf{a_m}$이 행렬 $\mathbf{A}$의 행, $\mathbf{v_1}, \cdots, \mathbf{v_k}$ 및 $\sigma_1, \cdots, \sigma_k$가 행렬 $\mathbf{A}$의 오른쪽 특이벡터와 특이값이라고 할때, $r \leq k$인 $r$개의 특이벡터 $\mathbf{v_1}, \cdots, \mathbf{v_r}$가 span하는 공간 $V$가 ($\mathbf{a_1}$에서 공간 $V$ 사이의 거리)$^2$+ ... + ($\mathbf{a_m}$에서 공간 $V$ 사이의 거리)$^2$를 최소화하고, 그 최솟값은 $\left| \mathbf{A} \right|_F^2- \sigma_1^2-\sigma_2^2-\cdots-\sigma_r^2$임을 보인다.

  우선 앞에서 증명한 내용에 의해 공간 $V$에 대한 제곱거리 합은 다음과 같다.

  $\left| \mathbf{A} \right|_F^2- \sigma_1^2-\sigma_2^2-\cdots-\sigma_r^2$

  이는 $\mathbf{U}\mathbf{\Sigma}=\mathbf{A}\mathbf{V}$에서 알 수 있으며, 하나의 벡터성분만 보자면 $\sigma_i\mathbf{u_i}=\mathbf{A}\mathbf{v_i}$인데 양변을 제곱하며 크기를 구하면 $\mathbf{u_i}$는 단위벡터이므로 크기는 $\sigma_i^2$이 된다.

  이제 이 값이 최소임을 증명하기 위해 임의의 r차원 벡터 공간 $W=span(\mathbf{w_1}, \cdots, \mathbf{w_r)}$을 도입하여 $W$까지의 제곱거리합이 위의 값보다 작지 않다는 것을 보인다. $W$까지의 제곱거리합은 다음과 같다.

  $\left| \mathbf{A} \right|^2_F-\left| \mathbf{A}\mathbf{w_1} \right|^2-\cdots-\left| \mathbf{A}\mathbf{w_r} \right|^2 = \left| \mathbf{A} \right|^2_F- \left| \mathbf{A}\mathbf{W} \right|^2_F$

  따라서 $\left| \mathbf{A}\mathbf{W} \right|^2_F \leq \sigma_1^2+\sigma_2^2+\cdots+\sigma_r^2$ 임을 보여야한다. SVD에 의해 $\mathbf{A}=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^T$이며, $\mathbf{U},\mathbf{V}$ 는 직교행렬이므로 벡터를 곱했을때 norm을 보존한다. 즉, $\left| \mathbf{A}\mathbf{W} \right|^2_F=\left| \mathbf{U}\mathbf{\Sigma}\mathbf{V}^T\mathbf{W} \right|^2_F=\left| \mathbf{\Sigma}\mathbf{V}^T\mathbf{W} \right|^2_F$ 이다. 여기서 $\mathbf{V}^T\mathbf{W}=\mathbf{X}$라고 하자.

  $\mathbf{x_1}, \cdots, \mathbf{x_r}$이 행렬 $\mathbf{X}$의 열이라고 할 때, $\mathbf{x_i}=\mathbf{V}^T\mathbf{w_i}\rightarrow\mathbf{V}\mathbf{x_i}=\mathbf{V}\mathbf{V}^T\mathbf{w_i}$이며, QR decomposition에서 보았듯이 이는 $V$로의 투영 $\mathbf{w_i}^{\parallel V}$이다. 길이가 1인 단위행렬 $\mathbf{w_i}$를 투영한 것이므로 $|\mathbf{V}\mathbf{x_i}|^2\leq1$이고, $\mathbf{V}$는 직교행렬이므로 벡터를 곱했을때 norm을 보존하여 $|\mathbf{x_i}|^2\leq1$이다. 따라서 $\left| \mathbf{X} \right|^2_F\leq r$이다(행렬의 제곱크기는 열벡터들의 제곱크기의 합이므로).

  $\mathbf{y_1}, \cdots, \mathbf{y_k}$이 행렬 $\mathbf{X}$의 행이라고 하면 $\mathbf{y_i}=\mathbf{v_i}^T\mathbf{W}\rightarrow\mathbf{y_i}=\mathbf{W}^T\mathbf{v_i}$가 되어 동일한 과정으로 $|\mathbf{y_i}|^2\leq1$이다.

  $\left| \mathbf{\Sigma}\mathbf{X} \right|^2_F=\sigma_1^2|\mathbf{y_1}|^2+\cdots+\sigma_k^2|\mathbf{y_k}|^2$이고, $\left| \mathbf{X} \right|^2_F\leq r$이므로 $|\mathbf{y_1}|^2+\cdots+|\mathbf{y_k}|^2\leq r$이다. 따라서 다음과 같다($\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_k$).

  $\begin{aligned} \sigma_1^2|\mathbf{y_1}|^2+\cdots+\sigma_k^2|\mathbf{y_k}|^2 & \leq \sigma_1|^2\mathbf{y_1}|^2+\cdots+\sigma_r^2|\mathbf{y_r}|^2+\sigma_r^2|\mathbf{y_{r+1}}|^2+\cdots+ +\sigma_r^2|\mathbf{y_k}|^2 \\ & = ((\sigma_1^2-\sigma_r^2)|\mathbf{y_1}|^2+\cdots+(\sigma_r^2-\sigma_r^2)|\mathbf{y_r}|^2)+(\sigma_r^2|\mathbf{y_1}|^2+\cdots+\sigma_r^2|\mathbf{y_k}|^2)\\ & \leq ((\sigma_1^2-\sigma_r^2)+\cdots+(\sigma_r^2-\sigma_r^2))+\sigma_r^2(|\mathbf{y_1}|^2+\cdots+|\mathbf{y_k}|^2)\\ & \leq (\sigma_1^2+\cdots+\sigma_r^2-r\sigma_r^2)+\sigma_r^2r\\ & = \sigma_1^2+\cdots+\sigma_r^2 \end{aligned}$

  따라서 $\left| \mathbf{A}\mathbf{W} \right|^2_F=\left| \mathbf{U}\mathbf{\Sigma}\mathbf{V}^T\mathbf{W} \right|^2_F=\left| \mathbf{\Sigma}\mathbf{V}^T\mathbf{W} \right|^2_F=\left| \mathbf{\Sigma}\mathbf{X} \right|^2_F \leq \sigma_1^2+\cdots+\sigma_r^2$가 되어 증명이 완료된다.
  

---

이제 $\mid \mathbf{A}\mathbf{x} \mid$를 최소로 만드는 최소제곱문제의 최적해가 가장 작은 특이값에 대응되는 오른쪽 특이벡터라는 것을 증명해보자. 이를 위하여 임의의 벡터 $\mathbf{w}$에 대해서 $|\mathbf{A}\mathbf{w}| \leq |\mathbf{A}\mathbf{v_k}| \leq \mathbf{\sigma_k}$가 만족함을 보여야 한다. 이는 $\mathbf{W}$를 생성할 때 한 개의 임의의 벡터만 사용되었다고 생각하고 위 과정을 진행한 뒤에, 위 부등식에서 다음과 같이 전개하여 증명할 수 있다.

따라서 $\left| \mathbf{A}\mathbf{W} \right|^2_F=\left| \mathbf{U}\mathbf{\Sigma}\mathbf{V}^T\mathbf{W} \right|^2_F=\left| \mathbf{\Sigma}\mathbf{V}^T\mathbf{W} \right|^2_F=\left| \mathbf{\Sigma}\mathbf{X} \right|^2_F =\sigma_1^2|\mathbf{y_1}|^2+\cdots+\sigma_k^2|\mathbf{y_k}|^2 \geq \sigma_k^2$이고, 양변에 루트를 취하면 $\left| \mathbf{A}\mathbf{W} \right|_F \geq \sigma_k$가 되어 가장 작은 특이값에 대응되는 오른쪽 특이벡터를 $\mathbf{A}$에 곱했을 때, 임의의 벡터 $\mathbf{w}$를 곱했을 때보다 작거나 같은 값을 얻을 수 있음을 알 수 있다.