특이값 분해(Singular Value Decomposition)

[경고] 아래 글을 읽지 않고 "특이값 분해"를 보면 바보로 느껴질 수 있습니다.

1. 행렬의 고유치와 고유 벡터

2. 에르미트 행렬과 유니터리 행렬

[스트랭Gilbert Strang 교수의 SVD 강의]

행렬의 대각화(diagonalization)에 쓰이는 식 (1)에 제시한 고유 분해(eigendecomposition)는 유용하지만 제한이 많다.

                  (1)

여기서 $\mathbf{S}$는 고유 벡터 행렬(eigenvector matrix), $\mathbf{\Lambda }$는 고유치 행렬(eigenvalue matrix)이다. 식 (1)이 성립하려면, 행렬 $\mathbf{A}$는 정방 행렬이어야 한다. 만약 $\mathbf{A}$가 정방 행렬이며 대칭 행렬이라면, 식 (1)을 더 간단히 공식화할 수 있다.

                  (2)

여기서 $\mathbf{Q}$는 고유 벡터로 구성한 직교 행렬(orthogonal matrix)이다. 식 (2)처럼 아름다운 고유 분해를 모든 행렬로 확장할 수 있는 방법이 존재한다. 그 비법은 바로 임의의 행렬을 대각화할 수 있는 특이값 분해(singular value decomposition)이다. 특이값 분해는 간단히 SVD라고도 한다. SVD를 쓰면, 정방 행렬 혹은 대칭 행렬 조건에 관계없이 임의의 행렬을 대각화할 수 있다.

[그림 1] 2차원에 적용한 특이값 분해(출처: wikipedia.org)

[특이값 분해]

임의의 $m\times n$ 행렬 $\mathbf{A}$를 다음과 같은 행렬의 곱으로 대각화할 수 있다. 

                  (3)

여기서 $\mathbf{\Sigma }$는 대각선 원소가 음수가 아닌 특이값(singular value) ${\sigma }_i$인 대각 행렬, $\mathbf{U}$와 $\mathbf{V}$는 각각 좌특이 벡터(left-singular vector) ${\mathbf{u}}_i$와 우특이 벡터(right-singular vector) ${\mathbf{v}}_i$가 열 벡터로 들어가는 직교 행렬(orthogonal matrix), $(\cdot {)}^T$는 전치 행렬(transpose)이다. 행렬 $\mathbf{\Sigma }$, $\mathbf{U}$, $\mathbf{V}$의 차원은 각각 $m\times n$, $m\times m$, $n\times n$이다.

[증명]

행렬 $\mathbf{A}$에 대해 특이값이 $0$이 아닌 좌특이 벡터와 우특이 벡터는 다음과 같다.

                  (4)

여기서 ${\sigma }_i$ = $\sqrt{{\lambda }_i}$, ${\lambda }_i$는 고유치(eigenvalue)이다. 식 (4)를 고유치와 고유 벡터의 관점으로 다시 쓰면 다음과 같다.

                  (5)

여기서 ${\mathbf{u}}_i$와 ${\mathbf{v}}_i$는 특이 벡터이면서 동시에 고유 벡터이다. 최소 제곱 행렬 ${\mathbf{A}}^T\mathbf{A}$와 $\mathbf{A}{\mathbf{A}}^T$는 $\mathbf{A}$에 관계없이 항상 대칭 행렬이다. 또한 두 최소 제곱 행렬의 고유치 ${\lambda }_i$는 음수가 아니고 서로 같다. 최소 제곱 행렬의 고유 벡터는 서로 직교하는 성질이 있다. 이러한 성질과 식 (5)를 바탕으로 최소 제곱 행렬을 고유 분해한다.

                  (6)

식 (6)에 있는 직교 행렬 $\mathbf{U}$, $\mathbf{V}$와 대각 행렬 ${\mathbf{\Lambda }}_u$, ${\mathbf{\Lambda }}_v$는 다음처럼 구성한다.

                  (7)

여기서 $r$ = $\mathrm{rank}(\mathbf{A})\le min(m,n)$, 대각 행렬의 고유치는 내림차순으로 ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_r\ge 0$처럼 배치한다. 고유치가 서로 다르지 않고 같은 경우가 생기면, 고유 벡터를 선택할 때 자유도가 생긴다. 이때는 그람–슈미트 과정(Gram–Schmidt process)을 이용해서 고유 벡터가 서로 직교하도록 선택한다. 식 (7)에 있는 대각 행렬 ${\mathbf{\Lambda }}_u$, ${\mathbf{\Lambda }}_v$를 다음처럼 다시 분해할 수 있다.

                  (8)

여기서 특이값도 고유치[${\lambda }_i$ = ${\sigma }_i^2$]처럼 내림차순으로 ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r\ge 0$을 만족하게 배열한다. 식 (8)을 식 (6)에 대입하고 직교 행렬의 성질인 $\mathbf{Q}{\mathbf{Q}}^T$ = ${\mathbf{Q}}^T\mathbf{Q}$ = $\mathbf{I}$를 적용하면, 식 (6)을 더 세부적인 행렬로 분해할 수 있다.

                  (9)

따라서 행렬 $\mathbf{A}$는 식 (3)처럼 분해될 가능성이 있다. 마지막으로 식 (3)의 우변이 좌변과 같은지 확인하자[3]. 먼저 임의의 열 벡터 $\mathbf{x}$와 $\mathbf{\Sigma }{\mathbf{V}}^T$를 곱해보자.

                  (10)

식 (3)의 우변과 같은 모양을 만들기 위해 식 (10)의 결과에 $\mathbf{U}$를 곱한다.

                  (11)

식 (11)에 식 (4)의 첫째식을 대입해서 정리한다.

                  (12)

여기서 ${\mathbf{v}}_i$는 정규 직교 기저(orthonormal basis), $i>r$이면 $\mathbf{A}{\mathbf{v}}_i$ = $0$, $\mathbf{V}{\mathbf{V}}^T$ = $\mathbf{I}$이다. 따라서 식 (12)는 임의의 $\mathbf{x}$에 대한 항등식이어서 식 (3)이 성립한다.

______________________________

특이값의 영어 알파벳이 s로 시작하므로, 특이값을 가진 대각 행렬의 알파벳은 $\mathrm{\Sigma }$가 된다. 또한 행렬 $\mathbf{U}$는 일반적으로 유니터리 행렬(unitary matrix)이어서 알파벳 U로 표현한다.

명확히 증명한 특이값 분해는 다양한 방식으로 응용할 수 있다.

   1. 기본(basics)   

[유사 역행렬(pseudoinverse)]

                  (1.1)

여기서 ${\mathbf{\Sigma }}^{+}$의 차원은 $n\times m$이며 대각선 원소는 $1/{\sigma }_1,1/{\sigma }_2,\cdots ,1/{\sigma }_r,0,\cdots ,0$이다.

[증명]

유사 역행렬의 특성을 확인하기 위해 다음 행렬 곱을 고려한다.

                  (1.2)

                  (1.3)

여기서 $i>r$이면 ${\mathbf{u}}_i^T\mathbf{A}$ = ${\mathbf{v}}_i^T{\mathbf{A}}^{+}$ = $0$이다. 행렬 곱 $\mathbf{A}{\mathbf{A}}^{+}$와 ${\mathbf{A}}^{+}\mathbf{A}$는 완전한 항등 행렬이 아닐 수 있지만,  $\mathbf{A}$ 혹은  ${\mathbf{A}}^{+}$가 곱해진 조건에서는 항등 행렬이 된다. 따라서 식 (1.1)은 유사 역행렬의 표현식이 된다.

______________________________

행렬 $\mathbf{A}$의 행 벡터가 모두 선형 독립이면, 식 (1.2)에 의해 $\mathbf{A}{\mathbf{A}}^{+}$ = $\mathbf{I}$가 된다. 이 경우 ${\mathbf{A}}^{+}$는 우역행렬(right inverse)이다. 비슷하게 $\mathbf{A}$의 열 벡터가 선형 독립이면, ${\mathbf{A}}^{+}\mathbf{A}$ = $\mathbf{I}$가 되어서 ${\mathbf{A}}^{+}$는 좌역행렬(left inverse)이 된다. 유사 역행렬은 일반화 역행렬(generalized inverse) 혹은 무어–펜로즈 역행렬(Moore–Penrose inverse)이라고도 한다.

[복소 영역으로 일반화]

에르미트 행렬(Hermitian matrix)과 유니터리 행렬(unitary matrix)을 도입하면 복소 영역에서 특이값 분해를 할 수 있다.

                  (1.4)

여기서 $\mathbf{\Sigma }$는 대각선 원소가 음수가 아닌 실수 특이값(singular value) ${\sigma }_i$인 대각 행렬, $\mathbf{U}$와 $\mathbf{V}$는 특이 행렬로 구성한 유니터리 행렬, $(\cdot {)}^H$는 켤레 전치 행렬(conjugate transpose)이다.

[증명]

에르미트 행렬의 고유치는 실수이며, 고유 벡터는 서로 직교한다. 유니터리 행렬은 열 벡터가 서로 정규 직교(orthonormal: 크기는 $1$이면서 서로 직교)한다. 이런 특성을 식 (3)의 증명에 교체해서 적용하면, 식 (1.4)를 증명할 수 있다.

______________________________

[참고문헌]

[1] G. Strang, Linear Algebra and its Applications, 4th ed., Brooks/Cole, 2006.

[2] G. Gundersen, "Proof of the singular value decomposition," Blog, 2018. (방문일 2020-08-03)

[3] M. Hutchings, "Notes on singular value decomposition for Math 54," Linear Algebra and Differential Equations, UC Berkeley, 2017. (방문일 2020-08-04)

[4] P. L. Gilabert, R. N. Braithwaite and G. Montoro, "Beyond the Moore-Penrose inverse: strategies for the estimation of digital predistortion linearization parameters," IEEE Microw. Mag., vol. 21, no. 12, pp. 34–46, Dec. 2020.