그람-슈미트 직교화 (Gram-Schmidt Orthogonalization)

이름은 존내 어려워 보이는데 사실 존내 쉽다.

그냥 독립인 n개의 n 차원 벡터들을 서로 수직하도록 만들어(직교화)주는 것이다.

 

그람-슈미트 직교화란?

그람 슈미트 직교화란 위 그림처럼 서로 독립인 벡터들을 서로 직교하게 만드는 과정을 의미한다.

위와 같이 직교하도록 한 후 각 벡터들을 전부 길이가 1이 되도록 normalize하면 orthonormal한 관계로 만들 수 있다.

 

결과만 보면 매우 어려울 것 같지만 의외로 고등 수학에서 배운 내용(내적)만으로도 이해가 가능할 정도로 간단하다는 점이 재밌다.

 

그람-슈미트 직교화

위에서 말한 것처럼 내적의 개념을 사용하면 그람-슈미트 직교화가 가능하다.

먼저 내적에 대해 다시 기억을 끄집어 내보자. 내적이란 결국 정사영을 의미한다.

이전에 본 $a_1$를 $a_2$에 정사영한 벡터 $b_1$는 위 그림과 같이 나오게 된다.

이때 벡터 $a_1$은 벡터의 분해에 의해 위 그림처럼 $a_1$을 $a_2$에 정사영한 벡터와 그 벡터를 $a_1$에서 뺀 벡터로 이루어진다.

위 그림에서 다시 $a_2$를 가져와 보자.

가져와 보면 $a_1 - b_1$은 $a_2$와 수직한 것을 확인할 수 있다.

즉, $a_1$을 $a_2$에 정사영한 벡터를 빼고 남은 성분은 $a_2$와 수직하다는 것을 알았다.

이러한 과정을 해주는 것이 바로 그람-슈미트 직교화이다.

 

이를 정리해서 나타내보자.

서로 독립인 $n$차원 벡터 $a_1, a_2, \dots, a_n$가 있다고 하자. 이를 서로 직교하는 $q_1, q_2, \dots, q_n$ 벡터로 변형시키고 싶다.

이때 그람-슈미트 직교화는 아래와 같은 과정을 거친다.

1. 서로 독립인 $n$차원 벡터 집합 $V = {a_1, a_2, \dots, a_n}$에서 하나를 골라 그대로 수직 벡터 집합 $Q$에 넣고 $V$에서 해당 벡터를 제거한다.
2. 벡터 집합 $V$에서 하나의 벡터 $a_i$를 고른다.
3. $a_i$를 수직 벡터 집합 $Q= {q_1, q_2,..., q_{i-1}}$에 속한 벡터들에 정사영 시킨 벡터들을 빼준다.
4. 빼 준 결과 벡터 $q_i$를 수직 벡터 집합 $Q$에 추가하고 $a_i$는 $V$에서 제거한다.
5. 2~4 과정을 $V$가 공 집합이 될 때까지 반복한다.
6. orthonormal 벡터 집합을 얻기 위해 벡터 집합 $Q$의 요소들을 각각의 크기 $||q_i||$로 나누어주면 정규 직교 벡터 집합을 얻을 수 있다.

 

위 과정에서 가장 중요한 점은 정사영시킨 벡터를 찾는 것이다.

이전에 행렬과 벡터의 기초 연산 - 벡터와 내적의 정사영에서 이미 우리는 정사영 내린 벡터를 구하는 공식에 대해서 알아보았다.

위와 같은 상황에서 정사영된 벡터 $ux$는 아래 공식과 같이 결정된다고 하였다.

$$
\frac{u^Tv}{\sqrt{v^Tv}} \times \frac{v}{\sqrt{v^Tv}}
$$

그냥 단순히 $u$를 $v$의 unit vector와 내적 후 결과 값을 $v$의 unit vector에 곱해준 것에 불과하다.

 

즉, 위 알고리즘에서 “3. $a_i$를 수직 벡터 집합 $Q= {q_1, q_2,..., q_{i-1}}$에 속한 벡터들에 정사영 시킨 벡터들을 빼 새로운 직교 벡터 $q_i$를 구한다.”는 아래와 같은 수식으로 표현 가능하다.

$$
q_i = a_i - \sum_{j = 0}^{i-1}\frac{a_i^Tq_j}{\sqrt{q_j^T q_j}} \times \frac{q_j}{\sqrt{q_j^T q_j}} , (q_j \in Q)
$$

이 방식은 이전에 배운 Least Square로도 표현할 수 있다.

이전에 최소자승법에서 정리한 것처럼 위 “3. $a_i$를 수직 벡터 집합 $Q= {q_1, q_2,..., q_{i-1}}$에 속한 벡터들에 정사영 시킨 벡터들을 빼 새로운 직교 벡터 $q_i$를 구한다.”는 사실상 벡터 집합 $Q$로 $a_i$와 가장 가깝게 표현한 벡터를 빼주는 것과 동일하다.

이전에 정리한 것처럼 행렬 $A$를 $b$와 가장 가깝게 만들어주는 벡터 $x$는 아래와 같다.

$$
(A^TA)^{-1}A^T b = x
$$

결국 우리가 그람-슈미트 직교화에서 구해야 하는 것은 이번엔 $x$가 아니라 $e$가 되므로 아래와 같이 구할 수 있다.

$$
q_i = a_i - Q(Q^TQ)^{-1}Q^Ta_i
$$

이때 $Q$는 직교 행렬이기 때문에 $Q^TQ$는 $I$ 벡터가 된다. 그러므로 아래와 같이 정리된다.

$$
q_i = a_i - QQ^Ta_i
$$

이때 그람-슈미트 직교화는 벡터들이 선형 독립일 때만 잘 작동한다는 점이 중요하다.

당연하게도 선형 종속인 벡터가 존재하면, 직교화 과정에서 영 벡터가 나오게 된다.

이러한 영 벡터가 나오는 경우 그냥 무시하거나 벡터의 개수가 차원의 크기보다 커서 선형 종속이 발생할 수밖에 없는 경우 직교하는 벡터가 차원의 크기만큼 나오면 종료해야 한다.

 

Reference

• 혁펜하임 유튜브
• 다크 프로그래머 - Gram–Schmidt(그람-슈미트) 직교화