Eigenspace, part 2
Singluar Value Decomposition
\(A \in \mathbb C^{m \times n}\)을 생각해보자. 이런 조건에서 아이겐 분해를 어떻게 활용할 수 있을까? 일단 \(A\)를 정방행렬로 만들어주어야 할 것이고, 이에는 두 가지 방법이 있다.
\[ \underbrace{A^T A}_{n \times n}, \overbrace{A A^T}^{m \times m} \]
아울러, \((A^T A)^T = A^T A\), \((AA^T)^T = A A^T\)가 성립하기 때문에 두 매트릭스 모두 normal 매트릭스다. 따라서 아래와 같은 개념화가 가능하다.
\[ A = \underbrace{ \begin{bmatrix} \vert & \dotsb & \vert \\ u_1 & \dotsb & u_m \\ \vert & \dotsb & \vert \\ \end{bmatrix}}_{m \times m} \overbrace{ \begin{bmatrix} \sigma_1 & 0 & \dotsb \\ 0 & \sigma_2 & \dotsb \\ 0 & 0 & \dotsb \\ \end{bmatrix}}^{m \times n} \underbrace{ \begin{bmatrix} -- & v_1^T & -- \\ -- & \vdots & -- \\ -- & v_n^T & -- \\ \end{bmatrix}}_{n \times n} = U \Sigma V^T \]
\(U\)를 통해 분해되는 부분을과 \(V\)를 통해 분해되는 부분을 다음과 같이 나타내보자.
\[ \begin{aligned} A A^T & = U \Lambda_l U^T \\ A^T A & = V \Lambda_r V^T \\ \end{aligned} \]
소문자의 \(l\)와 \(r\)은 각각 left, right를 뜻한다. \(U\)와 \(V^T\)를 명시적으로 적어보자.
\[ U = \begin{bmatrix} \vert & \dotsb & \vert \\ u_1 & \dotsb & u_m \\ \vert & \dotsb & \vert \\ \end{bmatrix}, \text{~where} \{ (\lambda_i, u_i) = \text{eigenvects}(A A^T) \} \]
\[ V = \begin{bmatrix} -- & v_1^T & -- \\ -- & \vdots & -- \\ -- & v_n^T & -- \\ \end{bmatrix}, \text{~where} \{ (\lambda_i, v_i) = \text{eigenvects}(A^T A) \} \]
이제 유사 대각행렬 \(\Sigma\)를 보자. 이 행렬은 \(m \times n\) 형태다.
\[ \sigma_i = \sqrt{\lambda_i}, \text{ where } \lambda_i = \text{eigenvals}(A A^T) = \text{eigenvals}(A^T A) \]
Change-of-basis
기저를 바꾸는 관점에서 다시 음미해보자.
\[ \vec y = A \vec x = U \Sigma V^T \vec x \]
- \(V^T \vec x\): \(V^T = \phantom{}\_{B\_{SVD}}[1]\_{B_S}\). 즉, \(B_{SVD} \leftarrow B_S\)를 수행한다.
- \(\Sigma\): 유사 대각행렬을 곱해 각 기저의 크기를 조절한다.
- \(U\): \(U = \phantom{}\_{B_{S}}[1]\_{B\_{SVD}}\): \(B_{S} \leftarrow B_{SVD}\)
즉, \(B_S \leftarrow B_{SVD} \leftarrow B_S\)를 수행한다.
Outer product
외적의 관점에서 이해하는 것도 흥미롭다. 일단 외적에 관해서 간단히 살펴보자. 벡터 \(u \in \mathbb R^m\), \(v \in \mathbb R^n\)이 있다고 할 때,
\[ u v^T \in \mathbb R^{m \times n} \]
외적의 rank는 어떻게 될까? 1이다. 직관적으로는 이해가 안될 수 있다.
\[ {\rm rank} (AB) \leq \min({\rm rank}(A), {\rm rank} (B)) = 1 \]
SVD 식을 다시 조립해보자. 일단 \(m \geq n\)을 가정하자.
\[ U \Sigma = \begin{bmatrix} \vert & \dotsb & \vert \\ u_1 & \dotsb & u_m \\ \vert & \dotsb & \vert \\ \end{bmatrix} \begin{bmatrix} \sigma_1 & 0 & \dotsb \\ 0 & \sigma_2 & \dotsb \\ 0 & 0 & \dotsb \\ \end{bmatrix} \]
\[ \begin{aligned} A & = U \Sigma V^T \\ & = \underbrace{ \begin{bmatrix} \sigma_1 u_1, \dotsb, \sigma_n u_n, \dotsc, 0 u_m \end{bmatrix}}_{U \Sigma} \begin{bmatrix} -- & v_1^T & -- \\ -- & \vdots & -- \\ -- & v_n^T & -- \\ \end{bmatrix} \\ & = \sigma_1 u_1 v_1^T + \dotsb + \sigma_n u_n v_n^T + \dotsb + 0 u_m v_m^T \end{aligned} \]
\(u_i v_i^T\)는 각각 1의 rank를 지니고 앞에 곱해진 singular value의 기저로 이해할 수 있다. 해당 기저들의 선형 결합으로 매트릭스 \(A\)를 다시 분해할 수 있다.
An application
이렇게 대각화를 할 때 어떤 이득이 있을까? 앞서 유사 행렬을 활용하면 행렬의 곱이 간단해진다는 점을 보았다. SVD에도 비슷한 이점이 있다. 이 외에 SVD를 써서 할 수 있는 중요한 이득이 있다. 계산량을 줄이는 것이다.
\(M \in \mathbb R^{1000 \times 2000}\)의 변환이 있다고 하자. 이 변환의 싱귤러 밸류들 많아야 1000개가 나올 것이다. 만일 이 1000개 중에서 3개를 제외하고 나머지 값이 0에 가깝다고 하자.
\(M\)이라는 변환의 근사값을 구하고 싶다면, 0에 가까운 값을 모두 0으로 둔다. 이렇게 바꾸면,
\[ M \approx \hat M = \hat U \hat \Sigma \hat V^T \]
- \(\hat U \in \mathbb R^{1000 \times 3}\)
- \(\hat \Sigma \in \mathbb R^{3 \times 3}\)
- \(\hat V^T \in \mathbb R^{3 \times 2000}\)
이렇게 근사값을 구하면 계산량이 많이 줄어들 것이다. \(M\)와 \(\hat M\) 사이의 힐베르트-슈미트 거리를 구하면,
\[ \Vert M - \hat M \Vert_{\rm HS} = \sqrt{\sum_{i=4}^{1000} \sigma_i^2} \]
이 값이 크지 않다면, \(M \approx \hat M\)으로 간주할 수 있다. 실제로 이미지 압축 등에서 많이 사용되는 방법이다.
LU
\(n \times n\) 정방 행렬에 대해서 \(A = LU\)를 수행할 수 있다. \(L\)과 \(U\)는 하방삼각 행렬과 상방삼각 행렬이다. 이렇게 매트릭스를 쪼개는 이유를 각각에 관해서 역행렬을 구하기 힘들기 때문이다. 즉,
\[ A \vec x = LU \vec x = b \Leftrightarrow U \vec x = L^{-1}b \Leftrightarrow \vec x = U^{-1}L^{-1}b \]
우선 LU가 가능하라면 \(A\)가 RREF으로 열의 교환 없이 환원될 수 있어야 한다.
Cholesky
\(A\)가 대칭이고 PSD 매트릭스라면 \(LU\) 분해는 더욱 단순해진다.
\[ A = L L^T \text{ or } A = U^T U \]
QR
\(A \in \mathbb R^{n \times n}\)일 때 이 매트릭스를 쪼개는 강력한 방법은 G-S 알고리듬을 활용하는 것이다.
\[ A = O U \]
- \(O\): orthogonal matrix
- \(U\): Upper triangluar matrix
보통 \(U\)를 right-triangular matrix로도 쓰기 때문에, 이를 \(QR\)로 표기하기도 한다. \(R\)의 경우 \(O\)의 컬럼 벡터를 하나씩 추가해가면서 계산하게 된다. 이는 G-S 알고리듬에서 하나씩 벡터를 빼가면서 계산하는 것을 구현할 수 있게 해준다.
Example
실제로는 어떻게 하는지 살펴보자. 먼저 \(A\)의 각 컬럼들을 두고, 두번째 열은 첫번째에 직교하게, 세번째는 첫번째와 두번째에 직교하게 행렬을 변형한다.
\[ A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} \]
\(O\) 혹은 \(Q\)를 구해보자. G-S 알고리듬을 활용하자.
\[ A = [a_1, a_2, a_3] \]
\(a_1\)과 직교하는 \(e_2\)를 구하면 아래와 같다.
\[ e_2 = a_2 - \dfrac{a_2 \cdot a_1}{\Vert a_1 \Vert^2} \]
다음으로 \(e_3\)는 \(a_1\)과 직교하고 동시에 \(e_2\)와 직교해야 한다. 따라서,
\[ e_3 = a_3 - \dfrac{a_3 \cdot a_1}{\Vert a_1 \Vert^2} - \dfrac{a_3 \cdot e_2}{\Vert e_2 \Vert^2} \]
이를 다시 길이 1로 표준화하면 \(Q\)를 구할 수 있다. 그리고
\[ Q^T A = Q^T Q R = 1 R \]
따라서 \(R\)은 \(Q^T A\)로 구할 수 있다.