행렬의 특이값 분해
개요
늘 고유값 대각화를 통해 행렬을 쪼갤 수 있다면 좋겠지만, 이 방법엔 아쉽게도 주어지는 행렬이 정방행렬이어야한다는 제한이 있다. 이에 대각화할 행렬을 정방행렬이 아닌 경우로 확장해서 분해하려고 한다.
빌드업
두 자연수 $m > n$ 에 대해 행렬 $A \in \mathbb{C}^{ m \times n}$ 의 계수가 $\text{rank} A = n$ 으로 주어진다고 하자. 그러면 $\dim C(A) = \dim C(A^{T}) = n $ 으로, 이들의 정규직교벡터 $\mathbb{v}_{1} , \cdots , \mathbb{v}_{n} \in C(A)$ 과 $\mathbb{u}_{1} , \cdots , \mathbb{u}_{n} \in C(A^{T})$ 을 생각할 수 있다.
고유값의 기하학적인 의미를 생각할 때와 마찬가지로 $$ A \mathbb{v}_{i} = \sigma_{i} \mathbb{u}_{i} $$ 를 만족하는 $\sigma_{i}>0$ 가 존재한다고 가정하자. 그러면 $A$ 는 $\mathbb{v}_{i}$ 의 방향을 $\mathbb{u}_{i}$ 와 일치하도록 만드는 선형변환이고 $\sigma_{i}>0$ 는 그 크기를 맞춰주는 것으로 볼 수 있다. 이러한 $\sigma_{i}$ 는 고유값이 아니라 $A$ 의 특이값이라 정의하는데, 아쉽게도 그 의미는 특이값 분해와 전혀 상관이 없다. 여기서 고유값에서의 논의와 달라지는 것은 $A \in \mathbb{C}^{ m \times n}$, 즉 $\mathbb{v}_{i} \in \mathbb{C}^{n}$ 이고 $\mathbb{u}_{i} \in \mathbb{C}^{m}$ 이므로 $A$ 가 벡터의 차원도 바꾼다는 것이다. 행렬 $A$ 에 대해 정리해서 $A = \sigma_{i} \mathbb{u}_{i} \mathbb{v}_{i}^{\ast}$ 이고 양변의 차원은 $m \times n = ( m \times 1 ) \times (1 \times n )$ 이 됨을 확인해보자. 한편 고유벡터와 달리 좌우가 구분이 되므로 $\mathbb{u}_{i}$ 는 좌특이벡터 , $\mathbb{v}_{i}$ 가 우특이벡터 로 정의된다는 것에 유의하자.이제 $A \mathbb{v}_{i} = \sigma_{i} \mathbb{u}_{i}$ 을 $1 \le i \le n$ 에 대해 풀어서 쓰면 $$ A \begin{bmatrix} \mathbb{v}_{1} & \mathbb{v}_{2} & \cdots & \mathbb{v}_{n} \end{bmatrix} = \begin{bmatrix} \mathbb{u}_{1} & \mathbb{u}_{2} & \cdots & \mathbb{u}_{n} \end{bmatrix} \begin{bmatrix} \sigma_{1} & 0 & \cdots & 0 \\ 0 & \sigma_2 & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & \sigma_{m} \end{bmatrix} $$ 간결한 표현을 위해서 아래와 같이 나타내도록 하자. $$ V := \begin{bmatrix} \mathbb{v}_{1} & \mathbb{v}_{2} & \cdots & \mathbb{v}_{n} \end{bmatrix} \in \mathbb{C}^{n \times n} \\ \widehat{U} := \begin{bmatrix} \mathbb{u}_{1} & \mathbb{u}_{2} & \cdots & \mathbb{u}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n} \\ \widehat{\Sigma} := \text{diag} ( \sigma_1 , \sigma_2 , \cdots , \sigma_n) $$ 편의상, $\sigma_{i} \ge \sigma_{j} > 0$ 이라고 하자. 정리하면 $$ AV = \widehat{U} \widehat{\Sigma} $$ 이고 $V V^{\ast} = V^{\ast} V = I$ 이므로 $$ A = \widehat{U} \widehat{\Sigma} V^{\ast} $$ 물론 $\widehat{U} \in \ \mathbb{C}^{m \times n}$ 이므로 $\widehat{U}$ 가 유니터리 행렬은 아니지만, 정규직교성을 가지므로 $\widehat{U}^{\ast} \widehat{U} = I_{n}$ 이고 $$ \begin{align*} A^{\ast}A =& (\widehat{U} \widehat{\Sigma} V^{\ast})^{\ast} (\widehat{U} \widehat{\Sigma} V^{\ast}) \\ =& V \widehat{\Sigma} \widehat{U}^{\ast} \widehat{U} \widehat{\Sigma} V^{\ast} \\ =& V \widehat{\Sigma}^{2} V^{\ast} \\ =& V \widehat{\Sigma}^{2} V^{-1} \end{align*} $$
$$ A = S \begin{bmatrix} \lambda_{1} & 0 & \cdots & 0 \\ 0 & \lambda_2 & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & 0 & \lambda_{m} \end{bmatrix} S^{-1} $$
이는 정방행렬 $A^{\ast} A \in \mathbb{C}^{m \times m}$ 에 대해서 고유값 대각화를 마친 결과로 볼 수 있다. $\sigma^{2}_{i}$ 는 $A^{\ast}A$ 의 고유값이며 $\mathbb{v}_{i}$ 는 $\sigma^{2}_{i}$ 에 해당하는 고유벡터가 되는 것이다. 이제 수치적인 계산을 위해 위의 과정을 거꾸로 거슬러 올라가보자.
알고리즘
행렬 $A \in \mathbb{C}^{m \times n} (m \ge n)$ 에 대해 $\text{rank} A = n$ 이라고 하자.
Step 1.
$A^{\ast} A$ 의 고유값 $\sigma_{1} \ge \sigma_{2} \ge \cdots \ge \sigma_{n}>0$ 들을 찾는다. 임의의 $\mathbb{x} \ne \mathbb{0}$ 에 대해서 $$ \mathbb{x}^{\ast} A^{\ast} A \mathbb{x} = || A \mathbb{x} ||^2 > 0 $$ 즉 $A^{\ast} A$ 가 양의 정부호기 때문에 $\sigma_{i} >0$ 임이 보장된다.
Step 2.
구한 고유값에 대응되는 고유벡터로 정규직교벡터 $V = \begin{bmatrix} v_{1} & v_{2} & \cdots & v_{n} \end{bmatrix}$ 을 찾는다.
Step 3.
$\displaystyle \mathbb{u}_{i} = {{1} \over { \sigma_{i} }} A \mathbb{v}_{i}$ 를 통해 $\widehat{U} = \begin{bmatrix} u_{1} & u_{2} & \cdots & u_{n} \end{bmatrix}$ 을 찾는다.
축소 특이값 분해와 전체 특이값 분해
이렇게 $A = \widehat{U} \widehat{\Sigma} V^{\ast}$ 를 만족하는 세 행렬로 $A$ 를 쪼개는 것을 축소reduced 특이값 분해(rSVD) 라고 한다.
이를 전체full 특이값 분해(fSVD) 와 구분하기 위해서 $\widehat{U}$ 과 $\widehat{\Sigma}$ 같은 표기가 쓰인 것이다.전체 특이값 분해의 아이디어는 단순히 축소 특이값 분해를 조금 확장한 것에 지나지 않는다. 정방행렬 $$ U := \begin{bmatrix} \widehat{U} & \mathbb{u}_{n+1} & \cdots & \mathbb{u}_{m} \end{bmatrix} \in \mathbb{C}^{m \times m} $$ 가 유니터리 행렬이 되도록 하는 $\mathbb{u}_{n+1} , \cdots , \mathbb{u}_{m}$ 을 찾고, $\widehat{\Sigma}$ 의 하단에 $0$ 을 붙이는 식으로 $m \times n$ 행렬 $\Sigma := \begin{bmatrix} \widehat{\Sigma} \\ O \end{bmatrix}$ 를 구성해서 $A = U \Sigma V^{\ast}$ 꼴로 분해하는 것이다.
fSVD 는 이론적으로 더 견고하고, rSVD 는 실제 계산에 더 유리할 것이다. 둘 중 뭐가 됐든 SVD를 구하라는 말은 곧 $U$ 혹은 $\widehat{U}$, $\Sigma$ 혹은 $\widehat{\Sigma}$, $V$ 를 구하라는 말이다.