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

직교행렬 (Orthogonal Matrix)

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

$\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) 이라고 부른다.²
$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$ 정규 직교벡터 행렬 $Q$ 와 $n\times n$ 상삼각 행렬 $R$ 로 분해가 된다. ³
양변에 좌측에 $Q^T$ 를 곱하면 $R = Q^TA$ 이다. 그램-슈미트 과정에서 나중에 만들어진 $\mathbf{q}_i$ 가 먼저 있던 $\mathbf{a}_j$ 와 수직이므로 $R$ 은 상삼각 행렬일 수 밖에 없다. 또 $\mathbf{a}_i^T \mathbf{q}_i > 0$ 이므로 $R$ 의 대각성분들은 양수다.

주어진 행렬 $A$ 에서 그램-슈미트 과정으로 행렬 $Q$ 를 구하고, $A$ 와 $Q$ 를 이용해서 $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}$

코드로 나타내면,

for (j = 0; j < n; j++) {
  u = A.col(j);

  for (i = 0; i < j; i++) {
    R(i, j) = dot(Q.col(i), u);
    u -= R(i, j) * Q.col(i);
  }

  R(j, j) = norm(u);
  Q.col(j) = u / R(j, j); 
}

for (j = 0; j < n; j++) {

u = A.col(j);

for (i = 0; i < j; i++) {

R(i, j) = dot(Q.col(i), u);

u -= R(i, j) * Q.col(i);

}

R(j, j) = norm(u);

Q.col(j) = u / R(j, j);

}

$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 목록

선형대수 note 1: Geometry of linear equations (9/30/2015)
선형대수 note 2: Elimination with Matrices (9/30/2015)
선형대수 note 3: Multiplication and Inverse Matrices (9/30/2015)
선형대수 note 4: Factorization into A = LU (9/30/2015)
선형대수 note 5: Transposes, permutations, space R^n (9/30/2015)
선형대수 note 6: Column space and nullspace (10/2/2015)
선형대수 note 7: Solving Ax = 0 pivot variables, special solutions (10/2/2015)
선형대수 note 8: Solving Ax = b row reduced form R (10/2/2015)
선형대수 note 9: Independence, basis, and dimension (10/2/2015)
선형대수 note 10: The four fundamental subspaces (10/3/2015)
선형대수 note 11: Matrix spaces; rank 1; small world graphs (10/4/2015)
선형대수 note 14: Orthogonal vectors and subspaces (10/4/2015)
선형대수 note 15: Projections onto subspaces (10/4/2015)
선형대수 note 16: Projection matrices and least squares (10/6/2015)
선형대수 note 17: Orthogonal matrices and Gram-Schmidt (10/10/2015)
선형대수 note 18: Properties of determinants (10/10/2015)
선형대수 note 19: Determinant formulas and cofactors (10/12/2015)
선형대수 note 20: Cramer’s rule, inverse matrix, and volume (10/13/2015)
선형대수 note 21: Eigenvalues and Eigenvectors (10/14/2015)
선형대수 note 22: Diagonalization and Powers of A (10/18/2015)
선형대수 note 23: Differential equations and exp(At) (12/23/2015)
선형대수 note 24: Markov matrices; fourier series (12/23/2015)
선형대수 note 25: Symmetric matrices and positive definiteness (12/23/2015)
선형대수 note 26: Complex matrices; fast fourier transform (12/23/2015)
선형대수 note 27: Positive definite matrices and minima (12/24/2015)
선형대수 note 28: Similar matrices and jordan form (12/24/2015)
선형대수 note 29: Singular value decomposition (12/25/2015)
선형대수 note 30: Linear Transformations and Their Matrices (12/26/2015)
선형대수 note 33: Left and Right Inverses; Pseudoinverse. (12/27/2015)

$m \ge n$
Orthonormal Matrix 로 불려야 할것 같지만 일반적으로 Orthogonal Matrix 라고 불린다.
$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}$

JUDIS.me

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

직교행렬 (Orthogonal Matrix)

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

QR 분해 (using Gram-Schmidt)

Leave a Reply Cancel reply