📝 상세 정리
- 행렬 $A \in R^{m \times n}$가 랭크 $r \in [0, min(m, n)]$ 인 rectangular matrix라 할 때, $A$의 $SVD$는 다음과 같은 형태이다.
- $A = U\Sigma V^T$
- 그리고 이 Singular Value Decomposition(SVD, 특잇값 분해)는 정사각 행렬 뿐만 아니라 모든 행렬에 대해 적용할 수 있고 항상 존재한다!!
- 이에 fundamental theorem of linear algebra라고도 부른다.
- 기하학적 직관으로 관찰하면 다음과 같다.
- 고윳값 분해 에서 확인했던 것과 마찬가지로, 직관적으로 보기 쉬운 축으로 변환한 뒤 변환을 수행하고 원래대로 놀려놓는 것이다.
- 일단 정사각 행렬의 고윳값분해와 특잇값분해를 보면서 차이를 비교해보자.
- $S = S^T = PDP^T$
- $S = U\Sigma V^T$
- 그러면 $U = P = V, D = \Sigma$로 매칭됨을 먼저 확인할 수 있다.
- 이 식이 어떻게 탄생했을지 생각해보자.
- 일단 고윳값분해가 안되는 행렬이 존재했던 이유는 변환과 역변환 과정에서 같은 기저를 사용했다는데에 있다.
- 그런데 같은 기저를 두번 사용할 필요가 있을까?
- 입력공간 $R^N$ 에서 사용하는 기저와 출력공간 $R^M$에서 사용하는 기저가 달라도, orthogonal함과 관계만 잘 정의되면 크게 문제없지 않을까?
- 따라서 $A$의 SVD를 계산하는것은 $R^M$의 기저 $U$와 $R^N$의 기저 $V$를 찾는 것과 같다.
- 먼저 $R^N$의 기저 $V$를 찾고,
- 이에 맞춰 $U$를 구성한 후
- 그 둘을 직교성을 살리며 잘 이어붙이는 방향으로 진행해보자.
- 전략을 하나 생각해보자. $U, V$를 만들고싶은데, 정사각 행렬이 아니라서 고유값 분해를 바로 쓰지 못한다.
- $A^TA, AA^T$를 사용하는건 어떨까?
- 항상 정방행렬이며, 심지어 symmetric하다.
- 다시말해, 확실하게 고유값분해가 존재하고, eingervector 직교하기까지 한다!
- $A^TA, AA^T$를 사용하는건 어떨까?
- $V$를 먼저 구성해보자.
- 이는 $A^TA$의 eingervector이다.
- 따라서 $A^TA = PDP^T, \, D = diag(\lambda_1, ..., \lambda_n), \, \lambda_i \geq 0$ 이다.
- 만약 SVD $A = U\Sigma V^T$가 존재한다면, 위 식은 다음과 같이 바뀔것이다.
- $A^TA = (U\Sigma V^T)^T(U\Sigma V^T) = V\Sigma^TU^TU\Sigma V^T = V(\Sigma^T\Sigma )V^T$
- $\Sigma^T\Sigma = diag(\sigma_1^2, ..., \sigma_n^2)$
- 그렇다면 $A^TA$가 $PDP^T$, $V(\Sigma^T\Sigma )V^T$ 두가지로 대각화된 셈인데, 대각화는 유일해야하므로 두 식의 대응되는 조각들은 같아야한다. 따라서
- $V = P, \sigma_i^2 = \lambda_i$ 임이 나온다! $V$는 그냥 $A^TA$의 eingervector이고, $\sigma_i$는 $A^TA$의 $eingervalue$의 제곱근이다.
- 같은 방식으로 $U$에 적용하면
- $AA^T = SDS^T$ 에서
- $U = S$, $U$는 $AA^T$의 고유벡터임을 확인할 수 있다
- 자, 각각의 존재성은 알겠다. 그런데 이 $U, V$가 서로 무관하면 우리의 가설이 성립한다는 보장이 없다. 서로 잘 대응되게 짝지어줘야한다.
- 방식을 약간 바꿔서, $U$를 $V$로부터 구해보자.
- 일단 $A{v_i}$들끼리는 서로 직교한다.
- $(A{v_i})^T(A{v_j}) = v_i^T(A^TA)v_j = v_i^T(\lambda_j v_j) = \lambda_j (v_i^T v_j) = 0$
- orthonormal함을 위해 정규화해서 $u_i$를 만들자.
- $u_i := \frac{Av_i}{||Av_i||}$
- $||Av_i|| = \sqrt{(Av_i)^T(Av_i)} = \sqrt{v_i^TA^TAv_i} = \sqrt{\lambda_i} = \sigma_i$
- 이렇게 정의한 $u_i$가 $AA^T$의 eigenvector과 같음을 알 수 있다!
- 위 정리로부터 $Av_i = \sigma_i u_i$ 임을 알 수 있고, 이를 행렬로 압축하면
- $AV = U\Sigma$, 다시말해 우리가 기대하던 $A = U\Sigma V^T$ 를 얻을 수 있다!