QR Decomposition (QR 분해)

Definition

QR 분해는 실수 행렬을 직교 행렬 (Q, Normal orthogonal matrix)과 상삼각 행렬 (R, upper triangular matrix)의 곱으로 나타내는 행렬 분해 방법입니다.

[1] Overview of QR Decomposition

Why

Ax = b 문제는 상당히 실생활에 많이 존재합니다. b라는 결과를 얻기 위해서 시스템 A에 어떠한 x 인풋을 넣어야 얻을 것인지에 생각할 때 분야를 막론하고 다양한 예제들이 존재할 것입니다. 

Ax = b를 만족하는 x를 구하고 싶다고 가정할 때 일반적인 방법은 x = A^(-1)b 또는 pesudo inverse와 같이 A의 역행렬을 계산하여 b에 곱하고 x를 얻을 수가 있습니다.

하지만 역행렬을 구하는 것이 전공책에 제시된 문제 수준에서 더 나아가 차원이 커질수록 시간의 복잡도가 기하급수적으로 커지게 됩니다. 때문에 우리는 역행렬을 직접 구하지 않고 시간 복잡도가 선형이며, 수치적으로 용이한 LU 분해 또는 QR 분해를 사용합니다.  

 

(1) Characteristics of `Q` (Q 행렬 특성)

QR 분해에서 Q는 Gram-Schmidt Process를 통해서 얻어진 정규 직교 기저로 이뤄진 행렬입니다. 

Q는 직교 행렬이기 때문에 symmetric matrix이면서 다음의 성질을 가지고 있습니다. 

 

(2) Characteristics of `R` (R 행렬 특성)

R은 상삼각 행렬입니다. 행렬의 주대 각선을 기준으로 대각 항의 모든 아래쪽 원소 값이 0인 행렬이 상 삼각 행렬입니다. 

상삼각 행렬은 덧셈, 곱셈, 역행렬에 대해 닫혀있습니다. 때문에 삼상각 행렬끼리의 덧셈, 곱셈, 역행렬 연산을 통해 나오는 행렬 (또는 결과) 또한 상삼각 행렬 형태를 지닙니다 (마찬가지로 하 삼각 행렬 또한 동일합니다).

*다만 순 삼각 행렬은 주 대각선 성분들이 0 값을 가지기에 역행렬에 대해 닫혀있기 위해서는 삼각 행렬이 가역 행렬 이어야 하는 추가 조건이 반드시 존재해야 합니다. 

 

이러한 성질을 통해서 결과적으로 Ax=b문제는 다음과 같이 풀이될 수 있습니다. A=QR일 때 아래의 순서와 동일하게 진행을 하면 x를 도출할 수 있습니다.  

 

QR Decomposition advantages (QR 분해 장점들)

(1) QR 분해는 A가 정방 행렬이 아닐 때 (행과 열 개수가 다른 행렬)도 적용이 가능합니다. 

(2) 컴퓨터에 알고리즘을 적용 시 구현이 용이합니다. 

 

 

How

우선 이전 포스팅에서 올린 Gram-Schmidt 과정을 통해 정교 직교 기저 벡터 (Q)를 얻을 수 있었습니다. 

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

다음 과정은 R 행렬을 얻는 과정입니다. 

A = QR 일 때, 열 벡터 a_n을 가진 행렬 A는 다음과 같습니다.

선형 독립인 열 벡터 a_n으로 구성된 A에 Gram-Schmidt과정을 적용하면 다음과 같이 Q 행렬을 얻습니다. 

이때 Q 행렬의 q_n 열 벡터는 A에 대해서 정규 직교 기저이기 때문에 a_n 을 q_n의 선형 결합으로 표현 가능합니다. 

정리하면 A = QR 형태는 아래와 같습니다. 

이때 a1⋅q2 을 생각해볼 때 q2는 a1 및 q1 성분이 모두 제거된 성분이기에 값이 0이 됩니다. 

마찬가지로 a_i ⋅ q_j 에 대해 생각할 때 i < j인 경우  a_i ⋅ q_j = 0이 되어버리기 때문에 아래와 같은 식으로 변경되어서 R행렬이 곧 상 삼각 행렬로 됩니다. 

정리하면 R 행렬은 a와 q로 이뤄진 행렬이며 a와 q정보는 이미 다 알고 있으므로 R을 도출해낼 수가 있습니다. 

 

Example

A가 위와 같은 행렬일 때 QR 분해를 해보겠습니다. 순서는 다음과 같습니다. 

(1) Gram-Schmidt 과정을 통해 Q 행렬 계산

(2) Q 행렬과 A 행렬 연산을 통해 R 행렬 계산 

먼저 (1) Gram-Schmidt 과정을 수행하기 위해서 행렬 A의 열 벡터를 다음과 같이 정의합니다. 

직교 벡터인 u1, u2, u3에 대해서 계산을 위해서 먼저 하나의 a_n 벡터를 u_n 벡터와 동일하게 정합니다. 

u2 벡터를 구하기 위해서 u1에 a2 벡터를 정사 영하여서 계산합니다. 

u3 벡터를 구하기 위해서 u1과 u2에 먼저 정사영을 각각 하여 정 사영된 벡터를 각각 구하고, u3에 정사영된 벡터들을 빼줍니다.

마지막으로 정규화를 합니다. 

(2) 과정인 R 행렬을 계산하면 최종적으로 아래와 같이 A 행렬을 구할 수 있습니다. 

 

Additional Information (추가 자료) 

QR 분해과정에서 Gram-Schmidt 과정만이 유일한 방법이 아닙니다. 아래와 같이 다양한 알고리즘이 있으며 각각의 알고리즘은 계산방법은 다르더라도 QR로 분해한다는 목표는 동일합니다. 하지만 이와 같이 다양한 알고리즘이 개발된 이유는 계산의 효율성 (복잡도) 문제를 개선하거나 정확도 (반올림)의 문제에 대해서 개선하기 위해서 탄생한 방법들입니다 [1]. 실시간 시스템이나 빅데이터를 분석할 때는 에너지나 시간의 문제는 반드시 더 적게 소모되어야 하며 더 효율적인 과정과 정확한 결과를 동반해야 합니다. 때문에 간단한 연산이라도 선형대수에서는 Decomposition을 위해서 다양한 알고리즘이 연구되어 왔습니다. 

(1) Gram-Schmidit 

(2) Modified Gram-Schmidt algorithm

(3) Householder reflection 
제일 많이 사용되는 알고리즘으로서 MATLAB이나 Julia에 사용되고 있습니다 (function name: `qr`)

(4) Givens Rotations

(5) Schwarz-Rutishauser Algorithm

아래는 알고리즘의 복잡도에 대해서 비교한 표입니다. Schwarz-Rutishauser Algorithm이 Gram-Schmidt 방법보다 2배 더 개선된 결과를 보입니다. 

QR-Algorithms Computational Complexity [2]

 

Reference

[1] http://wiki.nuaj.net/index.php?title=File:QR.png

[2] Gander, Walter. "Algorithms for the QR decomposition." Res. Rep 80.02 (1980): 1251-1268.

[3] “ECE133A — Applied Numerical Computing (6. QR-Factorization)”, Prof. L. Vandenberghe, University of California, Los Angeles, USA, Fall, 2019