동차 선형 방정식을 SVD로 풀 수 있는 이유

동차 선형 방정식을 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}$의 마지막 열이 됩니다.