QR 분해(QR Decomposition)

[경고] 아래 글을 읽지 않고 "QR 분해"를 보면 바보로 느껴질 수 있습니다.
1. 행렬
2. 행렬식의 기하학적 의미
3. 가우스 소거법

[그림 1] 데카르트 좌표계의 정규 직교 기저, $\hat i, \hat j, \hat k$(출처: wikipedia.org)

가우스 소거법(Gaussian elimination)의 중요한 결과인 LU 분해(lower–upper decomposition)를 사용하면 1차 연립 방정식을 매우 효과적으로 풀 수 있다.

                  (1)

여기서 $\bf P$는 순열 행렬(permutation matrix)이다. 행렬식(determinant)의 고민에서 나온 벡터 공간(vector space)의 정규 직교 기저(orthonormal basis)를 만들 때는 QR 분해(QR decomposition) 혹은 QR 인수 분해(QR factorization)를 쓰면 정말 편리하다. 다른 관점으로 보면 벡터 공간의 직교 기저를 만드는 방식을 체계적으로 정리한 개념이 행렬의 QR 분해이다. QR 분해라는 목적지로 가기 위한 첫걸음은 좌표계(coordinate system)에서 시작한다. 우리가 살고 있는 공간은 3차원이지만, 3이란 숫자에 너무 집착할 필요는 없다. 좌표계 구성에 따라 임의의 $n$차원 공간까지 상상할 수 있다. 따라서 임의의 $n$차원에 있는 벡터를 $\bar v$라 할 수 있다. 벡터 $\bar v$를 구성하는 기저(basis)를 만들기 위해 선형 독립(linear independence)인 $n$개의 벡터 $\bar r_i$를 다음처럼 선택한다.

                  (2)

선형 독립인 벡터는 충분히 기저가 될 수 있지만, 벡터의 성분(component)을 계산할 때는 많이 불편하다. 이 개념을 이해하기 위해 식 (2)에 있는 $\bar r_i$를 이용해 $\bar v$를 구성한다.

                  (3)

여기서 $\alpha_i$는 벡터 $\bar v$의 스칼라 성분(scalar component)이다. 성분 $\alpha_i$를 구하기 위해, 식 (3)에 나온 선형 결합(linear combination)을 행렬로 만든다.

                  (4)

여기서 $\bar r_i$는 행 벡터(row vector)라 생각한다. 행렬을 구성하는 행 벡터 $\bar r_i$가 서로 선형 독립이기 때문에, 역행렬이 존재해서 $\alpha_i$를 유일하게 정할 수 있다. 기저를 새롭게 보기 위해, 식 (3)에 내적(inner product)을 적용한 후 다음처럼 계산할 수도 있다.

                  (5)

기저 간의 모든 내적 $\bar r_j \cdot \bar r_i$를 원소로 하는 행렬에 기본 행 연산(elementary row operation)을 써본다. 그러면 행렬에 있는 어떤 행에서는 다음 식이 나온다.

                  (6)

여기서 $\bar w$는 행렬에 사용한 기본 행 연산을 표현하는 벡터이다. 식 (4)에 있는 행렬 $[\bar r_i]$에 적절한 기본 행 연산을 적용하면 식 (5)에 구성한 행렬 $[\bar r_j \cdot \bar r_i]$가 얻어지므로, 식 (5)의 행렬도 역행렬이 분명 존재한다. 그래서 식 (6)에 있는 모든 원소가 $0$이 되기는 불가능하다. 이러한 결론을 내적 관점으로 보면, 어떤 벡터든지 모든 기저에 직교하기[$\bar w \cdot \bar r_i$ = $0$]는 불가능하다.

[그림 2] 2차원 벡터에 대한 그람–슈미트 과정(출처: wikipedia.org)

식 (4), (5)에서 기저의 선형 결합으로 표현한 벡터의 성분을 구하는 방법을 유도했지만 여전히 복잡하다. 그래서 내적에 대한 직교(orthogonality) 개념까지 적용해서 더 간략화한다. 먼저 내적과 벡터 성분의 관계를 이해하기 위해, $\alpha_i$를 내적으로만 표현한다. 첫 단계로 식 (3)에 정의한 $\bar v$에서 기저 $\bar r_1$이 없는 새로운 벡터를 $\bar v^{(1)}$이라 한다.

                  (7)

여기서 벡터의 내적(inner product) $\bar r_1 \cdot \bar r_1$은 $|\bar r_1|^2$과 같아서 두 번 나오는 $\bar r_1$을 단위 벡터로 만들어주며, $\bar v$에서 $\bar r_1$과 같은 방향의 성분을 찾기 위해 $\bar v \cdot \bar r_1$ 연산을 사용한다. 식 (7)에 $\bar r_1$을 내적하면 $0$이 나오므로 $\bar v^{(1)}$과 $\bar r_1$은 서로 수직이다. 식 (7)에서 기저  벡터 $\bar r_1$을 단위 기저 벡터(unit basis vector) $\hat r_1$로 바꾸면 더 간단해진다.

                  (8)

여기서 $\hat r_1$ = $\bar r_1 / |\bar r_1|$이다. 식 (8)과 비슷하게 벡터 $\bar v^{(1)}$에서 $\bar r_2$와 관계없는 벡터를 $\bar v^{(2)}$라 한다.

                  (9)

식 (9)를 식 (8)에 대입해서 정리하면 $\bar v$를 다음처럼 표현할 수 있다.

                  (10)

식 (10)에서 멈추지 않고 $\bar v^{(n)}$까지 계속 진행하면, 식 (3)에 대한 깔끔한 표현식을 얻을 수 있다.

                   (11)

여기서 벡터 $\bar r_i$는 서로 직교할 필요가 없지만, $\bar v^{(i)}$와 $\bar r_i$는 항상 직교한다[$\bar v^{(i)} \cdot \hat r_i$ = $0$]. 식 (5)보다는 식 (11)이 더 간단하지만, 기저가 서로 직교하지 않기 때문에 벡터 성분의 표현식이 여전히 복잡하다. 그래서 서로 직교하는 기저를 이용해 식 (11)을 더 간략화하면 좋다. 그래서 일반 벡터 $\bar v$에 적용한 식 (10)과 같은 절차를 일반 기저 $\bar r_i$에 사용해 정규 직교 기저 $\hat e_i$를 만든다. 예를 들어, [그림 2]에 있는 2차원 벡터와 정규 직교 기저 $\hat e_1, \hat e_2$를 보면, 대각선으로 표시된 일반 벡터 $\bar v_2$를 서로 직교하는 정규 직교 기저인 $\hat e_1, \hat e_2$의 선형 합으로 표현할 수 있다. 전체 과정 중에서 첫번째 정규 직교 기저 $\hat e_1$은 처음 나오는 기저이기 때문에 간단히 $\hat e_1$ = $\hat r_1$으로 둔다. 그 다음 정규 직교 기저 $\hat e_2, \cdots, \hat e_n$ 등은 다음처럼 차례차례 만든다.

                   (12)

여기서 $\bar s_i$는 직교하지만 크기가 1이 아닐 수 있는 직교 기저이다. 식 (12)의 첫째식이 [그림 2]에 정확히 대응한다. 식 (12)에 의해 정규 직교 기저는 서로 선형 독립이면서 다음 관계를 항상 만족한다.

                  (13)

이러한 정규 직교 기저를 생성하는 방법을 그람–슈미트 과정(Gram–Schmidt process)이라 부른다. 정규 직교 기저를 이용하면, 식 (11)과는 다르게 식 (3)에 있는 벡터를 매우 간단히 표현할 수 있다.

                   (14)

식 (14)와 비슷한 모양으로 일반 기저 $\bar r_i$를 $\hat e_i$의 선형 결합으로 나타낼 수도 있다. 식 (12)의 첫째식을 다음처럼 바꾼다.

                  (15)

위와 유사한 방법으로 모든 $\bar r_i$를 $\hat e_i$의 선형 결합으로 표현할 수도 있다.

                   (16)

그람–슈미트 과정과 식 (16)을 이용하면 행렬 분해의 중요한 기법인 QR 분해 방법을 유도할 수 있다.

[QR 분해]
열 벡터가 서로 선형 독립인 행렬 $\bf A$는 다음과 같은 두 행렬 $\bf Q$, $\bf R$의 곱으로 분해될 수 있다.

                   (17)

여기서 $\bf Q$의 열 벡터(column vector)는 그람–슈미트 과정으로 만든 정규 직교 기저, $\bf R$은 상삼각 행렬(upper triangular matrix)이다.

[증명]
열 벡터 ${\bf a}_i$를 가진 행렬 $\bf A$는 다음과 같다.

                  (18)

선형 독립인 열 벡터 ${\bf a}_i$를 일반 기저로 생각하면, 그람–슈미트 과정을 적용할 수 있어서 $\bf Q$를 다음처럼 생성할 수 있다.

                  (19)

여기서 열 벡터 ${\bf q}_i$는 $\bf A$에 대한 정규 직교 기저이다. 그러면 식 (16)에 따라 ${\bf a}_i$를 ${\bf q}_i$의 선형 결합으로 바꿀 수 있다.

                  (20)

여기서 $(\cdot)^T$는 전치 행렬(transpose)이다. 식 (20)을 행렬의 곱으로 쓰면 다음을 얻을 수 있다.

                  (21)
______________________________

QR 분해를 할 때 사용하는 그람–슈미트 과정은 나눗셈(division)과 매우 유사하다. 그래서 분해 명칭에 몫(quotient)과 나머지(remainder)를 뜻하는 QR을 사용한다. 행렬 $\bf Q$가 정방(square)이면 $\bf R$은 $\bf A$의 차원을 따라간다. 반대로 $\bf R$이 정방 행렬(square matrix)인 경우는 $\bf Q$의 차원이 $\bf A$와 같아진다.

QR 분해에 나오는 행렬 $\bf Q$는 열 벡터가 서로 직교하는 재미있는 성질이 있다. 행렬을 구성하는 행 벡터 혹은 열 벡터가 서로 직교하는 정방 행렬은 직교 행렬(orthogonal matrix) 혹은 정규 직교 행렬(orthonormal matrix)이라 부른다. 여기서 직교 행렬을 구성하는 행이나 열 벡터의 크기는 $1$이 되어야 한다. 행렬 $\bf Q$의 행과 열의 개수가 같으면, $\bf Q$도 직교 행렬이 된다. 그래서 직교 행렬을 표현하는 알파벳으로 Q를 쓴다. 직교 행렬은 다음과 같은 중요한 성질이 있다.

[직교 행렬의 성질]

직교 행렬 $\bf Q$는 다음 성질이 성립한다.

(a)                   (21)

(b)                  (22)

(c)                  (23)

(d) 열 벡터가 서로 직교하면 행 벡터도 직교한다. 그 반대도 참이다.

여기서 $\| \cdot \|$는 행렬식 $|\cdot|$과 구별되는 벡터의 크기[정확히는 벡터 노름(vector norm) $\| \cdot \|_2$ 혹은 유클리드 노름(Euclidean norm)]를 의미한다.

[명제 (a)의 증명]

열 벡터의 직교성에 의해 행렬 $\bf Q$와 전치 행렬의 곱은 항등 행렬(identity matrix)이 된다.

                  (24)

식 (24)에 전치 행렬을 취하면 다음 관계식도 얻을 수 있다.

                  (25)

따라서 $\bf Q$의 전치 행렬은 역행렬이 된다.

[명제 (b)의 증명]

전치 행렬과 행렬 곱의 행렬식은 다음 관계가 성립한다.

                  (26)

                  (27)

따라서 식 (24)에 의해 $|{\bf Q}|^2$ = $1$이다.

[명제 (c)의 증명]

식 (23)을 다음처럼 변형한 후 식 (24)를 대입하면 식 (23)이 증명된다.

                  (28)

[명제 (d)의 증명]

식 (25)의 좌변에 의해 행 벡터도 서로 직교한다.

______________________________

직교 행렬의 원소는 모두 실수이다. 만약 행렬의 원소가 복소수(complex number)까지 될 수 있고, 복소수 관점에서 열 벡터가 서로 직교하면, 이 행렬은 유니터리 행렬(unitary matrix)이라 부른다. 즉, 직교 행렬을 복소 영역으로 확장하면 유니터리 행렬이 된다.

식 (22)에 의해 직교 행렬의 행렬식은 $1$ 혹은 $-1$이다. 두 값을 구별하기 위해, 행렬식이 $1$이면 정상 직교 행렬(proper orthogonal matrix)이라 한다. 행렬식이 $-1$인 경우는 이상 직교 행렬(improper orthogonal matrix)이 된다. 식 (23)은 직교 행렬이 있든지 없든지 원래 벡터의 크기는 일정함을 뜻한다. 즉, 직교 행렬의 연산을 적용하더라도 벡터의 크기는 항상 보존된다. 물론 벡터의 방향은 바뀔 수 있다.

LU 분해와 비슷하게 QR 분해를 이용해서 1차 연립 방정식을 다음처럼 효과적으로 풀 수 있다.

                  (29)

식 (29)의 마지막식은 상삼각 행렬 $\bf R$만 계산하면 되므로, 후진 대입법(backward substitution)을 사용하면 된다. 다만 QR 분해로 연립 방정식을 풀 때는 행렬의 곱과 전치 행렬 연산이 필요하므로, LU 분해만큼 효과적이지는 않다.

[다음 읽을거리]

1. 선형 최소 제곱법

2. 행렬의 고유치와 고유 벡터