(선형대수학) 9-2. Gram-Schmidt 방법

이번 시간에는 그람-슈미츠 방법(Gram-Schmidt Process)에 대해서 알아보자.

 

일단, 그람-슈미츠 방법이 무엇을 하는 과정인지 살펴보자.

 

목표

주어진 Independent Vector들이 이루는 Space의 Orthonormal Basis를 구해보자!!

 

---

먼저, 왜 이런 Orthonormal Basis를 찾으려고 하는지 잠깐 생각해보자.

=> 행렬(선형변환)에 의해서 변환된 좌표계에서

=> Standard Basis를 알면 벡터를 표현하기 편하다!!

=> 이 Standard Basis 역할을 그대로 해주는 것이 Orthonormal Basis!

 

ex) 다음과 같은 변환을 생각해보자!

이미 알고 있듯이 이 변환은 Theta만큼 시계 반대방향으로 돌리는 회전변환이다.

변환 전의 Standard Basis는 [1,0], [0,1]이다.

=> 변환 후의 Standard Basis는 [cos theta, sin theta], [-sin theta, cos theta]가 된다. => Orthonormal Basis이다!

그러면 주어진 벡터 [1,2]는 변환 전과 후에 표현 방식이 어떻게 바뀔까???

표현 방식이 다음과 같이 바뀐다는 것을 말한다!

물론, 이 예시로 유용성은 파악하기 어렵지만, 느낌만 보자!!

---

그럼 지금부터 Orthonormal Basis를 찾기 위해서 Gram-Schmidt 방법을 소개한다!

 

1. 먼저 Independent Vector a_1,a_2,...,a_n이 주어져 있다고 하자!

(Independent가 아니면, Space로 Span할 때, Redundant한 Vector가 존재! => NO)

그러면 우리가 원하는 Orthonormal Basis는 n개의 성분을 가지고 있고, 각각 q_1,q_2,...,q_n이라고 하자.

 

2. a_1으로부터 q_1을 뽑아내자!

=> 그냥 Norm이 1이면 된다! => Normalize!

 

3. q_2를 뽑아내기 위해서, a_2를 이용하자!

(a) a_1과 a_2가 Independent => a_2에는 a_1으로는 표현할 수 없는 성분(Orthogonal)이 존재한다.

=> Least Square Method를 생각해보자!

=> 아래 그림에서 a_1은 평면 위에 존재하는 벡터, a_2가 b라고 하자...

=> e는 a_1(q_1)과 수직! => e를 가지고 q_2를 만들면 된다!

 

(b) (앞에서 b를 평면(여기선 q_1이 이루는 Space)으로 Projection하는 Matrix를 P라고 했었다!!) 이를 이용하면

(q_1^Ta_2 =  내적 -> 실수이므로 순서를 바꿔버릴 수 있다!)

4. q_3을 뽑아내기 위해서 3번을 반복하자!

(a) a_3는 a_1과 a_2와 Independent

(b) 여기서도 a_3를 q_1, q_2가 이루는 Space로 Projection하는 Matrix를 생각해보면...

(위에서 P를 실제로 계산해보면, 저런 식으로 분해가 가능하다!)

 

5. 이를 q_n까지 계속 반복하면 된다!!

(NOTE)

---

정리하자면,

=> Gram-Schmidt 방법은 Orthonormal Basis를 찾는 방법인데

=> Least Square Method를 통해서 구한 "Orthogonal Vector"를 Normalize하면 된다!!

 

---

조금 더 나아가서 QR Decomposition에 대해서 살펴보자.

 

위의 일반화된 경우에서

e_j는 결국 q_j로 Projection된 a_j의 성분을 말하므로 아래와 같이 a_j를 작성할 수 있다.

즉, a_j를 Basis={q_1,q_2,...,q_j}로 나타낼 수 있다!!

 

모든 a_j를 이러한 방식으로 작성할 수 있으므로, 이를 행렬로 정리해보면

즉,

Independent Vector로 이루어진 행렬 => Full-Rank 인 경우(심지어, 정사각행렬일 필요도 없다!!)

=> Orthogonal Matrix와 Upper Triangular Matrix로 쪼갤 수 있다!! 

(NOTE)

특히 저 R은 Upper Triangular Matrix이므로, 정사각행렬이고 INVERTIBLE이다!!!

 

이러한 Decomposition을 QR Decomposition이라고 한다!

 

---

QR Decomposition을 이용하면 Least Square Method를 다음처럼 사용할 수 있다!!

우리가 앞에서 Gauss-Jordan Form에 대해서 보았을 때, Upper Triangular Matrix의 경우

=> 저 x_hat을 구하는 과정이 아주 심플했다!!

=> 빠르게 x_hat을 구할 수 있다! (물론, Gram-Schmidt 과정으로 Q를 구하는 것이 필요하지만...)

 

---

이 Gram-Schmidt 과정과 QR Decomposition은

Fourier Transformation을 빠르게 계산할 수 있는 Fast Fourier Transformation(FFT)에도 이용된다!

=> Fourier Transformation을 수치적으로 계산할 때는 적분 이슈를 피하기 위해서 대부분 FFT를 사용할 것이다.

(물론, 이용하는 입장에선 당연히 직접 FFT를 계산하는 코드를 짜는 일은 없고, Matlab 등에서 fft 함수나 ifft(Inverse Fast Fourier Transformation)을 쓰게 된다.)