동차 선형 방정식을 SVD로 풀 수 있는 이유
Solving homogeneous linear equation using SVD
최소 자승법을 이야기 하면서 의사 역행렬을 이용해 over-constrained eq.을 푸는 방법을 소개 했는데 정작 왜 그것이 정답이 되는지는 얼버무리고 넘어간 것 같아서 이 글을 게시합니다.
SVD(Singular Value Decomposition)은 선형 대수학에서 매우 중요한 의미를 가집니다. eigenvalue, eigenvector가 중요한 것처럼 singular value들은 eigenvalue와 관계가 있기 때문입니다. 컴퓨터 비전이나 기계 학습에서 선형 대수학이 빠질 수 없는 이유는 바로 선형 변환에 불변하는 특성을 가지는 eigenspace 해석을 통해서 중요한 성질을 구할 수 있기 때문입니다. PCA(Principal Component Analysis)도 결국 SVD를 이용해서 주요 성분을 얻어내는 것이고, 기계 학습에서 sparse coding으로 중요한 정보 만을 이용해서 영상을 분류하는 방법에도 적용될 수 있습니다.
행렬 \(\mathbf{A}\)의 singular value를 \(\sigma\)라고 하면, \(\mathbf{A^*A}\)와 \(\mathbf{AA^*}\)의 0이 아닌 eigenvalue, \(\lambda\)와 \(\sigma\) = \(\sqrt{\lambda}\)의 관계를 가집니다. 여기서 \(\mathbf{A^*}\)는 \(\mathbf{A}\)의 켤레전치행렬(conjugate transpose) 입니다. 간단하게 상수라고 생각하면 제곱 한 것을 분해한 것과 그냥 분해한 것의 차이 정도로 대략 감을 잡으시면 될 것 같습니다.
그럼 SVD로 어떻게 동차 방정식의 해를 구할 수 있는지 보겠습니다.
\(\mathbf{Ax} = 0\)
와 같은 동차 방정식이 주어지는 경우, 자명하지 않은 해(non trivial solution)을 구한는 것이 목적입니다. (\(\mathbf{x}=0\)이면 항상 참이 되니 자명한 해이므로 관심이 없습니다.)
그래서 자명한 해가 아닌 해를 구하기 위해서 제약 조건을 줍니다. 보통은 \(||\mathbf{x}||=1\) 과 같이 벡터의 크기를 정해줍니다. 우변이 0이기 때문에 벡터의 크기는 아무래도 관계 없기 때문입니다.
이제 행렬 \(\mathbf{A=UDV^T}\)로 분해하면,
\(\mathbf{||UDV^Tx||=||DV^Tx||}\) - ①
\(\mathbf{||x||=||V^Tx||}\) - ②
로 둘 수 있습니다. 왜냐하면, SVD로 구한 \(\mathbf{U, V^T}\)행렬은 각 열이 모두 orthogonal 하기 때문입니다. 이 특성은 회전 행렬과 같습니다. 벡터 공간에서 임의의 벡터를 아무리 회전 시켜도 그 크기가 변하지 않는다는 것을 생각해보면 식 ①, ②가 성립하는 것을 알 수 있습니다.
\(\mathbf{y=V^Tx}\) - ③
을 도입해 보면, 최초의 문제는 결국 '\(\mathbf{||Dy||}\)를 최소화하되 \(\mathbf{||y||}=1\)을 만족 시켜라.'는 문제로 바뀌게 됩니다.
여기서 SVD의 특성을 다시 한 번 생각해보면, 분해된 행렬 \(\mathbf{UDV^T}\)에서 \(\mathbf{D}\)는 대각 행렬이고 원소들은 singular value가 큰 순서대로 정렬되기 때문에 \(\mathbf{||Dy||}\)를 가장 작게 만들면서 \(\mathbf{||y||}=1\)을 만족 시킬 수 있는 방법은 \(\mathbf{y}=(0, 0, ..., 0, 1)^T\)로 두는 것입니다.
그러므로, \(\mathbf{x=V^Ty}\)는 결국 \(\mathbf{V^T}\)의 마지막 열이 됩니다.
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)
.gif)