Orthogonal matrices and Gram-Schmidt

1. 정규직교벡터(Orthonormal Vector)

■ 정규직교벡터는 정규화된 직교벡터로 길이가 1인 벡터를 의미한다. 그러므로 정규직교벡터는 직교 벡터이면서 단위 벡터인 벡터이다.

■ 벡터는 크기와 방향 성분을 가진다. 그래서 벡터를 화살표로 그리는 이유가 화살표에 크기와 방향에 대한 정보가 담겨 있기 때문이다.

■ 예를 들어 벡터 \( [2 \quad 0]^T \)과 \( [2 \quad 1]^T \)이 있다고 하자. \( [2 0]^T \)의 방향은 0도이며 2의 크기를 갖는다. 하지만 \( [2 \quad 1^T \)는 \( [2 \quad 0]^T \)의 방향인 0도에서 약 26도 회전한 방향을 가지며 크기도 \( \sqrt{5} \)가 된다. 또한 벡터에 스칼라를 곱하면 벡터의 길이(크기)가 늘어난다. 만약 \( [2 \quad 0]^T \)에 3을 곱하면 \( [6 \quad 0]^T \) 이 되며, 크기는 6이 된다.

■ 단위 벡터(unit vector)는 길이가 1인 벡터를 의미한다. 길이가 1이기 때문에 단위 벡터는 방향 성분만 나타내는 벡터이다.

- 길이가 1이라는 것은 단위 길이를 의미

■ 단위 벡터의 길이가 1인 이유는 다음과 같이 벡터를 벡터의 크기(길이)로 나누어주기 때문이다. 이렇게 단위 벡터는 항상 크기(길이)가 1이므로 어떤 스칼라 \( k \)를 곱하면 단위 벡터의 크기(길이)는 \( k \)가 된다.

\( \hat{\mathbf{v}} = \dfrac{\mathbf{v}}{\|\mathbf{v}\|} \)

■ 이런 단위 벡터를 정규화 벡터(normalized vector)라고도 한다. 서로 다른 성분(값)을 가지는 벡터에 \ 동일한 스케일을 가지기 위해 벡터의 크기를 나눠주기 때문에 '정규화'된 단위  길이를 가지기 때문이다.

■ 직교 벡터(orthogonal vector)는 사잇각이 90도. 즉, 수직 관계를 이루는 벡터를 말한다. 예를 들어 어떤 벡터 \( a \)가 있고 \( a \)와 수직 관계를 갖는 벡터 \( b \)가 있을 때, \( a \)와 \( b \)를 직교 벡터라고 부른다.

■ 벡터 \( a \)와 \( b \)가 수직 관계를 갖는다는 것은 두 벡터의 내적 값은 0이 된다. 두 벡터 사이의 사잇각이 90도 이기 때문이다. 

- 이렇게 직교 벡터는 하나의 벡터가 아니라 한 쌍 이상의 벡터로 정의된다.

■ 정규직교벡터란 직교 벡터이면서 단위 벡터인 벡터를 말한다. 즉, 두 벡터는 수직 관계(두 벡터의 사잇각은 90도)를 가지며 각 벡터의 크기(길이)는 1인 벡터로 방향 성분만 가지는 벡터를 정규직교벡터라고 한다.

■ 정규직교벡터도 한 쌍 이상의 벡터로 정의되며, 두 벡터의 내적 결과는 0이 되어야 하기 때문에 정규직교벡터는 다음과 같이 정의된다.

\( \mathbf{q}_i^T \mathbf{q}_j =
\begin{cases} 
    0 & \text{if } i \neq j \\ 
    1 & \text{if } i = j 
\end{cases} \)

■ 정규직교벡터를 각각 \( \mathbf{q}_i, \mathbf{q}_j \)라고 했을 때,  정규직교벡터의 크기는 1이므로 자기 자신과 내적하면 내적 값은 1이 된다. 즉, 자기 자신과는 직교하지 않는다.

■ 하지만, 서로 다른 벡터와 내적한 결과는 0. 즉, 수직 관계를 갖는다. 이렇게 정규직교벡터는 자기 자신의 크기는 1이며 서로 직교하는 모든 벡터와의 내적 값은 0이 된다.

■ 이러한 정규직교벡터는 수치 연산을 하는 과정에 값이 커지거나 작아져서 발생하는 오버플로우나 언더플로우 문제에 자유롭다. 크기가 1이기 때문이다.

 

2. 직교 행렬(Orthogonal Matrices)

2.1 Basic Orthogonal Matrix

■ 예를 들어 정규직교벡터를 갖는 \( Q \)라는 행렬이 있다고 하자. \( q_1 \)은 행렬 \( Q \)의 첫 번째 열이고, \( q_n \)은 \( n \)번째 열이라고 한다면, 모든 열벡터가 정규직교벡터이다. 이때 \( Q \)의 열공간을 만드는 정규직교벡터를 '정규직교기저(orthonormal basis)'라고 부른다. 

\( Q = \begin{bmatrix} \mathbf{q}_1 & \cdots & \mathbf{q}_n \end{bmatrix} \)

■ 위와 같이 정의한 행렬 \( Q \) 앞에 \( Q^T \)를 곱하면 

\( Q^T Q =
\begin{bmatrix} 
    \mathbf{q}_1^T \\ 
    \vdots \\ 
    \mathbf{q}_n^T
\end{bmatrix}
\begin{bmatrix} 
    \mathbf{q}_1 & \cdots & \mathbf{q}_n
\end{bmatrix} \)

■ 자기 자신과의 내적은 1이고 서로 다른 벡터와의 내적은 0이므로 \( Q^T Q \)의 결과 행렬의 원소(성분)은 주대각선에 1, 주대각선을 제외한 나머지는 0의 값을 갖게 된다. 즉, 단위 행렬이 된다.

\( Q^TQ = I \)

2.2 Square Orthogonal Matrix

■ square orthogonal matrix는 직교 행렬이 정방 행렬인 경우를 의미하며, 이때의 \( Q \)를 직교 행렬이라고 한다.

■ 정리하면, 행렬 \( Q \)가 \( n \times n \)으로 정방 행렬이고, 정규직교벡터로 이뤄져 \( Q^TQ = QQ^T = I \)가 되며 \( Q \)의 열벡터들과 행벡터들이 \( \mathbb{R}^n \)의 정규직교기저를 이루는 행렬을 직교 행렬이라고 한다.

■ \( Q \)가 정방행렬이면 \( Q \)는 역행렬을 갖으며, \( Q^TQ = I \)는 \( Q^T \)가 \( Q \)의 역행렬임을 말해준다. \( Q^T = Q^{-1} \)

■ 예를 들어 \( Q \)가 다음과 같은 \( 3 \times 3 \) 행렬일 때

\( Q =
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix} \)

■ 열 방향으로 보면 열벡터들은 단위 벡터이며 각각 내적을 계산하면 0이 되므로 열벡터들은 정규직교벡터이다. 행벡터들도 마찬가지이다. 그러므로 \( Q \)는 직교 행렬이다.

■ 직교 행렬 \( Q \)에 \( Q^T \)를 곱했을 때 \( QQ^T \)는 다음과 같이 단위 행렬이 되는 것을 확인할 수 있다. 그리고 \( Q^T \)도 또 다른 직교 행렬임을 알 수 있다.

\( Q Q^T =
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
= I \)

■ 사실 \( Q \) 행렬의 열벡터들은 \( \mathbb{R}^n \)의 표준 기저이다. 각 벡터는 다음과 같이 \( x, y, z \)축에 서로 수직이며 크기가 1이다. 또한 각 벡터끼리 내적했을 때 0이 된다.

■ 다음 예는 \( cos \)과 \( sin \)으로 이루어진 직교 행렬이다. 

\( Q =
\begin{bmatrix}
\cos\theta & -\sin\theta \\
\sin\theta & \cos\theta
\end{bmatrix} \)

■ \( cos^2 + sin^2 = 1 \)이며 행 방향, 열 방향 모두 각 벡터끼리 내적했을 때 내적 값이 0이므로 직교 행렬이다.

■ 하지만, 다음과 같은 행렬은 직교 행렬이라고 할 수 없다.

\( Q =
\begin{bmatrix}
1 & 1 \\
1 & -1
\end{bmatrix} \)

■ 행 방향, 열 방향 모두 각 벡터끼리 내적했을 때 내적 값이 0이므로 '직교'라는 조건은 갖추고 있으나 벡터의 크기가 1이 아니기 때문이다. 

■ 이런 경우 '정규화'가 필요하다. 즉, 현재 \( Q \)의 벡터들은 단순히 직교 벡터의 성질만 갖고 있으므로 벡터의 크기로 나눠 단위 벡터로 만들어야 한다. 벡터 크기로 나눈다는 것은 단순히 벡터에 스칼라배를 한다는 것이므로 벡터의 방향에는 아무런 영향을 미치지 않는다. 즉, 벡터 크기로 나눠줘도 직교 성질을 유지한다.

\( Q = \frac{1}{\sqrt{2}}
\begin{bmatrix}
1 & 1 \\
1 & -1
\end{bmatrix}
=
\begin{bmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}
\end{bmatrix} \)

■ 그리고 두 벡터가 서로 직교하지만, 두 벡터의 크기가 다른 경우가 있다. 이런 경우에는 열벡터1은 열벡터1의 크기로 열벡터2는 열벡터2의 크기로 각각 나눠주면 된다.

2.3 Rectangular Orthogonal Matrix

■ 2.2는 직교 행렬이 정방 행렬인 경우이다. 이번에는 직교 행렬이 다음과 같이 \( m \times n \)으로 직사각 행렬인 경우이다.

\( Q = \frac{1}{3}
\begin{bmatrix}
1 & -2 \\
2 & -1 \\
2 & 2
\end{bmatrix} \)

2.4 Adavantage of using Orthogonal Matrix

■ 다음과 같은 투영 행렬 \( P \)를 통해 어떤 벡터 \( b \)를 행렬 \( A \)의 열공간에 투영시킬 수 있었다.

\( P = A (A^T A)^{-1} A^T \)

■ 행렬 \( Q \)가 정규직교 열을 가지는 직사각 행렬이라고 가정하자. 이때, 행렬 \( Q \)의 열 공간에 어떤 벡터를 투영하고 싶다고 하면, 투영 행렬 \( P \)는 다음과 같이 대칭 행렬이 된다.

\( P = Q (Q^T Q)^{-1} Q^T = Q Q^T \)

- \( A \)를 \( Q \)로 바꾸기 위해서는 먼저, \( A \)의 벡터들이 서로 수직 관계를 가지게 만들어야 한다. 이는 gram-schmidt 과정을 통해 만들어 줄 수 있다.

- gram-schmidt 과정을 통해 만들어진 행렬의 벡터들은 수직 관계를 갖고 있지만, '단위 벡터' 성질을 가지고 있지는 않다. 그러므로 정규직교벡터로 만들어주고 싶다면 추가로 벡터의 크기로 나눠줘야 한다.

■ 만약 \( Q \)가 정방 행렬이라면, 역행렬이 존재하므로 다음과 같이 단위행렬이 된다.

\( P = Q (Q^T Q)^{-1} Q^T = Q Q^T = I \)

■ \( Q \)가 직사각 행렬이든 정방행렬이든 이렇게 행렬 \( A \)를 정규직교벡터를 갖는 직교 행렬 \( Q \)로 바꿔준다면 계산이 매우 간단해진다. 

■ \( Q \)가 정방 행렬일 때 투영 행렬 \( P \)가 단위 행렬이 되는 이유는 다음과 같다.

■ 투영은 \( A \mathbf{x} = b \)에서 선형 결합 \( A \mathbf{x} \)는 전체 공간의 일부를 차지하는 부분 공간인 \( A \)의 열공간에 존재하는데, \( b \)가 \( A \)의 열공간에 없는 경우 \( b \)를 \( A \)의 열공간에 투영시켜 \( A \)의 열공간에서 \( b \)와 가까운(근사한) 벡터 \( p \)를 찾기 위함이었다.

■ 하지만, 직교 행렬 \( Q \)가 정방행렬이라면 \( Q \)의 열벡터들이 만드는 열공간은 전체 공간과 같아진다. 위의 예시에서 3차원 공간의 표준 기저로 구성된 \( Q \)가 바로 그 예이다.

■ 즉, \( Q \)의 열공간 = 전체 공간이기 때문에 \( Q \mathbf{x} = b \)에서 \( b \)는 \( Q \)의 열공간에 있는 \( Q \mathbf{x} \)와 같은 공간에 존재한다고 할 수 있다.

■ 즉, 이미 벡터 \( b \)가 \( Q \)의 열공간에 존재하기 때문에 \( b \)를 \( Q \)에 투영하여도 \( b \)와 가장 가까운 벡터는 \( b \)가 된다. 즉, 투영의 의미가 없어진다. 이러한 이유로 직교 행렬 \( Q \)가 정방 행렬이면 투영 행렬이 단위 행렬이 되는 것이다.

■ 투영 행렬의 특성으로 \( P^2 = P \)가 있었다. \( P = Q(Q^TQ)^{-1}Q^T = QQ^T \)라고 할 때, \( P^2 \)은 

\( (QQ^T)(QQ^T) = QQ^T \)이므로 \( P^2 = P \)가 성립한다. 

- \( Q^TQ = I \)이기 때문

■ Q를 이용하면 계산이 간단해지는 또 다른 경우는 \( A \mathbf{x} = b \)를 만족하는 \( \mathbf{x} \)를 구할 수 없어 \( A^T A \hat{\mathbf{x}} = A^T b \)를 통해 근사해(또는 최적해)를 구하는 경우이다.

■ \( A \)를 그람-슈미트 과정을 통해 직교 벡터로 만들고 정규화를 통해 직교 행렬 \( Q \)로 만든다면, \( Q^T Q \hat{\mathbf{x}} = Q^T b \)가 되며 \( Q^TQ = I \)이므로 근사해(최적해)는 \( \hat{\mathbf{x}} = Q^T b \)가 된다.

 

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

■ 예를 들어 다음과 같이 벡터 \( a \)와 \( b \)가 독립 관계를 갖는다면, 두 벡터는 서로 직교하지 않는다.

■ 만약, 위의 \( a, b \)가 2차원을 정의하는 기저 벡터라고 할 때, 그람-슈미트 과정을 통해 수직 관계를 가지고 있지 않은 기저 \( \left\{a, b \right\} \)를 수직 관계를 갖는 (동일한 차원의) 다른 기저로 바꿔줄 수 있다.

■ 그람-슈미트 과정의 아이디어는 다음과 같다.

■ 그람-슈미트 과정의 목표는 서로 직교하지 않는 벡터 \( a, b \)를 서로 직교하는 벡터 \( A, B \)로 만드는 것이다. 이를 위해 '투영'을 사용한다.

■ \( b \)를 \( a \)에 투영시키면 \( a \) 위에서 \( b \)와 가장 가까운 지점은 \( b \)의 종점에서 수직으로 내린 지점 \( p \)이다. 이때 \( e = b - p \)이며 \( e \)와 \( a \)는 서로 수직이다. 이렇게 투영을 이용하면 서로 수직인 벡터를 얻을 수 있다.

■ 즉, 벡터 \( a \)를 \( A \)라고 가정한 상태에서, 투영을 통해 얻은 오차 벡터 \( e \)가 \( B \)가 되는 것이다. 

■ \( e = B \)이므로 \( B = b - p \)인데 \( p \)는 \( \dfrac{A^T b}{A^T A} A \)이므로 \( B = b - \dfrac{A^T b}{A^T A} A \)으로 정의할 수 있으며, \( A \perp B \Leftrightarrow A^T \cdot B = 0 \)가 성립한다.

■ 이렇게 서로 독립 관계를 갖는 벡터. 즉, 어떤 공간의 기저가 2개인 경우 그람-슈미트 과정은

- ⓛ \( a = A \)

- ② \( B = b - \dfrac{A^T b}{A^T A} A \)
■ 이번에는 서로 독립 관계를 갖는 3개의 벡터. 즉 어떤 공간의 서로 수직 관계를 가지고 있지 않은 기저가 3개인 경우이다.

■ 이제 그람-슈미트 과정의 목표는 서로 직교하지 않는 벡터 \( a, b, c \)를 서로 직교하는 벡터 \( A, B, C \)로 만드는 것이다. 이때 \( A, B \)는 위와 같이 \( a = A \), \( B = b - \dfrac{A^T b}{A^T A} A \)로 정의하면 된다.

■ 사실, \( B = b - \dfrac{A^T b}{A^T A} A \)는 \( a = A \)이므로, 벡터 \( b \)에서 벡터 \( a \)와 평행한 성분을 뺀 것으로 볼 수 있다. 그래서 \( B \)는 수직 성분만 남아 \( A \)와 직교하는 것이다.

■ \( C \)도 같은 방법으로 구해야 \( A \)와 직교하고 \( B \)와 직교하는 벡터 \( C \)를 만들 수 있다.

\( C = c - \dfrac{A^T c}{A^T A} A - \dfrac{B^T c}{B^T B} B \)

■ 이렇게 어떤 공간의 기저가 3개인 경우 그람-슈미트 과정은

- ⓛ \( a = A \)

- ② \( B = b - \dfrac{A^T b}{A^T A} A \)

- ③ \( C = c - \dfrac{A^T c}{A^T A} A - \dfrac{B^T c}{B^T B} B \)

■ 서로 수직 관계를 가지고 있지 않은 어떤 공간의 기저가 4개, 5개, \( \cdots \) \( n \)개여도 위와 같은 그람-슈미트 과정을 통해 수직 관계를 갖는 기저로 만들어 줄 수 있다.

■ 그리고 직교 기저(벡터) \( A, B, C \)를 정규직교기저로 바꾸고 싶다면, 다음과 같이 자신의 크기로 나눠주면 된다.

\( \dfrac{A}{\|A\|}, \dfrac{B}{\|B\|}, \dfrac{C}{\|C\|} \)

■ 예를 들어 서로 직교하지 않는 두 벡터 \( a, b \)가 다음과 같을 때

\( a = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \quad
b = \begin{bmatrix} 1 \\ 0 \\ 2 \end{bmatrix} \)

■ \( a = A \)로 두면 \( B \)는 다음과 같이 계산할 수 있다.

\( B = \begin{bmatrix} 1 \\ 0 \\ 2 \end{bmatrix} 
- \dfrac{3}{3} \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}
= \begin{bmatrix} 0 \\ -1 \\ 1 \end{bmatrix} \)

■ \( A, B \)는 직교 벡터이다. 이를 정규직교벡터로 \( q_1, q_2 \)로 만든다면 직교 행렬 \( Q \)는 다음과 같다.

\( Q =
\begin{bmatrix} 
    \mathbf{q}_1 & \mathbf{q}_2
\end{bmatrix}
=
\begin{bmatrix} 
    \frac{1}{\sqrt{3}} & 0 \\
    \frac{1}{\sqrt{3}} & -\frac{1}{\sqrt{2}} \\
    \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}}
\end{bmatrix} \)

■ 행렬 \( A \)가 다음과 같을 때

\( A = [a \quad b] =
\begin{bmatrix} 
    1 & 1 \\
    1 & 0 \\
    1 & 2
\end{bmatrix} \)

■ \( A \)의 열벡터를 정규직교벡터로 만들어서 사용하는 행렬이 직교 행렬 \( Q \)이다.

■ 이때 행렬 \( Q \)의 열들은 본질적으로 \( A \)의 열벡터들이 생성하는 부분공간을 그대로 '정규직교기저'가 생성하는 부분공간 형태로 바꾼 것에 불과하다. 즉, \( A \)와 \( Q \)의 열공간은 동일한 공간이다.

■  \( A \)의 열벡터와 \( Q \)의 열벡터를 각각 비교하면 \( Q \)의 첫 번째 열벡터는 \( A \)의 첫 번째 열벡터의 스칼라배이며, \( Q \)의 두 번째 열벡터는 \( A \)의 첫 번째 열벡터와 두 번째 열벡터를 선형 결합하여 만들 수 있는 열벡터이다. 즉, \( A \)와 \( Q \)가 갖는 열공간은 기저만 달라질 뿐 동일하다. \( C(A) = C(Q) \)

 

4. QR 분해(QR decomposition)

■ \( A = QR \) 분해는 그람-슈미트 과정을 통해 만든 \( Q \) 행렬을 이용해 원래 행렬 \( A \)를 \( A = QR \) 형태로 분해하는 것이다.

\( A = QR \)
\(
A: m \times n, \quad Q: m \times m, \quad R: m \times n
\)
\(
\begin{bmatrix}
    \vert & \vert &  & \vert \\
    \mathbf{a}_1 & \mathbf{a}_2 & \cdots & \mathbf{a}_n \\
    \vert & \vert &  & \vert
\end{bmatrix}
=
\begin{bmatrix}
    \vert & \vert &  & \vert \\
    \hat{\mathbf{q}}_1 & \hat{\mathbf{q}}_2 & \cdots & \hat{\mathbf{q}}_m \\
    \vert & \vert &  & \vert
\end{bmatrix}
\begin{bmatrix}
    \mathbf{a}_1^T \mathbf{q}_1 & \mathbf{a}_2^T \mathbf{q}_1 & \cdots & \mathbf{a}_n^T \mathbf{q}_1 \\
    \mathbf{a}_1^T \mathbf{q}_2 & \mathbf{a}_2^T \mathbf{q}_2 & \cdots & \mathbf{a}_n^T \mathbf{q}_2 \\
    \vdots & \vdots & \ddots & \vdots \\
    \mathbf{a}_1^T \mathbf{q}_m & \mathbf{a}_2^T \mathbf{q}_m & \cdots & \mathbf{a}_n^T \mathbf{q}_m
\end{bmatrix}
=
\begin{bmatrix}
    \vert & \vert &  & \vert \\
    \hat{\mathbf{q}}_1 & \hat{\mathbf{q}}_2 & \cdots & \hat{\mathbf{q}}_m \\
    \vert & \vert &  & \vert
\end{bmatrix}
\begin{bmatrix}
    \mathbf{a}_1^T \mathbf{q}_1 & \mathbf{a}_2^T \mathbf{q}_1 & \cdots & \mathbf{a}_n^T \mathbf{q}_1 \\
    0 & \mathbf{a}_2^T \mathbf{q}_2 & \cdots & \mathbf{a}_n^T \mathbf{q}_2 \\
    \vdots & \vdots & \ddots & \vdots \\
    0 & 0 & \cdots & \mathbf{a}_n^T \mathbf{q}_m
\end{bmatrix}
\)

■ 여기서 \( R \)행렬은 원래 행렬 \( A \)와 직교 행렬 \( Q \)를 연결시켜주는 상삼각행렬이다.

■ \( R \) 행렬의 2행 1열의 원소는 내적 \( a^{T}_1 q_2 \)인데 이 값이 0이 된다. 이는 그림-슈미트 과정에서 벡터 \( q \)를 이전 벡터들에 수직이 되도록 구성했기 때문이다. 다음 그림과 같이 \( A = a_1, B = q_2 \)라고 했을 때, 두 벡터는 서로 직교하므로 내적 값은 0이 된다. 이것이 \( R \)이라는 상삼각 행렬을 얻는 이유이다.

■ \( A \)가 정방행렬이라면 \( R \) 행렬은 다음과 같이 얻을 수 있다.

\( A = QR \)

\( Q^TA = Q^TQR \), \( \quad (Q^TQ = I) \)

\( Q^TA = R \)

 

참고) https://hyeon-jae.tistory.com/182[개념] 정규직교집합과 Gram-Schmidt 직교화

[개념] 정규직교집합과 Gram-Schmidt 직교화