[선형대수학#12] Gram-Schmidt Process

지난 포스팅에서 내적을 다뤘다. dot product의 정의와 기하학적 의미를 확인했고, 이를 일반화한 inner product와 내적 공간의 개념을 정리했다. 또한 orthgonal 집합이 자동으로 linear independent임을 보았다. 이번에는 임의의 basis를 orthogonal하면서 크기가 1인 basis, 즉 orthonormal basis로 변환하는 그람-슈미트 프로세스를 정리한다.

 

Orthonormal Set

이전 포스팅에서 orthogonal set은 서로 다른 원소 간의 내적이 모두 0인 집합이라고 했다. 여기에 조건 하나를 더 추가한다. $S$가 orthogonal set이고, $S$의 모든 벡터의 크기가 1(즉, 단위 벡터)이면 $S$를 orthonormal set이라 한다. 조건을 정리하면 다음과 같다. 

 

$$\langle \mathbf{v}_i, \mathbf{v}_j \rangle = 
\begin{cases} 
0 & (i \neq j) \\ 
1 & (i = j) 
\end{cases}$$

 

orthogonal set은 "방향이 서로 수직"이고, orthonormal set은 거기에 "크기까지 1"인 것이다.

 

Orthonormal Basis의 장점

벡터 공간 $V$의 basis가 orthonormal이면 좌표 표현이 극도로 단순해지낟. $\mathbb{R}^n$에서 basis $S = \{\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_n\}$가 orthonormal이라 하자. 임의의 벡터 $\mathbf{v}$는 basis의 linear combinatoin으로 표현된다. 

 

$$\mathbf{v} = c_1\mathbf{u}_1 + c_2\mathbf{u}_2 + \dots + c_n\mathbf{u}_n$$

 

일반적인 basis라면 계수 $c_1, c_2, \cdots , c_n$을 구하기 위해 연립방정식을 풀어야 한다. 그런데 $S$가 orthonormal이면, 양번에 $\mathbf{u}_1$과의 내적을 취하면

 

$$\langle \mathbf{u}_1, \mathbf{v} \rangle = c_1 \langle \mathbf{u}_1, \mathbf{u}_1 \rangle + c_2 \langle \mathbf{u}_1, \mathbf{u}_2 \rangle + \cdots + c_n \langle \mathbf{u}_1, \mathbf{u}_n \rangle = c_1$$

 

이 된다. $\langle \mathbf{u}_1, \mathbf{u}_1 \rangle = 1$이고 나머지 항은 직교 조건에 의해 전부 0으로 사라지기 때문이다. 마찬가지로 모든 $i$에 대해 

 

$$c_i = \langle \mathbf{u}_i, \mathbf{v} \rangle$$

 

이다. 연립방정식 없이 내적 한 번으로 각 계수를 구할 수 있다. 이것이 orthonormal basis가 강력한 이유이다.

 

 

Gram-Schmidt Process

그렇다면 임의의 basis를 어떻게 orthonormal basis로 바꿀 수 있을까? 이것이 그람-슈미트 프로세스가 하는 일이다.

 

$$\text{Basis } S = \{\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_n\} \longrightarrow \text{Orthonormal Basis } T = \{\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n\}$$

 

핵심 아이디어는 단순하다. 새로운 벡터를 추가할 때마다, 이전까지 만들어놓은 직교 벡터들 방향의 성분을 빼고 직교하게 만드는 것이다. 

 

출처: https://interactivetextbooks.tudelft.nl/linear-algebra/Chapter7/GramSchmidt.html

 

step 1

첫 번째 벡터는 그대로 가져온다. 

 

$$\mathbf{v}_1 = \mathbf{u}_1$$

 

step 2

$\mathbf{u}_2$에서 $\mathbf{v}_1$ 방향의 성분을 빼서 $\mathbf{v}_1$와 직교하는 벡터를 만든다.

 

$$\mathbf{v}_2 = \mathbf{u}_2 - \frac{\langle \mathbf{u}_2, \mathbf{v}_1 \rangle}{\langle \mathbf{v}_1, \mathbf{v}_1 \rangle} \mathbf{v}_1$$

 

이 식이 왜 직교를 보장하는지 확인해보자. $\mathbf{v}_2 = \mathbf{u}_2 - \alpha \mathbf{v}_1$로 놓고 $\langle \mathbf{v}_2, \mathbf{v}_1 \rangle = 0$ 조건을 만족하는 $\alpha$를 구하면 

 

$$\begin{aligned}
\langle \mathbf{u}_2 - \alpha\mathbf{v}_1, \mathbf{v}_1 \rangle &= 0 \\
\implies \langle \mathbf{u}_2, \mathbf{v}_1 \rangle - \alpha \langle \mathbf{v}_1, \mathbf{v}_1 \rangle &= 0 \\
\implies \alpha &= \frac{\langle \mathbf{u}_2, \mathbf{v}_1 \rangle}{\langle \mathbf{v}_1, \mathbf{v}_1 \rangle}
\end{aligned}$$

 

이다. 직교 조건으로부터 $\alpha$가 자연스럽게 결정된다.

 

step 3

$\mathbf{v}_3$은 $\{\mathbf{v}_1, \mathbf{v}_2\}$모두와 직교해야 하낟. 같은 논리로, $\mathbf{u}_3$에서 $\mathbf{v}_1$ 방향과 $\mathbf{v}_2$ 방향의 성분을 각각 빼면 된다.

 

$$\mathbf{v}_3 = \mathbf{u}_3 - \frac{\langle \mathbf{v}_1, \mathbf{u}_3 \rangle}{\langle \mathbf{v}_1, \mathbf{v}_1 \rangle} \mathbf{v}_1 - \frac{\langle \mathbf{v}_2, \mathbf{u}_3 \rangle}{\langle \mathbf{v}_2, \mathbf{v}_2 \rangle} \mathbf{v}_2$$

 

일반항

패턴이 보인다. $i$번째 벡터는 $\mathbf{u}_i$에서 이전까지 구한 $\mathbf{v}_1, \mathbf{v}_2, \cdots, \mathbf{v}_{i - 1}$ 방향의 성분을 모두 빼는 것이다. 

 

$$\mathbf{v}_i = \mathbf{u}_i - \sum_{j=1}^{i-1} \frac{\langle \mathbf{v}_j, \mathbf{u}_i \rangle}{\langle \mathbf{v}_j, \mathbf{v}_j \rangle} \mathbf{v}_j$$

 

이렇게 얻은 $\{\mathbf{v}_1, \mathbf{v}_2, \cdots, \mathbf{v}_n\}$은 orthogonal basis이다. 마지막으로 각 벡터를 자기 자신의 norm으로 나누면 orthonormal basis가 된다.

 

$$\mathbf{e}_i = \frac{\mathbf{v}_i}{\lVert \mathbf{v}_i \rVert}$$

 

---

 

ML에서 그람-슈미트 프로세스의 가장 직접적인 응용은 QR 분해(QR decomposition)이다. 행렬 $A$의 열벡터에 그람-슈미트 프로세스를 적용하면 직교 행렬 $Q$를 얻고, $A = QR$로 분해할 수 있다. QR 분해는 수치적으로 안정적인 연립방정식 풀이, 최소제곱근 계산, 그리고 고유값 분해 알고리즘의 핵심 서브루틴으로 사용된다.