Gram-schmidt process를 알아보자.

개요

Gram-schmidt가 뭔지 알아보자.

그리고 Gram-schmidt가 진행되는 과정을 살펴보자.

과정을 살펴보고 마지막엔 Gram-schmidt를 통해 얻은 벡터에 대해 알아보자.

 

Gram-schmidt란 뭘까?

우리는 Ax=b의 해가 존재하지 않을 때 Least square로 최적의 솔루션을 얻을 수 있는 수식인

x = (A^TA)^-1A^Tb를 얻었다.

 

이 과정에서 우리는 무엇을 알 수 있었나?

뭔가 최적의 해를 구하려면 b와 최대한 가까운 지점을 찾아야 한다는 사실을 알았다.

위에서의 x를 이용하면 b = Ax로 최적의 b hat 지점을 찾을 수 있었으니까.

여기까지는 Least square의 내용이었다.

Gram-schmidt와 무관하기는 하다.

 

그래도 Least square에서 gram-schmidt 과정으로 끌어올 수 있는 사실은 b가 수선의 발을 내린 지점을 찾는 일이

최적의 solution을 찾는 일이라는 것이다. 그리고 수선의 발을 지나는 모든 벡터와 orthogonal하다는 것이다.

 

그래서 gram-schmidt 과정은 어떤 역할을 하는가?

우리가 가진 linearly independent한 벡터들을 모두 orthogonal하게 만들어준다.

 

왜 굳이 linearly independent한 벡터들을 orthogonal하게 만들어 주어야 하나?

컴퓨터로 역행렬을 계산하는 게 시간이 많이 걸리기도 하고 계산상 잘못된 답이 도출될 수도 있기 때문이다.

-> 역행렬은 나누기 연산이라 계속 나누기 연산을 하면 계산이 부정확할 수 있다.

그 예로, x = (A^TA)^-1A^Tb의 (A^TA)^-1부분을 들 수 있다. 여기에서 A를 orthonormalize하여 A의 norm이 1이 됐다고 해보자.

그리고 A를 u로 바꿔부른다고 해보자.

그럼 저 부분은 그냥 사라지고 x = u^Tb가 된다.

이렇듯 계산이 용이해진다.

 

Gram-schmidt는 어떻게 진행될까?

gram-schmidt 과정을 통해 linearly independent한 벡터가 orthogonal 혹은 orthonormal한 벡터로 어떻게 바뀌는지 알아보기 전에,

gram-schmidt를 하기 위한 orthogonal projection을 하는 벡터를 얻는 수식을 알아보자.

이 수식이다.

만약 u가 unit 벡터라면?

 

y hat = (y^Tu)u이다.

 

이 수식을 통하면 어떤 벡터를 얻을 수 있는가?

바로 저 화살표가 가리키는 u와 y hat의 사이의 벡터를 구할 수가 있다.

 

이제 y hat을 구했으니 벡터 u와 orthogonal한 벡터를 만들 수가 있다.

어떻게 만드냐?

y에서 y hat을 빼주면 된다. 그게 바로 우리가 새로 만든 orthogonal한 벡터이며 이 벡터는 u와 수직을 이룬다.

그리고 orthogonal한 벡터를 새로 만들어줄 때 중요한 조건이 있다.

바로, 기존의 벡터 u와 y가 span하던 공간을 방금 만들어준 orthogonal한 벡터와 벡터 u가 그대로 span할 수 있어야 한다.

 

다행히도 우리가 만든 벡터와 벡터 u는, y와 u가 span 하던 2차원 공간을 그대로 span할 수 있다.

여기까지가 gram-schmidt 과정을 거쳐 orthogonal한 벡터를 얻는 과정의 대략적인 설명이었다.

이러한 과정을 바로 gram-schmidt 과정이라고 부를 수 있다.

즉, orthogonal한 벡터를 얻는 과정인 것이다!

 

여기에서 우리가 만든 orthogonal한 벡터를 v라고 할때 v를 normalize 해주면 v는 orthonormal한 벡터가 된다.

 

실습 전 정리

gram-schmidt process를 코드로 실습하기 전에 과정을 간단하게 정리해보자.

어떻게 gram-schmidt 과정이 흘러간 것이냐?

간단하게 말하면,

(기존의 linearly independent한 벡터를 x1, x2

그리고 새로 얻은 orthogonal한 벡터를 v1, v2

새로 얻은 orthonormal한 벡터들을 u1, u2라고 하겠다.)

 

1. 벡터 하나를 고정시킨다. x1을 고정시키겠다. 이제 이를 v1이라 부르자.

 

2. Gram-schmidt orthonormalization을 하기 위해 v1을 normalize한다.

이제 v1은 길이가 1이 됐고, v1을 u1이라고 부르겠다.

 

3. u1을 x2에 orthogonal projection을 해줄 시간이다.

위에서 구했던 그 수식을 이용하면 바로 x hat 벡터를 얻을 수 있다. 

 

4. v2에서 v hat을 빼주면, 새로운 orthogonal한 벡터를 얻을 수 있다.

마무리로 v2를 normalize까지 하면 길이가 1이고 v1과 수직인 orthonormal한 u2를 얻을 수 있다.

코드를 통한 실습

 

식이라서 어려워 보이지만 그냥 위에 있는 1, 2번 과정이다.

고정시키고 normalize 하는 거다.

 

 

그리고 다음 과정은 수식을 통해 orthogonal projection을 한 벡터를 얻어주면 된다.

즉, x2에 사영한 벡터를 얻어주자. 3번 과정이다.

 

그럼 끝났다고 볼 수 있다.

이제 x2에서 x2 hat을 빼주면 orthogonal한 벡터를 얻을 수 있다.

마무리로 normalize까지 해주면, u2를 얻는다!

 

그림을 통해 이해하자

벡터가 3개지만 세 번째 벡터인 x3는 사용되지 않았으니 상관없다.

 

---

이렇게 우리는 gram-schmidt가 뭔지

linearly independent한 벡터가 왜 gram-schmidt 과정을 거쳐야 하는지

어떤 과정을 통해 orthogonal한 벡터와 orthonormal한 벡터가 얻어지는지 즉, gram-schmidt가 어떻게 흘러가는지 알아보았다.