[응용선형대수] Orthonormal bases and Gram-schmidt

 

앞선 장에서는 projection과 cosine의 수학적 의미 등에 대해서 다루었다.

이번 장에서는 이러한 projection을 이용해서 space의 bases를 orthonormal bases로 바꾸는 방법에 대해 다룬다. 이렇게 하는 이유는 orthonormal bases일 때 가지고 있는 유용한 성질들 때문이다.

 

Orthonormal bases

 

$$\text{Def)}\quad q_1, \ldots, q_n \text{ are vectors and orthonormal if}\; q_{i}^{\top}q_{j}=\begin{cases}0 \; (i \neq j) \\ 1 \; (i=j)\end{cases}$$

 

$$\text{Def)} Q \text{ is called an orthogonal matrix, if }Q \text{ is }n\times n \text{ and all columns are orthonormal }(\Leftrightarrow Q^{\top}Q=I)$$

 

orthogonal matrix의 예시로 $A=\begin{bmatrix}\cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}$와 같은 rotation matrix를 꼽을 수 있다.

이러한 orthogonal matrix가 갖는 property는 다음과 같다.

 

1) $(Qx, Qy)=(x,y)$

$(Qx)^{\top}Qy=x^{\top}Q^{\top}Qy = x^{\top}y=(x,y)$

여기서 알 수 있는 사실은 orthogonal matrix로 선형변환을 하더라도 두 벡터 간의 각도가 보존된다는 사실이다.

 

2) $\| Qx \| = \|x\|$

orthogonal matrix로 선형변환을 하더라도 크기는 보존된다.

 

3) $Q=\begin{bmatrix} q_{1}, \ldots, q_{n} \end{bmatrix}$

$Qx=b$라고 하자.

$\begin{bmatrix} q_{1} & \cdots & q_{n}\end{bmatrix} \begin{bmatrix}x_{1} \\ \vdots \\ x_{n} \end{bmatrix}=\begin{bmatrix} b_{1} \\ \vdots \\ b_{n} \end{bmatrix} \Leftrightarrow x_1 q_1+ \ldots +  x_n q_n = b$

 

또한 위 식에 양변에 $Q^{\top}$을 곱하면

$q_{i}^{\top}b=x_{i}$ 으로 표현할 수 있다. 그리고 이 $x_{i}$를 위 식에 대입하면 다음과 같다.

$b=(q_{1}^{\top}b)q_{1}+\cdots + (q_{n}^{\top}b)q_{n}$

 

4) \( Q^{\top} Q = I \Leftrightarrow QQ^{\top} = I  \)

$Q$ inverse가 존재한다 (square)

 

---

 

앞서 배웠던 Projection을 생각해보자.

 

 

\( (A^{\top} \hat{x} - b) \in C(A^{\top}) = N(A^{\top})^{\perp} \)
\( A^{\top}(A^{\top} \hat{x} - b) = 0 \)

\( A^{\top} A \hat{x} = A^{top}b \)
\( \hat{x} = (A^{\top}A)^{-1} A^{\top}b \)

이 식은 projection 식으로 알려져있다.

 

 

위에서 다룬 $A$ matrix를 orthonormal column로 구성된 rectangular matrix$Q$라면 어떻게 될까?

 

$Q \hat{x}=b$를 만족시켜야 한다. 

$Q^{\top}Q\hat{x} = Q^{\top}b$

$\hat{x}=Q^{\top}b$

$Q\hat{x} =QQ^{\top}b$

 

따라서 projection matrix $p=QQ^{\top}$

 

---

 

만약 linearly independent vectors $a_{1},\ldots,a_{n}$이 있다고 할 때, 이 벡터들과 동일한 space를 만드는 orthonormal vectors $v_{1},\cdots,v_{n}$는 어떻게 찾을 수 있을까? 같은 space에 대한 표현이라도 orthonormal vector로 표현하는 것이 더 유리하다.

 

Gram Schmidt process

 

위의 질문에서 시작되는 것이 Gram Schmidt (그람 슈미츠) 과정이다. 이 방식은 QR decomposition에 활용될 수 있다.

예시를 통해 방법을 알아보자.

 

Example)

$a=[1,0,1]^{\top}, \; b=[1,0,0]^{\top}, \; c=[2,1,0]^{\top}$

 

 (1). \( a \)를 기준으로 계산을 한다고 할 때 orthonormal vector를 만들기 위해 normalization을 수행한다. (=크기로 나눠준다)

$$v_1 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}$$

 

(2). $a$ 벡터가 기준이 되었으므로 이 $v_{1}$ 벡터에 수직하도록 $b$ 벡터를 $v_{1}$ 벡터로 projection 한 결과 만큼 $b$를 빼주면 된다.

 

$$\begin{aligned} \beta &= b - (v_1^Tb)v_1, \text{ projection} \\   &= \begin{bmatrix} 1 \\ 0 \\ 0  \end{bmatrix} - \frac{1}{\sqrt{2}} \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} \\   &= \begin{bmatrix} -\frac{1}{2} \\ 0 \\ \frac{1}{2} \end{bmatrix} \end{aligned}$$
$$v_2 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 0 \\ -1 \end{bmatrix}$$

 

(3). 마찬가지로 마지막 벡터 $c$는 $v_1$과 $v_2$에 align되는 성분들을 뺀 결과이다.

$$\begin{aligned} c &= c - (v_1^Tc)v_1 - (v_2^Tc)v_2 \\   &= \begin{bmatrix} 2 \\ 1 \\ 0 \end{bmatrix} - \frac{2}{\sqrt{2}} \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} - \frac{2}{\sqrt{2}}\frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 0 \\ -1 \end{bmatrix} \\   &= \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} \end{aligned}$$
$$v_3 =\begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}$$

 

이렇게 얻은 $v_1,v_2,v_3$는 orthonormal vector가 된다.

 

이를 일반화 하면 다음과 같다.

 

If we found \( v_1, v_2, \ldots, v_4 \) \\
Then \( \tilde{v}_i = b_i - (b_i^{\top}v_1)v_1 - \ldots - (b_i^{\top}v_{i-1})v_{i-1} \) \\
$$v_i = \frac{\tilde{v}_i}{\|\tilde{v}_i\|}$$

The Factorization of \( A = QR \) 에서 Q는 orthonormal matrix를 의미하고 R는 upper triangular matrix이다. 이 QR decomposition을 할 경우 아래와 같은 과정을 거친다.

 

Given linearly independent \( a, b, c \) via Gram-Schmidt 
we have orthonormal vectors \( q_1, q_2, q_3 \)

$$a = (a^Tq_1)q_1$$
$$b = (b^Tq_1)q_1 + (b^Tq_2)q_2$$
$$c = (c^Tq_1)q_1 + (c^Tq_2)q_2 + (c^Tq_3)q_3$$

$$\begin{bmatrix} a & b & c \end{bmatrix} = \begin{bmatrix} q_1 & q_2 & q_3 \end{bmatrix} \begin{bmatrix} a^Tq_1 & b^Tq_1 & c^Tq_1 \\ 0 & b^Tq_2 & c^Tq_2 \\ 0 & 0 & c^Tq_3 \end{bmatrix}$$

\( A = Q \times R \) 

\( Q^TQ = I \) upper triangular 

여기서 전제는 $A$가 linearly independent 여야한다는 것이다. $R$ matrix는 대각항 아래로 모두 0이기 때문에 계산에 용이하다.