이번 포스팅에서는 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에 대해서 자세하게 알아보도록 하자.

몇 일 조금 놀았더니 조금 오랫동안 포스팅을 못 했다. 그래도 열흘 밖에 안 되기는 했다. 열 흘을 전부 논 것은 아니지만.. 아무튼 포스팅을 해보도록 하자.

이번에 포스팅할 내용은 Orthonormal Vector와 Orthonormal Vector의 유용성이다. 우선 Orthonormal Vector에 대해서 알아보도록 하자. 우리는 아래와 같은 식을 만족하는 Vector를 Orthonormal Vector라고 한다. 

가령 아래의 Vector들은 Orthonormal vector이다.

위의 Vector q1과 q2는 서로 perpendicular하다. 그리고 q1과 q2의 크기가 모두 1이다. 따라서 q1과 q2는 Orthonormal vector이다.

Orthonormal vector를 공부하는 이유는 무엇일까? 결론적으로 말하면 다음 포스팅에서 나올 Gram-Schmidt Process를 공부하기 위함이다. 그렇다면 거기서 Orthonormal vector의 개념은 왜 쓰일까? 계산을 쉽게 한덴다.. 왜 계산을 쉽게 할까? 여기서 Orthonormal vector의 Usefulness가 나오니 집중해서 보기를 바란다.

Q라는 Orthonormal vector가 Column Space로 있는 matrix를 보자.

위의 식에서 T(Q)Q를 보면 뭔가 어디선가 많이 봤다는 생각이 들 것이다. 이전 포스팅에서 실컷 봤을 것이다. 우리가 하나의 Vector를 subspace에 projection 시킬 때 그 Projection Matrix를 아래와 같이 유도했었다.

위의 수식에서 A를 q로 바꿔보자. 그러면 마지막에 P = Q Inv(T(Q)Q) T(Q)가 되는데 T(Q)Q는 항상 Identity Matrix이므로, P = Q T(Q)가 된다. 뭔가 깔끔하게 떨어지니까 좋다. 그리고 같은 원리로 아래와 같은 식도 깔끔하게 줄어든다.

이렇게 깔끔하게 줄어드는 것을 바탕으로 Gram이라는 사람과 Schemidt라는 사람이 뭔가 대단한 것을 했나보다. 그 사람들이 무엇을 했는지는 다음 포스팅에 잘 알아보려고 한다.

계속 말하는 것이지만 확실히 선형대수 포스팅은 하나하나가 조금 짧은 것 같은 느낌을 많이 받는다. 하지만 뭔 상관이여!! 조금씩 조금씩 해나가면 되는거지!!

우리가 보통 "Presentation을 한다"라 하면 ppt 파일을 하얀 곳에 projector로 뿌려서 발표하는 것을 말한다. 여기서 projector가 하는 일은 화면을 벽에 뿌려주는 일이다. 제목에 나오는 Projection은 뿌려주는 의미의 Project를 의미한다. 아래의 그림에서 보면 vector b가 vector a에 project되어 vector p가 되었다.

여기서 e는 error의 e인데, 왜 갑자기 error? 나중에 설명하기로 하자. 아무튼 위의 그림을 보면 아래와 같이 수식을 표현할 수 있다.

참고로, 위의 수식에서 는 X-HAT이라고 읽고 편의상 아래에서는 X^로 표현하려한다.

자, 이제 우리는 vector a와 vector b가 있으면 vector p를 구할 수 있다. 예제를 통해서 구해보자. 위의 그림에서 a = (3.1)로 놓고 b = (1,1)로 놔보자.

이런 식으로 써먹는단다. 자 지금까지 한 것은 Projecting onto a line이다. 우리는 (3,1)이라는 line에 vector b를 project했다. 이제부터는 subspace에 projecting을 할 것이다. 즉 어떤 공간에(subspace)에 projecting을 한다는 것이다. 

subspace의 정의를 생각해보자. subspace는 하나의 vector가 linear combination으로 이루고 있는 공간이다. n개의 vector a1, a2, ..., an이 A라는 subspace를 이루고 있다고 하면 c1a1 + c2a2 + ... + cnan이 A에 속해야 된다. 우리는 vector b를 A에 projecting 시킬 것이다. 그러면 아래와 같은 그림이 나오게 된다.

subspace A위에 있는 모든 a1, ..., an이 vector e와 Orthogonal하게 된다. 따라서 아래와 같은 식이 성립하게 된다.

e = b - aX^이므로 

위의 식을 행렬화하면 아래와 같이 된다.

마지막 식은 중요한 식이다. 막 A에 T(A)에.. 역행렬A에 막 아주 난리가 났다. 조금 머리가 많이 아프다. 아래의 예제를 통해서 이해해보자.

위의 결론으로 봤을 때, 우리는 particular vector b를 알고 있었다. b = (6,0,0) 이었다. 이 값을 통해서 우리는 X^를 알고 vector p를 구했다. 그리고 기존에 증명한 수식을 이용해서 projection matrix P를 구했다. 즉 마지막에 보이는 3x3 matrix P에 어떤 3x1 matrix b를 곱하면 그 vector p는 A의 column space(subspace)에 project되게 되는 것이다.

후 이번 포스팅은 내용의 난이도 보다도 수식 작성하고 하는 것이 조금 귀찮고 해서 오래걸렸다. 몇 줄 안되는 포스팅이지만 난 무려 3시간씩이나 걸렸다.

다음 포스팅에서는 최종적으로 Ax = b with no solution x를 풀어볼 것이다. 답이 없는 Ax = b를 풀겠다고? 무슨 말인지 다음 포스팅을 통해 확인해보면 된다.