[Linear Algebra] Gram-Schemidt Process and Factorization to A = QR

이번 포스팅에서는 Gram-Schemidt Process를 공부해보자. 그리고 나아가서 A = QR이라는 General Formula를 증명해볼 생각이다. 우선 Gram-Schemidt Process이다. 

Gram-Schemidt Process는 기본적으로 orthonormal 하지 않은 independent vector들을 orthonormal하게 만들기 위함이다. 어떻게 하는지 아래의 두 개의 independent vector a와 b를 보자. (Independent vector 두 개 짜리를 보고 세 개 짜리, ...., n개 짜리도 볼 것이다.)

위의 a와 b는 independent하다고 하고 이야기를 해보자. a와 b는 반드시 서로 perpendicular하다는 보장은 없다는 말이다. 우리는 이 두 vector를 orthonormal하게, 즉 서로 perpendicular하며 그 크기가 1이 되도록 할 것이다. 우선, a와 b를 서로 perpendicular한 vector A와 B로 바꾼다고 생각해보자. 우선, 고정으로 a를 A로 놔보자. 그 다음에 vector b를 A에 perpendicular한 B로 바꾸려고 한다. 그러려면 아래와 같이 b를 a에 projection 하는 과정이 필요하다.

우리가 필요한 A와 B는 위와 같이 구할 수 있다. A와 B는 갈색으로 구분해두었다. 지금 이 vector A와 B는 서로 orthogonal하지만(=perpendicular) 아직 orthonormal 하지는 않는다. 크기가 1이 아니기 떄문이다. 크기가 1이 되게 하기 위해서는 vector A와 B를 크기로 나누어 주어야 한다. 아래와 같다.

이제 위의 q1와 q2는 서로 orthonormal한 vector가 되었다. 이제 vector를 세 개로 놓고 이야기해보자.

제일 왼쪽 그림은 위에 그린 A와 B이다. 그 옆에 vector c가 추가된 것을 보자. 기본적으로 vector c는 a와 b에 perpendicular하지 않다. 그렇지만 이 c를 AB Plane에 projection하면서 vector C를 갖게 되고 그 C는 AB Plane에 perpendicular하게 된다. 그 vector C를 |C|로 나누면 (q1과 q2에 orthonormal한) q3를 갖게 된다는 것이다. 가장 오른쪽 그림에 있는 q1, q2, q3는 서로 orthonormal하게 된다. 그 말은 q1, q2 , q3의 크기도 각각 1이라는 뜻이다.

이것이 Gram-Schemidt Process이다. 서로 Independent한 vector n개를 주었을 때, 그 n개의 vector들을 하나씩 하나씩 projection하여 서로 perpendicular한 n개의 vector를 만든 후 그것을 각각의 길이로 나누어 최종적으로 orthonormal한 vector를 만드는 것이 Gram-Schemidt Process이다.

예제를 봐보자.

마지막에 [CHECK]부분에서 서로 perpendicular하는지를 검토하는 과정을 잊지 말자.

자 이제 마지막이다. Factorization A = QR을 알아보자. 결론은 이렇다. 모든 mxn matrix A with independent column은 QR로 표현될 수 있다는 것이다.

흠... 사실 이것을 깔끔하게 A = QR로 나눌 수 있음을 증명할 수 있으면 좋겠는데, 아직 나도 증명과정은 정확하게 잘 모르곘다. 우선 이 부분은 그렇다고 치고 너머가려한다.

자 이제 마지막 하나를 알아보고 새로운 파트를 공부해보도록 하자. 지금까지 우리가 vector e라고 계속 계속 말하고 다녔다. 그리고 이 vector e는 error의 e라고도 했다. 그 error가 갑자기 무슨 뜻일까?

전전 포스팅에서 마지막에 Ax = b with no solution을 풀어보겠다고 마지막에 이야기했었다. 이 말의 정체는 실제로 푸는 것이 아니라 best solution을 구하겠다는 것이다. 즉, Ax = b를 만족하는 가장 근사치 x를 구하겠다는 뜻이다. 

위의 Y = C + Dt 식을 보면 세 개의 점 중에서 어느 하나도 지나가지 않지만 그 세 개의 점과 가장 가까이 하고 있는 선으로 보인다. 우리는 이 선에서 C와 D를 구한 후 Ax = b를 만족하는 Best Solution을 구했다고 말하는 것이다. 이것을 구하는 방법이 바로 우리가 지금까지 했었던 Projection이다. (1,1), (2,2), (3,2)을 Y = C + Dt에 Projection시키는 것이다. 이제 조금씩 error가 무슨 error를 뜻하는지 감이 오기 시작할 수도 있겠다. 

위의 그래프를 조금 확대시켜봤다. (1,1)과 그 점을 Y = C + Dt에 Projection시킨 점의 차이가 발생하는데(vector e) 그 차이를 우리는 error라고 부르는 것이다. 왜냐면 정확한 값이 아니라 단순히 Best Solution, Closest Solution일 뿐이니까.

뭔가 정확하게는 모르겠지만, Projection이 Data Mining에서 유용하게 쓰일 것 같은 느낌적인 느낌이 든다. 왜냐면 여러가지의 데이터가 주어졌을 때 그것들의 최대 근사치를 구하는 방법으로 활용될 수 있을 것 같다는 느낌이 든다. 음 단순히 나만의 느낌일 뿐이니 이 말은 신뢰하지 않기를 바란다.

다음 포스팅에서는 Determinant에 대해서 자세하게 알아보도록 하자.