특이값 분해(Singular Value Decomposition)

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

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

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

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

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

                  (1)

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

                  (2)

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

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

[특이값 분해]

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

                  (3)

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

[증명]

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

                  (4)

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

                  (5)

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

                  (6)

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

                  (7)

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

                  (8)

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

                  (9)

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

                  (10)

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

                  (11)

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

                  (12)

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

______________________________

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

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

   1. 기본(basics)   

[유사 역행렬(pseudoinverse)]

                  (1.1)

여기서 ${\bf \Sigma}^+$의 차원은 $n \times m$이며 대각선 원소는 $1/\sigma_1, 1/\sigma_2, \cdots, 1/\sigma_r, 0, \cdots, 0$이다.

[증명]

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

                  (1.2)

                  (1.3)

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

______________________________

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

[복소 영역으로 일반화]

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

                  (1.4)

여기서 $\bf \Sigma$는 대각선 원소가 음수가 아닌 실수 특이값(singular value) $\sigma_i$인 대각 행렬, $\bf U$와 $\bf 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.