Gram-Schmidt Process (그람 슈미트 과정)

Definition

Gram-Schmidt: 내적 공간 (inner product space)에서 유한 개의 선형 독립 벡터 집합을 정규 직교 기저 (orthonormal basis)로 변환하는 방법입니다.

때문에 그람 슈미트 과정 (Gram-Schmidt Process) 또는 그람 슈미트 단위 직교화 (Gran-Schmidt orthonormalization)이라고 부릅니다. 

 

Why?

그람 슈미트 과정의 필요성은 다음과 같습니다. 흔히 우리가 다루는 3차원 공간에는 x, y, z 축이 있으며 각 축에 대한 기저가 존재합니다. 이것들을 우리는 standard basis라고도 부르며 해당 기저들은 서로 독립이기 때문에 다른 벡터를 표현할 때 basis의 조합으로 표현이 가능합니다.

3차원에서의 standard basis

standard basis와 같이 직교성을 갖는 기저는 많은 연산과정에서 편리하다는 장점이 있습니다. 즉 직교 기저에 의해서 생성되는 공간의 벡터들을 표현하기 위해서 기저에 특정한 가중치들을 가진 선형 결합으로서 쉽게 표현이 가능한 장점이 생깁니다. 

Gram-Schmidt과정 또한 어떤 벡터들이 span하는 공간에 대해 공간을 대표하는 basis를 찾는 과정입니다. 

Gram-Schmidt 과정을 통해서 나온 basis의 특성은 다음과 같습니다. basis끼리 직교 (Orthogonal)이며 정규화된 (Normalized) 값입니다. 즉 정규 직교 (Orthnormal) basis를 얻게 됩니다. 

*직교 (Orthogonality): 두 벡터의 내적이 0값을 가지는 것 (또는 선형 독립일 때)

*정규화 (Normalization): 벡터를 벡터의 norm으로 나눈 것 (때문에 정규화된 벡터는 최대 크기가 1 이하로 됨)

 

 

2D example

아래 그림을 보겠습니다. 우선 내적 공간 V의 기저 {v1, v2}가 주어져 있습니다. 

[1] Gram-Schmidt 과정의 기본 원리

v1과 v2는 선형 독립이며 이때 v1과 v2가 만들어내는 벡터 공간의 직교 벡터는 u1과 u2입니다. 그리고 u1과 u2를 단위 벡터 (또는 정규화) 생성 과정을 통해서 정규 직교 기저 (Orthonormal basis)은 e1과 e2가 되며 해당 e1과 e2를 찾는 과정이 Gram-Schmidt입니다. 

순서는 다음과 같습니다. 

1. 먼저 하나의 기준 벡터를 선정합니다.

임의의 벡터 u1은 제시된 벡터와 동일하게 둡니다 (u1 = v1) 

2. u1에 수직 (Orthogonal)한 벡터인 u2를 찾기 위해서 먼저 v2를 v1 (또는 u1)에 정사영 (Projection)합니다.

정사영된 벡터를 v2에 빼줌으로써 u2를 찾을 수 있습니다.

3. u1과 u2를 모두 찾았으니 정규화를 합니다. 

*1번 과정에서 u2 = v2로 시작을 해도 가능하지만, 반드시 v1과 v2를 사용해야 합니다. 아무런 벡터를 잡고 Gram-Schmidt를 진행할 수는 없으며 u는 v 벡터들을 생성하는 직교 기저이어야만 v- proju(v)값이 v공간에 속할 수 있기 때문입니다
(부분 공간에 포함).

 

 

3D example

v1, v2, v3의 벡터가 있을 때 Gram-Schmidt 과정을 적용해보겠습니다.

1. 먼저 임의의 벡터 하나를 기준으로 선정합니다 (u1은 직교 벡터입니다)

2. u2를 찾기 위해서 2D example에서 한 과정을 동일하게 수행합니다. 아래 그림과 같이 u1에 v2를 정사 영한 벡터를 찾고 

아래 그림과 같이 v2와 정사영된 벡터를 빼줌으로써 u2를 찾을 수 있습니다.

3. u3를 찾기 위해서 위의 과정에서 구한 u1과 u2 벡터에 v3를 정사영을 하여 proju2(v3)와 proju1(v3)를 구합니다.

계산된 2개의 정사영 벡터의 합 (빨간색)은 아래 그림과 같이 v3를 u1, u2 평면에 정사영한 벡터가 됩니다. 

u3를 구하기 위해서 v3에 정사영 벡터 합을 빼줌으로서 u3를 얻을 수 있습니다. 

 

4. 마지막으로 정규화 과정을 수행하면 정규 직교 기저를 얻을 수 있습니다. 

 

 

Generalization

일반화된 과정은 아래의 사진과 같습니다. 1번에서 basis가 주어졌을 때 2번 과정을 통해서 직교 벡터들 (w)를 구했으며, 3번에서 정규화하여 orthonormal basis를 얻어낼 수 있었습니다.

[2] Generalization of Gram Schmidt Process

 

Reference 

[1] https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process

[2] https://www.chegg.com/homework-help/questions-and-answers/apply-gram-schmidt-orthonormalization-process-transform-basis-r3-orthonormal-basis-use-dot-q24898669