A Fresh Approach to the Singular Value Decomposition 첫 번째

원문: 1998, Colm Mucahy and John Rossi, A Fresh Approach to the Singular Value Decomposition

선행개념: 행렬, 대각행렬, 전치행렬, 역행렬, 직교행렬, 고윳값, 고유벡터, 대각화, 직교대각화.

목차

1. 소개
2. 복소수의 극형식과 행렬의 극분해(Polar Decomposition)
3. 특이값 분해(Singular Value Decomposition)
4. 의사 역행렬(Pseudo-inverse)
5. Solving All Systems

항이 실수인 행렬만 다루며, 여기서는 1~2의 주제를 다룬다.

연결된 포스팅 링크: 1부(주제1,2), 2부(주제3), 3부(주제4,5)

---

1. 소개

SVD(Singular Value Decomposition) 이란?

임의의 행렬 $A$에 대해 $A=UDV^T$의 꼴로 나타내는 것을 SVD라고 한다. 여기서 $U, V$는 직교행렬*이며, $D$는 대각행렬**이다.

SVD의 활용

행렬의 랭크(Rank), norm, 불량조건의 최소제곱문제(least squares problem)에 사용되며,
또한 행렬의 극분해와 관련이 깊어 연속체역학, 재료과학, 편광학, 빅데이터에서의 차원 축소 등 광범위하게 쓰인다.

이 논문에서는 특히 복소수의 극형식에서 착안하여 행렬의 극분해(RW decomposition)로 SVD를 살펴보며, SVD가 어려운 것이 아니며 선형대수 학습 과정에서 매우 자연스러운 주제임을 알리는데 목표가 있다고 한다.

$\mathbf{Theorem}$. 모든 행렬은 역행렬이 존재한다. 그러므로 모든 선형 구조의 문제는 풀 수 있다.

의사역행렬, 최소제곱법 등 선형대수의 목표로 돌아가 선형 형태의 방정식을 풀 수 있다는 것을 정리로 논문을 시작한다.

* $A^T$는 대각선을 기준으로 뒤집은 행렬 즉 전치행렬(transpose)을 뜻한다.
* 직교행렬(orthogonal matrice)이란 $A A^T = A^T A = I$을 만족하는 행렬이다. 여기서 $I$는 단위행렬(대각선 성분이 1이고 나머지가 0인 정사각행렬)이다. 직교행렬은 각 열벡터가 단위벡터이고 서로 독립인 벡터로 이루어져있다.
**대각행렬(diagonal)이란 행렬의 대각선 성분 $a_{ii}$을 제외한 나머지 성분이 0인 행렬을 의미한다.

---

2. 복소수의 극형식과 행렬의 극분해(Polar Decomposition)

고윳값과 고유벡터를 이용한 고윳값 분해

다음의 과정을 이해하려면 정사각행렬에 대해 고윳값과 고유벡터를 구하여 $A=PDP^{-1}$를 구하는 과정을 알고 있어야한다.
특히, 각 항이 실수인 대칭행렬 A는 항상 $A=UDU^T$꼴로 표현이 가능하다. 이때 $U$는 직교행렬, $D$는 대각행렬이다.
여기서 행렬 $D$는 $A$의 고윳값 $\lambda_1, \lambda_2, ... $을 대각성분으로 하는 행렬이며, $U$는 각 고윳값에 대응되는 고유벡터 중 길이가 1인 단위벡터를 열로 갖는 행렬이다. 이것을 직교대각화라고 한다.
증명은 이번 주제의 메인이 아니므로 생략한다.

복소수의 극형식과 행렬의 유사성

전치행렬은 켤레복소수와 유사한 점이 있다.
먼저, 복소수 집합 $\mathbb{C}$의 원소 $z$를 생각하자.
$z = x+yi, \; x,y \in \mathbb{R}$ 꼴로 유일하게 표현이 가능하다.
이것을 켤레복소수를 이용하면 $x=\frac{z+\overline{z}}{2}$, $yi= \frac{z-\overline{z}}{2}$로 나타낼 수 있다.

또한 $z \neq 0$ 이면 $z=rw$ 꼴로도 표현이 가능하다. 이때 $r$은 실수, $w$는 단위복소수*이다.
이것을 보고 복소수의 극형식이라는 것을 눈치챈 분도 있을 것이다.
이를 다르게 표현하면 $ z=re^{i \theta}$ 꼴로 볼 수 있다.

이제 행렬도 위와 같은 방식으로 표현해보자.
모든 행렬은 $A= S+ K$의 꼴로 유일하게 표현이 가능하다.
여기서 $S$는 대칭행렬($S=S^T$), K는 반대칭행렬($K = -K^T$)이다.
이 사실은 $S= \frac{1}{2}(A+A^T), K=\frac{1}{2}(A-A^T)$ 라고 하면 쉽게 증명 할 수 있다.

이 유사성을 토대로 한 가지 재밌는 질문을 던질 수 있다. 행렬도 복소수처럼 극형식이 있지 않을까?
그래서 실제로 아래와 같은 정리를 찾을 수 있다.

$\mathbf{Theorem1}$. 가역*인 정사각행렬 A는 항상 $A=RW$로 표현 가능하다.
여기서 R은 모든 항이 양수인 대칭행렬($R=R^T$), W는 직교행렬이다.(W W^T=I$)

$\mathbf{Proof}$. 증명의 아이디어를 복소수에서 가져온다. 0이 아닌 복소수 $z \in \mathbb{C}$를 $z=rw$꼴($r>0$인 실수와 $w \overline{w}=1$을 만족하는 복소수 $w$)로 나타낼 수 있다는 것을 어떻게 보이는지 생각해보자. $z=rw$꼴로 나타낼 수 있다고 가정하자. (이때, $r, w$의 존재를 보이면 된다. 즉, 실제로 계산해서 해를 구하면 된다.)
$ \overline{z}= \overline{w} r$ 이고(복소수의 곱에 켤레를 취하면 곱하기 순서가 바뀜을 유의하자.)
$z \overline{z} = rw\overline{w} r = r^2 $ 이므로
$r= \sqrt{z \overline{z}}, w = r^{-1} z$ 이고 $r>0, \, w \overline{w}=1$도 만족한다.

이것을 흉내내어 행렬에서도 적용해보자.
만약 $A=RW$로 행렬이 표현되었다고 가정해보자.($R=R^T, W W^T=I$)
$A^T=W^T R$이므로 $A A^T=R W W^T R = R^2$ 이다.
따라서 우리는 $A A^T$의 제곱근이 존재하는지만 보이면 된다.
$(A A^T)^T=A A^T$ 이므로 $A A^T$은 대칭행렬이며, 고윳값이 항상 양수가 된다.
앞서서 말했듯 대칭행렬은 항상 직교대각화가 가능하다.

따라서 $A A^T=PBP^{T}$라고 쓸 수 있다.($P$는 열벡터가 고유벡터인 직교행렬, $B$는 고윳값을 항으로 갖는 대각행렬이다.)
이때 $P$의 열벡터 순서를 조정하여 $B$의 고윳값 배열을 증가하도록 놓을 수 있음을 기억하자.

고윳값은 항상 양수이므로 대각행렬 $B$의 제곱근이 되는 행렬 $D$를 찾을 수 있다.(각 항에 루트를 씌우기만하면 된다.)
즉 $B=D^2$이다. $R=PDP^{T}$라고 놓으면 $R^2 = PDP^{T}PDP^{T} =P D^2 P^{T} $이 되어
$A A^T$의 제곱근이 $R=PDP^{T}$임을 찾았다!
$R$은 대칭행렬이므로 역행렬이 항상 존재하기 때문에 $W=R^{-1} A $로 나타낼 수 있고
$WW^{T}=R^{-1} A A^{T} R^{-1} = R^{-1} R^2 R^{-1} = I $가 되어 만족하는 $W$도 찾을 수 있다.
($R^{-1} = PD^{-1} P^{T}$ 이므로 $(R^{-1})^{T} = PD^{-1} P^{T}=R^{-1}$ 이다. 대각행렬의 전치행렬은 자기자신이므로)

이로써 $R=PDP^{T}$, $W=R^{-1} A $으로 놓으면 위의 정리가 성립됨을 쉽게 보일 수 있다.

위의 정리를 복소수의 극형식과 같이 행렬의 극분해라고 표현한다.

복소수에서 극형식 $z=rw$ 꼴로 나타내면
복소평면에서 $r$은 길이 $w=e^{i \theta}$은 회전각을 나타냈던 것을 기억하는가?

놀랍게도 행렬도 위와 같이 작동한다.

행렬은 선형변환과 관련있다는 것을 알고 있을 것이다.
$T(\mathbf{x})=A \mathbf{x}$ 인 함수를 생각하면 이것이 선형변환이 되기 때문이다.
이때 $A=RW$로 표현하면
행렬 $W$는 회전변환이 되고
행렬 $R$에서 $D$의 고윳값은 길이를 확대하거나 축소하는 길이변환이 된다.
(행렬$P$는 회전된 새로운 축을 설정해주는 역할을 한다.)

다음 포스팅에서는 극분해의 실제 예시와 RW로부터 SVD로 확장하는 과정을 서술하겠다.

*단위복소수 : $|z|^2=z \overline{z}$ 라고 할 때, $|z|=1$인 복소수
**가역 : 역행렬이 존재한다. 역행렬은 $AA^{-1}=I$을 행렬곱의 역원인 행렬이다.