18. 특이값 분해(SVD)

김재희·2021년 9월 14일
0

Linear Algebra

목록 보기
18/18

수반연산자를 임의의 선형변환 T:VWT : V \to W로 확장해서 생각해보자. 이때, 수반사상 TT^*WW에서 VV로의 선형변환이고, [T]βγ=([T]βγ)[T^*]_\beta^\gamma = ([T]^\gamma_\beta)^*일 것이다. 재밌는 점은 VV의 선형연산자 TTT^*T는 positive semi-definite하고, rank(TT)=rank(T)rank(T^*T) = rank(T)라는 점이다. 이를 이용하여 특이값 정리가 나오게 된다.

정리 특이값 정리
유한차원 내적공간 VVWW, 랭크가 rr인 선형변환 T:VWT: V\to W를 가정하자.
이때,

T(vi)={σiui,(1ir)0,(i>r)T(v_i) = \begin{dcases} \sigma_iu_i,& (1\leq i \leq r)\\ 0, & (i > r) \end{dcases}

이 되도록 하는 VV의 정규직교기저 {v1,v2,,vn}\{v_1, v_2, \dots, v_n\}WW의 정규직교기저 {u1,u2,u,um}\{u_1, u_2, u\dots, u_m\}, 양의 스칼라 σ1σ2σr\sigma_1 \geq \sigma_2 \geq \dots \geq \sigma_r가 존재한다.
역으로 이야기하면, vi(1in)v_i(1 \leq i \leq n)TTT^*T의 고유벡터가 되고, 각 고유벡터에 대응하는 고유값은 1ir1\leq i \leq r일 때, σi2\sigma_i^2이고, i>ri>r일 때는 0이다. 즉, σ1,σ2,,σr\sigma_1,\sigma_2, \dots ,\sigma_rTT에 의해 유일하게 결정된다.

증명
VV의 선형연산자 TTT^*T는 랭크가 rr이고, positive semi-definite이다. 이를 이용하여, TTT^*T의 고유값 λi\lambda_i에 대응하는 고유벡터로 이루어진 정규직교기저 {v1,v2,,vn}\{v_1, v_2, \dots, v_n\}가 존재함을 알 수 있다. 이때, positive semi-definite하기 때문에 고유값을 정렬하여 λ1λ2λr>0\lambda_1 \geq \lambda_2 \geq \dots\geq \lambda_r >0이고, i>ri>r일 때, λi=0\lambda_i = 0이 될 것이다. 또한, 1ir1 \leq i \leq r에 대하여, σi=λi,ui=1σiT(vi)\sigma_i = \sqrt{\lambda_i}, u_i = {1 \over \sigma_i}T(v_i)라고 정의하자. 이제 {u1,u2,,un}\{u_1, u_2, \dots, u_n\}WW의 정규직교 부분집합임을 보이면 된다. qi,jrq \leq i, j\leq r이면 다음이 성립한다.

<ui,uj>=<1σiT(vi),1σjT(vj)>=1σiσj<TT(vi),vj>=1σiσj<λivi,vj>=σi2σiσj<vi,vj>=δij\begin{aligned} <u_i,u_j> &= <{1 \over \sigma_i}T(v_i), {1 \over \sigma_j}T(v_j)>\\ &={1\over \sigma_i\sigma_j}<T^*T(v_i), v_j>\\ &={1\over \sigma_i\sigma_j}<\lambda_i v_i, v_j>\\ &={\sigma_i^2 \over \sigma_i\sigma_j}<v_i, v_j>\\ &=\delta_{ij} \end{aligned}

이를 통해 {u1,u2,,ur}\{u_1, u_2, \dots, u_r\}이 정규직교임을 쉽게 보일 수 있다. 또한, 이 집합을 확장하여 WW의 정규직교 기저를 얻을 수 있다. 이제 우리는 1ir1 \leq i \leq r일 때, T(vi)=σiuiT(v_i) = \sigma_iu_i임을 알게 되었다. 또한, i>ri > r일 때, TT(vi)=0T^*T(v_i) = 0이고 이를 통해 T(vi)=0T(v_i) = 0가 임을 알 수 있다.

이제 σi\sigma_i가 유일함을 보이자. {v1,v2,,vn},{u1,u2,,um},σ1σ2σr>0\{v_1, v_2, \dots, v_n\}, \{u_1, u_2, \dots, u_m\}, \sigma_1 \geq \sigma_2 \geq \dots \sigma_r >0 이 세가지 조건이 만족되었다고 가정하자. 이때, σi=TT(vi)\sigma_i = \sqrt{T^*T(v_i)}를 이용하면 qim,1jnq \leq i \leq m, 1 \leq j \leq n에 대해 다음이 성립한다.

<T(ui),vj>=<ui,T(vj)>={σi,(i=jr)0,(else)\begin{aligned} <T^*(u_i), v_j> &= <u_i, T(v_j)>\\ &=\begin{dcases} \sigma_i,& (i=j \leq r)\\ 0, & (else) \end{dcases} \end{aligned}

이제 임의의 1im1 \leq i \leq m에 대해 T(ui)T^*(u_i)를 다음과 같이 보일 수 있다.

T(ui)=j=1n<T(ui),vj>vj={σivi(1=jr)0(else)\begin{aligned} T^*(u_i) = \sum^n_{j=1}<T^*(u_i), v_j>v_j = \begin{dcases} \sigma_iv_i& (1 = j \leq r)\\ 0 &(else) \end{dcases} \end{aligned}

정리해보면, iri \leq r일때, TT(vi)=T(σiui)=σiT(ui)=σ2viT^*T(v_i) = T^*(\sigma_iu_i) = \sigma_iT^*(u_i) = \sigma^2v_i로 정리되고, i>ri > r일 때, TT(vi)=T(0)=0T^*T(v_i) = T^*(0) = 0으로 정리된다. 즉, 각 viv_iiri \leq r에 대해 고유값 σi2=λi\sigma_i^2 = \lambda_i에 대응하는 고유벡터가 되고, i>ri>r에 대해서는 0이다.

정의
위의 정리에서 정의한 유일한 스칼라 $σ1,σ2,,σr\sigma_1,\sigma_2, \dots ,\sigma_rTT특이값이라 한다. r<m,r<nr<m, r<n이면 특이값은 σr+1==σk=0\sigma_{r+1} = \dots = \sigma_k = 0으로 확장이 가능하다. 이때, kkmmnn의 최소값이다.

여기서 선형변환 TT의 특이값은 TT에 의해 유일하게 결정되지만, 위 정리의 정규직교기저는 유일하게 결정되지 않는다는 점에 유의하자. 왜냐하면 TTT^*T의 고유벡터로 이루어진 정규직교기저는 당연히 하나 이상 존재할 것이기 때문이다. 교유값은 유일하지만, 이에 대응하는 고유벡터가 유일하지 않다는 점을 떠올리면 쉽게 이해할 수 있다.

또한, 선형 변환 T:VWT : V\to W와 그 수반연산자 TT^*의 특이값은 서로 같게 된다. 또한, VVWW의 정규직교기저를 뒤집으면 TT^* 의 정규직교기저가 될 것이다.

자연스레 이제 연산자에서 행렬로 특이값 정리를 이어가보도록 하자.

정의 m×nm \times n행렬 AA에 대하여 선형변환 LAL_A의 특이값을 AA의 특이값이라 정의한다.

정리 2 행렬의 특이값 분해 정리
랭크가 rrm×nm\times n행렬 AA가 있다고 하자. 이 행렬의 특이값은 σ1σ2σr>0\sigma_1 \geq \sigma_2 \geq \dots \geq \sigma_r >0이라 할때, m×nm \times n 행렬 Σ\Sigma를 다음과 같이 정의하자.

Σij={σi(i=jr)0(else)\begin{aligned} \Sigma_{ij} = \begin{dcases} \sigma_i & (i = j \leq r)\\ 0 & (else) \end{dcases} \end{aligned}

이제 A=UΣVA = U\Sigma V^*m×mm \times m 행렬 UUn×nn \times n행렬 VV가 존재한다.

증명
T=LA:FnFmT = L_A : F^n \to F^m이 있다고 하자. 이때 정리 1에 의해 T(vi)=σiui(1ir),T(vi)=0(i>r)T(v_i) = \sigma_iu_i(1\leq i \leq r) , T(v_i) = 0(i >r)FnF^n의 정규직교기저 β={v1,v2,,vn}\beta = \{v_1, v_2, \dots, v_n\}FmF^m의 정규직교기저 γ={u1,u2,,um}\gamma = \{u_1, u_2, \dots, u_m\}이 존재한다. 모든 jj에 대하여 jj열이 uju_jm×mm\times m 행렬을 UU, 모든 jj에 대하여 vjv_jn×nn\times n행렬을 VV라 하자. 중요한 점은 이대 U,VU, V 모두 유니타리 행렬이다.

이때 행렬표현에 의해 AVAVjj열은 Avj=σjujAv_j = \sigma_ju_j일 것이다. Σ\Sigmajj열은 σjej\sigma_je_j(eje_jFmF^mjj번째 표준벡터)이다. 이를 이용하면 UΣU\Sigmajj열은 다음과 같을 것이다.

U(σjej)=σjUej=σjujU(\sigma_j e_j) = \sigma_j Ue_j = \sigma_j u_j

이때, AVAVUΣU\Sigma는 모두 m×nm\times n행렬이고, 대응하는 열이 같다. 다시말해 AV=UΣAV = U\Sigma이므로, A=AVV=UΣVA = AVV^* = U \Sigma V^*이 된다.

정의
특이값이 σ1σ2σr>0\sigma_1 \geq \sigma_2 \geq \dots \geq \sigma_r >0이고, 랭크가 rrm×nm\times n행렬 AA를 생각하자. 이때, 정리 2에서 정의한 것처럼 유니타리 행렬 U,VU, Vm×nm\times n행렬 Σ\Sigma에 대해 A=UΣVA = U\Sigma V^*가 성립할 때, 이 분해를 AA의 특이값 분해라 한다.

여기서 VV의 열은 β\beta의 벡터이고, UU의 열은 γ\gamma의 벡터이다. 즉, 행렬의 특이값 분해는 행렬을 행공간, 열공간, 고유값 각각을 가지는 세 행렬로 나누는 것이다.

0개의 댓글