QR decomposition, GS process, Householder reflection
저번 포스팅에서 알아본 LU분해와 같이, 정방 행렬을 분해하는 또 다른 방법인 QR 분해에 대해 알아볼 시간이다.
QR decomposition
QR분해의 개념 자체는 간단하다. 어떤 정방행렬 A를 서로 직교하는 행렬(직교 행렬) Q와 상삼각 행렬 R로 분해하는 것이다.
이런 간단하게 생긴 QR분해는 그람-슈미트 과정, 하우스홀더 반사와 기븐스 회전 등 다양한 방법으로 가능하다. 오늘 다룰 방식은 그람-슈미트 과정(GS process)과 Householder reflection이다.
그전에, "직교 행렬"이라는 개념이 처음 등장하는데 이는 해당 행렬의 열 벡터들이 서로 직교하는 벡터를 의미한다. 한 예시로, 좌측 하단의 세 벡터 x, y, z는 우측 하단과 같은 직교 행렬 Q로 나타낼 수 있다.
또한 이런 열벡터들을 각기 q1~3로 표현하는 방법도 있다.
이러한 직교행렬의 기억할만한 특성으로는, 그 전치 행렬이 역행렬과 같다는 점이 있다.
따라서 아래와 같은 방식으로 행렬이 작동한다.
이제 본격적으로 QR분해를 알아볼 시간이다. 첫째로 그람-슈미트 과정을 알아보기 전에, 필요한 사전 지식인 정사영을 먼저 짚고 넘어가 보자. 이미 아는 내용이라면 최종식만 기억하고 넘어가도 무방하다.
정사영
위 그림과 같이, 서로 다른 두 벡터 중 한 벡터에 대해 다른 벡터와 같은 방향의 크기는 코사인을 통해 나타낼 수 있다.
추가적으로, 벡터 내적의 정의를 통해 이 값을 다르게 표현할 수도 있다.
이런 컴포넌트 값은 스칼라값이므로, 벡터 값으로 바꿔주려면 a방향의 단위 벡터를 곱해주면 된다.
우리가 사용할 최종 식은 다음과 같다.
그람-슈미트 과정(GS process)
GS 과정이란, 간단히 서로 선형 독립인 벡터들을 서로 직교하게 만들어주는 과정이다. 정의부터 QR분해를 하기 딱 맞는 모습이다.
벡터에서 직교란 어떤 개념일까? 쉽고 간단하게 "벡터들이 서로 상관 없음"이라고 말할 수 있을 것이다. 그렇다면 어떤 벡터 b가 다른 벡터 a에 대해 아무런 관계도 없으려면 어떻게 해야 할까? 바로 b벡터 안에 있는 a벡터의 성분만을 모조리 빼 버리는 것이다. 이 "b벡터 안의 a성분"이 앞서 배운 정사영이고, b벡터에서 정사영을 빼는 그 과정이 바로 그람-슈미트 과정의 핵심이다.
이제 계산 과정에 대해 알아보자. 벡터 v1와 v2에 대해, v2의 v1에 대한 사영 벡터를 제거함으로써 서로 직교하게 만든다. 이를 u2벡터라고 칭하자.
이 u2벡터를 그 norm으로 나누어 정규화한다. 이를 e2벡터라고 하며, 여기까지 하면 GS과정을 완료한 것이다. 물론 기준이 되었을 v1벡터 또한 그 norm으로 나누어 정규화해야 한다.
이제 GS과정을 QR분해에 적용해 보자. 여기서 Q는 GS과정을 거친 A 행렬이고, R은 A=QR의 양 변에 Q의 역행렬을 곱해줌으로써 구할 수 있다.
Q : GS과정을 거친 A 행렬
R : R = A^(-1)Q인 상삼각 행렬
간단한 예시를 통해 자세히 알아보도록 하자. 이번에 QR분해를 할 대상인 행렬 A는 다음과 같다.
다음은 A행렬으로부터 GS process를 거쳐 Q 행렬을 구하는 과정이다.
이해를 위해 일부 계산과정을 간략히 설명하자면,
1) A->U
x1의 경우 기준 벡터이니 그대로 유지한다.
x2와 x3의 경우 x1을 기준으로 GS과정을 거치게 되는데, 그 첫 과정인 "사영 벡터를 빼 주어 직교화"하는 과정이다. 아래는 x2벡터를 직교화하는 과정이다.
2. U->Q
각 벡터를 그 벡터의 노름으로 나누어 정규화한다. 예시로 v2벡터를 u2벡터로 계산하는 과정을 첨부하였다.
다른 벡터들 또한 각각의 노름으로 나누어주면 된다. 이 과정을 끝내면 Q행렬을 만들어낼 수 있다.
다음은 R행렬을 구하는 과정이다. Q의 역행렬과 A행렬을 곱해 간단히 구할 수 있다.
계산해보면 아래의 성분들이 자연스럽게 0이 되어 상삼각 행렬이 되는 걸 알 수 있다. 대표적으로 a1·q2를 생각해 보자. 우리가 Q 행렬을 만들어 낼 때, 각각의 행렬끼리 서로 직교하게 만들었다. 따라서 q2는 q1 혹은 a1과 직교하게 되고, a1·q2의 값은 0이 된다. 같은 논리로 q3의 경우 a1, a2와 직교하기 때문에 그 계산 값이 0이 되고, 확장하여 qn의 경우 qn·am(m <n) = 0이 된다.
Householder 변환
그런데 이를 컴퓨터를 활용하여 계산하였을 때, 0이 되어야 하는 R의 성분들이 0이 아닌 값들을 가지는 경우가 다반사다. 이는 계산 과정상 분수를 포함할 때 어쩔 수 없이 생기는 오차 때문인데, 직교해야 할 Q행렬의 열 벡터들이 미세하게 직교하지 않음을 의미한다. 이 오차는 작은 행렬에서는 무시할 만하겠지만 행렬이 커질수록 오차도 기하급수적으로 커질 것이기 때문에 우리는 오차를 줄이기 위해 Householder 변환이라는 새로운 방법을 통해 QR분해를 하게 되었다.
이론
하우스홀더 변환의 이론적인 부분부터 살펴보도록 하자. 조금 복잡하니 넘겨도 무방하지만, 더 깊은 이해를 위해서는 한 번 참고하면 좋다.
어떤 벡터 X를 거울에 대고 대칭시켰다고 생각해보자. 그때 반대되는 벡터를 HX라고 하면, X벡터는 HX벡터가 되기 위해서 거울의 법선 벡터인 U에 대한 정사영을 두 번 빼 주어야 한다.
위 계산식을 표준 행렬화 하면 아래와 같은 식으로 변환된다.
이때, 만일 법선벡터 U가 아래와 같은 조건을 만족하는 단위 벡터라면
처음의 식은 아래와 같이 축약되며, 이를 우리는 householder matrix라고 한다.
이 식을 통해 우리는 하우스홀더 행렬의 큰 특징 두 가지를 알 수 있다.
1. symmetric
2. orthogonal
H행렬과 그 전치행렬을 곱하면, 계산 결과 서로 직교한다는 걸 알 수 있다.
따라서 H는 symmetric과 orthogonal을 동시에 만족한다.
직교행렬과 같은 특성을 가지고 있기에 하우스홀더 행렬을 활용해서도 QR분해를 해 볼 수 있다는 걸 알 수 있다.
조금 확장시켜 크기가 같은 두 벡터 v와 w에 대해 하우스홀더 행렬을 적용시켜 보자.
상당한 계산을 생략했지만, 중요한 결론은 아래와 같다.
이는 곧, 크기만 같다면 하우스홀더 행렬을 통해 복잡한 벡터 v의 거울상으로 훨씬 간단한 벡터인 w를 만들 수 있게 되었다는 뜻이다.
따라서 우리는 w를 한 성분이 v벡터의 크기와 같고, 나머지 성분이 모두 0인 간단한 모양의 벡터로 설정한다.
이제 이를 통해 QR분해를 시도해 보자. 아래의 식에서 a1~3은 A행렬의 열 벡터이며, q1, q2는 전치하여 곱하였을 시 Q 행렬이 되는 서로 직교하는 행렬들이다. 간단히 Q를 분해해두었다고 생각해도 좋다.
A=QR 행렬에서 a는 v와 같은 역할을 한다고 생각하자. 우선 a1과 q1에 대해 계산한다.
두 번째. a2와 q2의 경우 대각 성분을 1로, 첫 행과 첫 열의 성분을 0으로 두고 나머지를 찾을 수 있다. 만일 3x3보다 더 큰 행렬의 경우 이와 같이 계속해서 바깥의 행과 열을 하나씩 제거하며 찾을 수 있다.
마지막으로, 얻은 정보를 활용해 R과 Q를 찾을 수 있다.
