logo

행렬의 특이값 분해 📂행렬대수

행렬의 특이값 분해

개요

늘 고유값 대각화를 통해 행렬을 쪼갤 수 있다면 좋겠지만, 이 방법엔 아쉽게도 주어지는 행렬이 정방행렬이어야한다는 제한이 있다. 이에 대각화할 행렬을 정방행렬이 아닌 경우로 확장해서 분해하려고 한다.

빌드업

두 자연수 m>nm > n 에 대해 행렬 A∈Cm×nA \in \mathbb{C}^{ m \times n} 의 계수가 rankA=n\text{rank} A = n 으로 주어진다고 하자. 그러면 dim⁡C(A)=dim⁡C(AT)=n\dim C(A) = \dim C(A^{T}) = n 으로, 이들의 정규직교벡터 v1,⋯ ,vn∈C(A)\mathbf{v}_{1} , \cdots , \mathbf{v}_{n} \in C(A) 과 u1,⋯ ,un∈C(AT)\mathbf{u}_{1} , \cdots , \mathbf{u}_{n} \in C(A^{T}) 을 생각할 수 있다.

고유값의 기하학적인 의미를 생각할 때와 마찬가지로 Avi=σiui A \mathbf{v}_{i} = \sigma_{i} \mathbf{u}_{i} 를 만족하는 σi>0\sigma_{i}>0 가 존재한다고 가정하자. 그러면 AA 는 vi\mathbf{v}_{i} 의 방향을 ui\mathbf{u}_{i} 와 일치하도록 만드는 선형변환이고 σi>0\sigma_{i}>0 는 그 크기를 맞춰주는 것으로 볼 수 있다. 이러한 σi\sigma_{i} 는 고유값이 아니라 AA 의 특이값이라 정의하는데, 아쉽게도 그 의미는 특이값 분해와 전혀 상관이 없다. 여기서 고유값에서의 논의와 달라지는 것은 A∈Cm×nA \in \mathbb{C}^{ m \times n}, 즉 vi∈Cn\mathbf{v}_{i} \in \mathbb{C}^{n} 이고 ui∈Cm\mathbf{u}_{i} \in \mathbb{C}^{m} 이므로 AA 가 벡터의 차원도 바꾼다는 것이다. 행렬 AA 에 대해 정리해서 A=σiuivi∗A = \sigma_{i} \mathbf{u}_{i} \mathbf{v}_{i}^{\ast} 이고 양변의 차원은 m×n=(m×1)×(1×n)m \times n = ( m \times 1 ) \times (1 \times n ) 이 됨을 확인해보자. 한편 고유벡터와 달리 좌우가 구분이 되므로 ui\mathbf{u}_{i} 는 좌특이벡터 , vi\mathbf{v}_{i} 가 우특이벡터 로 정의된다는 것에 유의하자.이제 Avi=σiuiA \mathbf{v}_{i} = \sigma_{i} \mathbf{u}_{i} 을 1≤i≤n1 \le i \le n 에 대해 풀어서 쓰면 A[v1v2⋯vn]=[u1u2⋯un][σ10⋯00σ2⋱⋮⋮⋱⋱00⋯0σm] A \begin{bmatrix} \mathbf{v}_{1} & \mathbf{v}_{2} & \cdots & \mathbf{v}_{n} \end{bmatrix} = \begin{bmatrix} \mathbf{u}_{1} & \mathbf{u}_{2} & \cdots & \mathbf{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:=[v1v2⋯vn]∈Cn×nU^:=[u1u2⋯un]∈Cm×nΣ^:=diag(σ1,σ2,⋯ ,σn) V := \begin{bmatrix} \mathbf{v}_{1} & \mathbf{v}_{2} & \cdots & \mathbf{v}_{n} \end{bmatrix} \in \mathbb{C}^{n \times n} \\ \widehat{U} := \begin{bmatrix} \mathbf{u}_{1} & \mathbf{u}_{2} & \cdots & \mathbf{u}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n} \\ \widehat{\Sigma} := \text{diag} ( \sigma_1 , \sigma_2 , \cdots , \sigma_n) 편의상, σi≥σj>0\sigma_{i} \ge \sigma_{j} > 0 이라고 하자. 정리하면 AV=U^Σ^ AV = \widehat{U} \widehat{\Sigma} 이고 VV∗=V∗V=IV V^{\ast} = V^{\ast} V = I 이므로 A=U^Σ^V∗ A = \widehat{U} \widehat{\Sigma} V^{\ast} 물론 U^∈ Cm×n\widehat{U} \in \ \mathbb{C}^{m \times n} 이므로 U^\widehat{U} 가 유니터리 행렬은 아니지만, 정규직교성을 가지므로 U^∗U^=In\widehat{U}^{\ast} \widehat{U} = I_{n} 이고 A∗A=(U^Σ^V∗)∗(U^Σ^V∗)=VΣ^U^∗U^Σ^V∗=VΣ^2V∗=VΣ^2V−1 \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[λ10⋯00λ2⋱⋮⋮⋱⋱00⋯0λm]S−1 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∗A∈Cm×mA^{\ast} A \in \mathbb{C}^{m \times m} 에 대해서 고유값 대각화를 마친 결과로 볼 수 있다. σi2\sigma^{2}_{i} 는 A∗AA^{\ast}A 의 고유값이며 vi\mathbf{v}_{i} 는 σi2\sigma^{2}_{i} 에 해당하는 고유벡터가 되는 것이다. 이제 수치적인 계산을 위해 위의 과정을 거꾸로 거슬러 올라가보자.

알고리즘

행렬 A∈Cm×n(m≥n)A \in \mathbb{C}^{m \times n} (m \ge n) 에 대해 rankA=n\text{rank} A = n 이라고 하자.

Step 1.

A∗AA^{\ast} A 의 고유값 σ1≥σ2≥⋯≥σn>0\sigma_{1} \ge \sigma_{2} \ge \cdots \ge \sigma_{n}>0 들을 찾는다. 임의의 x≠0\mathbf{x} \ne \mathbb{0} 에 대해서 x∗A∗Ax=∣∣Ax∣∣2>0 \mathbf{x}^{\ast} A^{\ast} A \mathbf{x} = || A \mathbf{x} ||^2 > 0 즉 A∗AA^{\ast} A 가 양의 정부호기 때문에 σi>0\sigma_{i} >0 임이 보장된다.

Step 2.

구한 고유값에 대응되는 고유벡터로 정규직교벡터 V=[v1v2⋯vn]V = \begin{bmatrix} v_{1} & v_{2} & \cdots & v_{n} \end{bmatrix} 을 찾는다.

Step 3.

ui=1σiAvi\displaystyle \mathbf{u}_{i} = {{1} \over { \sigma_{i} }} A \mathbf{v}_{i} 를 통해 U^=[u1u2⋯un]\widehat{U} = \begin{bmatrix} u_{1} & u_{2} & \cdots & u_{n} \end{bmatrix} 을 찾는다.

축소 특이값 분해와 전체 특이값 분해

이렇게 A=U^Σ^V∗A = \widehat{U} \widehat{\Sigma} V^{\ast} 를 만족하는 세 행렬로 AA 를 쪼개는 것을 축소reduced 특이값 분해(rSVD) 라고 한다.

이를 전체full 특이값 분해(fSVD) 와 구분하기 위해서 U^\widehat{U} 과 Σ^\widehat{\Sigma} 같은 표기가 쓰인 것이다.전체 특이값 분해의 아이디어는 단순히 축소 특이값 분해를 조금 확장한 것에 지나지 않는다. 정방행렬 U:=[U^un+1⋯um]∈Cm×m U := \begin{bmatrix} \widehat{U} & \mathbf{u}_{n+1} & \cdots & \mathbf{u}_{m} \end{bmatrix} \in \mathbb{C}^{m \times m} 가 유니터리 행렬이 되도록 하는 un+1,⋯ ,um\mathbf{u}_{n+1} , \cdots , \mathbf{u}_{m} 을 찾고, Σ^\widehat{\Sigma} 의 하단에 00 을 붙이는 식으로 m×nm \times n 행렬 Σ:=[Σ^O]\Sigma := \begin{bmatrix} \widehat{\Sigma} \\ O \end{bmatrix} 를 구성해서 A=UΣV∗A = U \Sigma V^{\ast} 꼴로 분해하는 것이다.

fSVD 는 이론적으로 더 견고하고, rSVD 는 실제 계산에 더 유리할 것이다. 둘 중 뭐가 됐든 SVD를 구하라는 말은 곧 UU 혹은 U^\widehat{U}, Σ\Sigma 혹은 Σ^\widehat{\Sigma}, VV 를 구하라는 말이다.

같이보기