선형대수 note 17: Orthogonal matrices and Gram-Schmidt

직교행렬 (Orthogonal Matrix)

지난 강의들에서 우리는 직교 벡터의 의미와 직교하는 부분공간들을 알아봤다. 이제 직교행렬에 대해서 설명하겠다. 정규직교 (Orthonormal) 열들로 이루어진 행렬에 대해서 알아보자. m \times n 행렬 Q 의 모든 열들 \mathbf{q}_i 은 서로 orthonormal 하다고 하면,1

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

Q 는 정의에 의해서 아래와 같은 성질을 갖는다.

(1)   \[Q^TQ = I \]

여기서 Q 가 정방행렬이면 특별히 직교행렬 (Orthogonal Matrix) 이라고 부른다.2
Q 가 정방행렬이면 Q 는 역행렬이 존재하고, 식 (1) 은 Q^T = Q^{-1} 을 의미한다. Q 가 정방행렬이든 아니든 Q 의 열들은 orthonormal 하다. Q 의 열공간으로의 투영행렬에 대해서 알아보자.

    \[P = Q(Q^TQ)^{-1}Q^T = QQ^T\]

투영행렬이 더 간단한 형태가 되었다. 특히 Q 가 정방행렬이면 P = I 가 된다. (당연하다. Q 가 정방행렬이면 열 공간은 전체 공간을 이루기 때문이다) Q 가 정방행렬이 아니더라도 열공간의 기저가 orthonormal 형태가 되면 많은 계산이 간단해진다. 예를 들어 최소자승 (Least Square) 문제 A\mathbf{x} = \mathbf{b} 에 최대한 근접하는 해 \hat{\mathbf{x}} 를 구하는 문제는 아래처럼 된다.

    \[\begin{aligned} A^T A\hat{\mathbf{x}} &= A^T \mathbf{b} \\ Q^T Q\hat{\mathbf{x}} &= Q^T \mathbf{b} \\ \hat{\mathbf{x}} &= Q^T \mathbf{b} \end{aligned}\]

그램-슈미트 정규 직교화 (Gram-Schmidt orthonormalization)

지금까지 orthonormal 한 열들을 가진 행렬에 대해서 설명했다. 이제 orthonormal 하지 않는 벡터들을 orthonormal 하도록 바꾸는 알고리즘을 소개한다. 그램-슈미트 정규 직교화 (Gram-Schmidt orthonormalization) 는 선형독립 벡터들을 정규직교 벡터로 변환하는 방법이다.

우선 벡터 \mathbf{b} 를 벡터 \mathbf{a} 로 투영하는 연산은 아래와 같다.

    \[proj_\mathbf{a}(\mathbf{b}) = \frac{\mathbf{a}^T \mathbf{b}}{\mathbf{a}^T \mathbf{a}} \mathbf{a}\]

\mathbf{a} 가 단위 벡터 \mathbf{q} 라면,

    \[proj_\mathbf{q}(\mathbf{b}) = \mathbf{q}^T \mathbf{b} \mathbf{q}\]

모든 열들이 선형독립인 m\times n 행렬 A 의 열들을 \mathbf{a}_i 라고 하고, 직교화된 벡터들을 \mathbf{u}_i, normalisation 까지 된 벡터들을 \mathbf{q}_i 라고 하면 그램-슈미트 정규 직교화의 전체적인 과정은 다음과 같다.

    \[\begin{aligned} \mathbf{u}_1 &= \mathbf{a}_1, && \mathbf{q}_1 = \frac{\mathbf{u}_1}{||\mathbf{u}_1||} \\ \mathbf{u}_2 &= \mathbf{a}_2 - \mathbf{q}_1^T \mathbf{a}_2 \mathbf{q}_1, && \mathbf{q}_2 = \frac{\mathbf{u}_2}{||\mathbf{u}_2||} \\ \mathbf{u}_3 &= \mathbf{a}_3 - \mathbf{q}_1^T \mathbf{a}_3 \mathbf{q}_1 - \mathbf{q}_2^T \mathbf{a}_3 \mathbf{q}_2, && \mathbf{q}_3 = \frac{\mathbf{u}_3}{||\mathbf{u}_3||} \\ \vdots && \vdots \\ \mathbf{u}_n &= \mathbf{a}_n - \mathbf{q}_1^T \mathbf{a}_n \mathbf{q}_1 - \mathbf{q}_2^T \mathbf{a}_n \mathbf{q}_2 - \mathbf{q}_3^T \mathbf{a}_n \mathbf{q}_3 - ... - \mathbf{q}_{n-1}^T \mathbf{a}_n \mathbf{q}_{n-1}, && \mathbf{q}_n = \frac{\mathbf{u}_n}{||\mathbf{u}_n||} \\ \end{aligned}\]

말로 풀어쓰면, 정규화된 첫벡터를 기준으로 정규직교 벡터 집합을 구성하고, 이 집합에 모두 수직인 정규직교 벡터들을 하나씩 계산해서 집합에 추가하는 것이다.

QR 분해 (using Gram-Schmidt)

LU 분해가 행렬을 삼각화 (Triangularization) 했듯이, QR 분해는 행렬을 직교화 (Orthogonalization) 한다.
모든 i 에 대해서 \mathbf{u}_i = \mathbf{q}_i^T \mathbf{a}_i \mathbf{q}_i 이므로 그램-슈미트 과정을 바꿔쓰면,

    \[\begin{aligned} \mathbf{a}_1 &= \mathbf{q}_1^T \mathbf{a}_1 \mathbf{q}_1 \\ \mathbf{a}_2 &= \mathbf{q}_1^T \mathbf{a}_2 \mathbf{q}_1 + \mathbf{q}_2^T \mathbf{a}_2 \mathbf{q}_2 \\ \mathbf{a}_3 &= \mathbf{q}_1^T \mathbf{a}_3 \mathbf{q}_1 + \mathbf{q}_2^T \mathbf{a}_3 \mathbf{q}_2 + \mathbf{q}_3^T \mathbf{a}_3 \mathbf{q}_3\\ \vdots \\ \mathbf{a}_n &= \mathbf{q}_1^T \mathbf{a}_n \mathbf{q}_1 + \mathbf{q}_2^T \mathbf{a}_n \mathbf{q}_2 + \mathbf{q}_3^T \mathbf{a}_n \mathbf{q}_3 + \dots + \mathbf{q}_{n-1}^T \mathbf{a}_n \mathbf{q}_{n-1} + \mathbf{q}_n^T \mathbf{a}_n \mathbf{q}_n \end{aligned}\]

    \[A =  \underbrace{ \begin{bmatrix} | & | & | & & | \\ \mathbf{a}_1 & \mathbf{a}_2 & \mathbf{a}_3 & \cdots & \mathbf{a}_n \\ | & | & | & & | \end{bmatrix}}_{m\times n} = \underbrace{ \begin{bmatrix} | & | & | & & | \\ \mathbf{q}_1 & \mathbf{q}_2 & \mathbf{q}_3 & \cdots & \mathbf{q}_n \\ | & | & | & & |  \end{bmatrix}}_{m\times n} \underbrace{ \begin{bmatrix} \mathbf{q}_1^T \mathbf{a}_1 & \mathbf{q}_1^T \mathbf{a}_2 & \mathbf{q}_1^T \mathbf{a}_3 & \cdots & \mathbf{q}_1^T \mathbf{a}_n \\ 0 & \mathbf{q}_2^T \mathbf{a}_2 & \mathbf{q}_2^T \mathbf{a}_3 & \cdots & \mathbf{q}_2^T \mathbf{a}_n \\ 0 & 0 & \mathbf{q}_3^T \mathbf{a}_3 & \cdots & \mathbf{q}_3^T \mathbf{a}_n \\ \vdots & \vdots & \cdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \mathbf{q}_n^T \mathbf{a}_n  \end{bmatrix}}_{n\times n} = QR\]

m\times n 행렬 A 의 열들이 선형독립이면 m\times n 정규 직교벡터 행렬 Qn\times n 상삼각 행렬 R 로 분해가 된다. 3
양변에 좌측에 Q^T 를 곱하면 R = Q^TA 이다. 그램-슈미트 과정에서 나중에 만들어진 \mathbf{q}_i 가 먼저 있던 \mathbf{a}_j 와 수직이므로 R 은 상삼각 행렬일 수 밖에 없다. 또 \mathbf{a}_i^T \mathbf{q}_i > 0 이므로 R 의 대각성분들은 양수다.

주어진 행렬 A 에서 그램-슈미트 과정으로 행렬 Q 를 구하고, AQ 를 이용해서 R 을 구할 수 있었다. 하지만 행렬 R 은 대각 성분이 ||\mathbf{u}_j|| 이고, 대각성분의 윗부분은 \mathbf{u}_j 를 구할 때 사용되는 값이다. 그래서 아래처럼 A 에서 R, Q 의 열들을 순서대로 구할 수 있다.

    \[\begin{aligned} r_{ij} = \mathbf{q}_i^T \mathbf{a}_j \\ \mathbf{u}_j = \mathbf{a}_j - \sum_{i=1}^{j-1} r_{ij} \mathbf{q}_i \\ r_{jj} = ||\mathbf{u}_j|| \\ \mathbf{q}_{j} = \frac{\mathbf{u}_j}{r_{jj}} \end{aligned}\]

코드로 나타내면,

QR 분해는 왜, 언제 필요할까?

A^TA = (QR)^T QR = R^T Q^T Q R = R^T R 이다. QR 분해를 미리 해놓으면 A^T A\hat{\mathbf{x}} = A^T \mathbf{b} 였던 최소자승식이,

    \[\begin{aligned} A^T A \hat{\mathbf{x}} &= A^T \mathbf{b} \\ R^T R \hat{\mathbf{x}} &= R^T Q^T \mathbf{b} \\ R\hat{\mathbf{x}} &= Q^T \mathbf{b} \end{aligned}\]

로 훨씬 간단해 진다. R 은 상삼각 행렬이므로 Back substitution 으로 풀 수 있다.


선형대수 note 목록

  1. m \ge n
  2. Orthonormal Matrix 로 불려야 할것 같지만 일반적으로 Orthogonal Matrix 라고 불린다.
  3. Q 를 정방행렬인 직교행렬로 분해하기도 한다. QR = \underbrace{\begin{bmatrix}Q_1 & Q_2\end{bmatrix}}_{m\times m}\underbrace{\begin{bmatrix}R_1 \\ 0\end{bmatrix}}_{m\times n}

Leave a Reply

Your email address will not be published. Required fields are marked *