Gram-schmidt Orthogonalization

 

어떤 임의의 linearly independent 한 vector set이 주어졌을 때, orthonormal한 basis vector로 변환을 시켜주는 것이 중요하다. 이러한 과정을 수행하는 것이 Gram-schmidt Orthogonalization 이다.

 

위의 말을 이해하기 위해 general subspaces에 Projection 시키는 과정을 살펴보자.

 

 

 

 

 

n 차원의 벡터 $x$가 있고, m 차원의 subspace $U$로 Orthogonal Projection을 시켜보도록 하자. 예를 들어 $U$가 2 차원이라고 해보자. 2 차원이면 basis veocor $b$ 가 2개 존재할 것이다. 그리고 원래 vector space 에 $x$라는 vector가 있을 때, 이 vector를 Orthogonal Projection한다는 것은 $U$에 Projection 된 vector $\pi_{U}(x)$가 있을 때, $x - \pi_{U}(x)$와 Orthogonal 해야한다는 것을 의미한다. 그리고 subspace $U$에 존재하는 $\pi_{U}(x)$는 $b$ 기저벡터들의 선형결합으로 표현이 가능해야한다.

 

 이 부분을 generalize 해보자. $U$가 m차원이니 basis vector를 $(b_{1}, ... ... , b_{m})$ 라고 하면, $U$로 projection된 vector는 이 $b$ 들의 선형결합으로 표현이 되기 때문에 $\pi_{U}(x) = \sum_{i=1}^{m}\lambda_{i}b_{i}$ 로 표현할 수 있다.

 

1. coordinate $\lambda_{i}$들을 찾아보자. 

 

 $\pi_{U}(x)$ 를 $B\lambda$ 로 나타낼 수 있다. 원래의 vector 와 projection된 vector와의 차이인 $x - \pi_{U}(x)$는 $U$의 모든 basis vector들과 orthogonal 해야한다. 그렇기 때문에 $B(x - B\lambda)=0$이 성립하고, $B^{T}(x - B\lambda) = 0$ 와 같고, 풀어서 전개하면 식(3.56)과 같이 $B^{T}B\lambda = B^{T}x$와 같게 된다.

식(3.56) $B^{T}B\lambda = B^{T}x$ 과 같은 equation을 normal equation이라고 부른다(linear regression에서 볼 수 있는 equation). 

 이제 $\lambda$만 남겨주기 위해서 양변에 $((B^{T}B))^{-1}$를 곱해준다. (inverse가 존재하는지가 가정되어 있어야한다. $B^{T}B$는 full rank이다.) 그러면 아래의 식 (3.57)과 같게 된다.

 

$\lambda$를 구했으니 $\pi_{U}(x) = B\lambda$ 에 대입을 하게 되면 식(3.58)을 얻게 된다.

위의 식에서 $x$ 앞에 곱해진 matrix는 projection matrix에 해당하므로 projection matrix는 식(3.59)와 같게 된다.

projection vector $\pi_{U}(x)$는 여전히 n 차원의 vector이다. 하지만 이제 더이상 n개의 coordinate을 전부 사용해서 data를 표현할 필요없이 subspace상에서의 m개의 coordinate로 이 vector를 표현할 수 있게 된다.

 

 

 

어떤 vector space상에 존재하는 vector가 있을 때, 얘를 subspace로 orthogonal projection하는 과정을 살펴보았다. 최종적으로 식 (3.59)의 $B(B^{T}B)^{-1}B^{T}x$를 보면 알겠지만, 여기서 계산하기 제일 귀찮은 부분은 inverse를 구하는 term 부분이다. $U$를 span하는 basis들은 unique하지 않는데, 여기서 이 basis들이 특별한 basis를 취할 수 있으면, 이 부분을 간단하게 구할 수 있다. 그게 바로 subspace $U$를 span 하는 orthonormal basis를 찾으면 된다. 

왜냐하면  orthonormal basis를 찾고, $B$라는 basis가 orthonormal basis로 이루어져 있다면, $B^{T}B = I$ identity matrix가 되고, 식(3.58)의 $B(B^{T}B)^{-1}B^{T}x$ 는 $BB^{T}x$ 가 된다. 

 

이제 글 제일 위에 했던 말을 다시 한번 상기시켜보자.

어떤 임의의 linearly independent 한 vector set이 주어졌을 때, orthonormal한 basis vector로 변환을 시켜주는 것이 중요하다. 이러한 과정을 수행하는 것이 Gram-schmidt Orthogonalization 이다.

여기서 목표는 vector space $V \in \mathbb{R}^{n}$에서 n개의 linearly independent한 basis가 주어져 있을 때 $(b_{1}, ... ,b_{n})$, 이러한  $(b_{1}, ... ,b_{n})$를 orthogonal 또는 orthonormal한 basis vector($u_{1}, ... ,u_{n}$)로 transformation시켜주는 것이다.

 

이러한 orthonormal한 basis들은 항상 존재한다. 왜냐하면 $b$들과 $u$들이 span하는 공간은 같은 공간이기 때문이다.

 

Gram-schmidt Orthogonalization orthogonalization 방법은 iterative 하게 basis들을 orthogonal하게 하나하나 만들어가는 구성으로 이루어져 있다.

 일반적인 과정은 아래의 식 (3.67), (3.68)을 보면 된다. 

먼저 $u_{1}$에 $b_{1}$을 하나 취한다.

그리고 $u_{2}$를 어떻게 계산을 하냐하면, 앞에서 $u_{1}$이라고 하는 basis vector가 span하는 subspace로 $b_{2}$라고 하는 basis를 orthogonal projection시키는 것이다. 

 그렇게 되면 원래의 $b_{2}$와 orthogonal projection 된 vector $\pi_{span[u_{1}, ... ,u_{k-1}]}(b_{k})$와의 차이가 $u_{1}$과 orthogonal하게 된다.

 $u_{3}$는 $u_{1}$과 $u_{2}$가 span하는 subspace 상으로 $b_{3}$를 projection시키고, 원래의 $b_{3}$에서 projection된 vector를 마찬가지로 빼주면, 최종적으로 $u_{3}$는 $u_{1}$, $u_{2}$와 orthogonal 해지게 된다.

 

이러한 과정을 n개의 basis를 찾을 때까지 iterative하게 만들어 나가는 방법이다.

 

 

 

예제를 살펴보자.

(a) 처럼 non-orthogonal basis vector $b$ 가 2개 있다고 가정하자. 그리고 (b)를 보자. 우선 $u_{1}$을 $b_{1}$으로 두도록하자. 그런 다음 $u_{1}$이 span하는 subspace에 $b_{2}$의 projection vector는 $\pi_{span[u_{1}]}(b_{2})$ 이 된다. 이는 원래의 $u_{1}$과 orthogonal 하게 된다. 최종적으로 $u_{2}$ 는$b_{2} - \pi_{span[u_{1}]}(b_{2})$가 된다.

 

 이제 $u_{1}$과 $u_{2}$는 orthogonal 한 basis가 되었다. 

 이번에는 $u_{1}$과 $u_{2}$가 span 하는 plane 상으로 $b_{3}$를 projection 시키고, 그 subspace에 orthogonal 한 $u_{3}$를 구해낼 수 있게 된다. 이 과정을 계속 반복하게 되면 원래 orthogonal하지 않은 vector들을 orthogonal하게 만들 수 있고, orthonormal하게 만들기 위해 각각의 norm으로 나누어 만든다.

 

 

 

 

 

 

 

지금까지는 vector subspace에 projection했을 때를 보았고, 이번에는 affine subspace에 임의의 vector를 orthogonal projection시키는 것을 알아보자.

 

우선 affine subspace 를 $L = x_{0} + U$ 라 하자. affine subspace는 vector subspace $U$가 주어질 때, 여기에 $x_{0}$라는 offset에 해당되는 vector가 더해진 subspace를 말한다. 그리고 $U$의 basis vector를 $b_{1}, b_{2}$라고 하자.

 

 위의 그림처럼 $b$로 span되는 $U$라는 space가 있고, 여기 모든 vector들에 $x_{0}$를 다 더하면, $L$이라는 affine space가 될 것이다.

 이 때, $x$라는 임의의 vector가 있다고 해보자. $x$라는 vector를 affine space $L$에 orthogonal projection시키고 싶은 것이다. 이를 하는 방법은 offset $x_{0}$를 원점으로 위치시킨 다음에, orthogonal projection을 하고, 그 다음에 원상복구 시키면 된다.

 그림 (b)처럼 $x$에서 $x_{0}$를 빼주고, $L$에서 $x_{0}$를 빼주면, 그게 바로 vector subspace가 된다. 그리고 원점이 맞춰지게 된다. 그리고 이제 $U$를 $L - x_{0}$라고 볼 수 있다. 여기서 앞서 했던 orthogonal projection을 수행하는 것이다. $x - x_{0}$가 $\pi_{U}(x - x_{0})$로 projection이 될 것이고, 그 다음에 projection 된 vector에다가 다시 $x_{0}$를 더해주면 된다.

 원래 전체 vector에서 $x_{0}$를 빼줘서 원점을 맞추고, 거기서 projection 시킨 다음에, 다시 $x_{0}$를 더해서 원상복구 시키는 것이다.

 

 그렇게 되면 $L$이라고 하는 affine subspace가 원래의 위치로 돌아가게 되고, 원래의 origin 원점은 (c)의 보라색 벡터가 가리키는 곳으로 가게 된다. 그 지점에서 앞에서 구했던 $\pi_{U}(x-x_{0})$ vector를 볼 수 있고, 여기다가 $x_{0}$만큼 더해주면 된다. 최종적으로 origin 원점에서 $\pi_{L}(x)$ point까지 향하는 vector를 구할 수 있게 된다. 이 벡터가 $\pi_{U}(x-x_{0}) + x_{0}$이 된다. 이것이 affine space $L$에 orthogonal projection 된 projection vector가 된다.

 

projection 이라는 것이 어떠한 성질을 가진 linear mapping인지 이해를 해야한다. 그 중에서도 orthogonal projection 하는 과정에 대해서 천천히 살펴보면서 익혀보자.

 

 

 

 

 

 

 

 

ref)

MML book