[수치해석 21] Hessenberg QR

저번 포스트에서는 rotation 관점을 활용하여 QR factorization을 하는 Givens rotation 방식을 소개했고, Hessenberg matrix의 정의까지 확인했다.

[수치해석] - [수치해석 20] Givens rotation, QR algorithm and Hessenberg matrix

Hessenberg matrix에 대해서 QR 분해 후 RQ 연산을 반복하면 빠르게 Eigenvalue problem을 해결할 수 있다고 했는데, 이번 포스트에서는 Hessenberg matrix를 얻는 방법과 왜 Eigenvalue problem을 빠르게 해결할 수 있다는 건지 정리하려고 한다.

 

Hessenberg matrix의 정의 먼저 확인해 보자.

Hessenberg matrix

$H \in \mathbb {R}^{n \times n}, h_{ij} = 0 \;\; \forall i > j+1$

Shape wise $\begin {bmatrix} *&*&*&*&*\\*&*&*&*&*\\0&*&*&*&*\\0&0&*&*&*\\0&0&0&*&* \end {bmatrix}$

이러한 형태의 upper triangular 행렬에 가까운데, diagonal 바로 아래까지 채워져 있는 형태의 행렬을 Hessenberg matrix라고 한다.

---

 

$n \times n$ 행렬에서 $A$에서 첫 번째 열을 Hessenberg 형태로 만드려고 한다.

Hessenberg reduction

Householder reflextion (recap)

먼저 Householder reflection의 특성을 확인하자. $a = \begin {bmatrix} a_1 & a_2 & \cdots & a_n \end {bmatrix}^\top $이라는 벡터를 Householder relfection을 통해 벡터를 변환하면,$\alpha e_1 = \begin {bmatrix}-\text {sign}(a_1)||a||_2 & 0 & \cdots & 0\end {bmatrix}^\top$ 으로 변환된다. 즉 한 번의 변환으로 하나의 성분 빼고 나머지를 모두 지울 수 있다.

$v = a - \alpha e_1$에 대해서 변환 행렬 $H = I - 2 \frac {vv^\top}{v^\top v}$를 Householder matrix라 한다.  

 

Hessenberg reduction

Householder reflection을 활용하여 Hessenberg reduction을 진행한다. $n \times n$ 행렬의 첫 번째 열 먼저 진행해 보자. 타깃은 첫 번째 열의 두 번째 성분부터 마지막 성분까지를 소거해야 한다.

• 첫 번째 열에서 주대각선 아래 부분을 추출한다.
  $$a_1 = \begin {bmatrix} a_{21} & a_{22} & \cdots & a_{n1} \end {bmatrix}^\top \in \mathbb {R}^{n-1}$$
• Householder reflection을 통해 첫 번째 성분만 남긴 벡터가 되도록 변환시키는 Housholder matrix $H_1 \in \mathbb {R}^{(n-1) \times (n-1)}$을 구한다.
  $$H_1 a_1 = \begin {bmatrix} -\text {sign}(a_{21})||a_1||_2 & 0 & \cdots & 0 \end {bmatrix}^\top $$
• $P_1 = \begin {bmatrix} 1 & 0 \\ 0 & H_1 \end {bmatrix}$ 행렬을 구축하여 $P_1 A P_1^\top$을 연산한다.

$P_1 A P_1^\top$은 어떤 의미가 있을까

1. 먼저 A 앞에 곱해지는 행렬은 행끼리 연산을 의미하고, A 뒤에 곱해지는 행렬은 열끼리의 연산을 의미한다. 즉 처음부터 upper triangular 형태로 만들려는 시도를 했다면, $P A$에 의해 첫 번째 열의 diagonal 제외한 성분들을 모두 0으로 만들고, $(PA) P^\top$에 의해 지워진 성분들이 다른 열들에 의해 다시 채워지게 된다.
   
   그렇기 때문에 $P_1 = \begin {bmatrix} 1 & 0 \\ 0 & H_1 \end {bmatrix}$ 형태로 만들어야 $P_1 A$는 첫 번째 열의 두 번째 성분부터 마지막 성분까지를 소거된다. $P_1^\top$을 뒤에 곱하지만 $\begin {bmatrix} 1 & 0 \\ 0 & H_1 \end {bmatrix}$ 형태에 의해 첫 번째 열은 유지된다. 즉 소거된 상태로 유지시킬 수 있기 때문에 바로 upper triangular 형태는 만들 수 없지만 Hessenberg 형태는 만들 수 있게 된다.
2. $P_1 = \begin {bmatrix} 1 & 0 \\ 0 & H_1 \end {bmatrix}$에 대해
   $$P_1 P_1^\top = \begin {bmatrix}1 & 0 \\ 0 & H_1\end {bmatrix} \begin {bmatrix}1 & 0 \\ 0 & H_1^\top\end {bmatrix} = \begin {bmatrix}1 & 0 \\ 0 & H_1 H_1^\top\end {bmatrix} = \begin {bmatrix}1 & 0 \\ 0 & I\end {bmatrix}  $$ 즉 orthogonal matrix이기 때문에, $P_1 A P_1^\top$은 eigenvalue들이 유지된다.

이렇게 각 열에 대해서 Hessenberg matrix 형태로 만드는 과정을 반복하여 Hessenberg matrix를 eigenvalue들을 유지한 상태로 만들어낼 수 있다.

---

Hessenberg QR

먼저 QR factorization은 Givens rotation을 활용한다. 이걸 활용하는 이유는 Hessenberg matrix 형태를 유지하기 위해서인데, 왜 유지될까?

 

Givens rotation으로 R, 그러니까 upper triangular matrix 형태로 만드는 원리는 $i$번째 row의 원소가 $j$번째 row의 원소에 영향을 줘서 제거하는 방식을 활용했다. 즉 2개의 row끼리 상호작용을 하게 되는데, $H$라는 Hessenberg matrix가 있고, 이를 Givens rotation을 통해 첫 번째 column을 upper triangular 형태로 만드는 상황이라고 생각하자. 그렇게 얻은 $R$에 다시 $Q$를 곱하게 되는데, 이러면 1,2 column이 서로 영향을 주게 된다. 그림에서 보면 upper triangular 행렬의 1,2 column의 상호작용은 다시 1번째 column을 Hessenberg matrix 형태로 만들게 된다. 이렇게 QR iteration도 Givens rotation을 활용하면 Hessenberg matrix 형태를 유지하면서 QR 분해와 RQ 연산을 반복할 수 있게 된다.

 

이건 첫 번째 column뿐 아니라 전체로 봐도 마찬가지다. 각각 column의 Givens rotation matrix를 통해 QR factorization 하면

$Q = G_1 G_2 \cdots G_{n-1}$이 되고, $$RQ = Q^\top Q RQ = Q^\top H Q = (G_{n-1}^\top \cdots G_1^\top) H (G_1 \cdots G_{n-1}) = (G_{n-1}^\top \cdots (G_1^\top H G_1) \cdots G_{n-1})$$

이렇게 G_1은 1,2 번째 row, column끼리의 상호작용, G_2는 2,3번째 row, column끼리의 상호작용... 이렇게 순서대로 진행되기 때문에 방금 설명한 Hessenberg matrix 형태가 유지된다는 것이 1,2 column뿐만 아님을 보일 수 있다.

 

Hessenberg QR complexity

기존의 QR iteration을 위해 Q 행렬을 구성하는 방법이 꽉 찬 dense matrix에 대해 모든 column에 대해 Householder reflection을 활용하는 등 이것만으로 $\frac {4}{3} n^3$ flops가 소요되기 때문에, 반복 한 번당 $O(n^3)$가 되지만, Hessenberg QR은 Hessenberg 형태로 만드는 단 한 번의 $O(n^3)$의 비용이 들고, 이후의 연산은 반복 한 번당 $O(n^2)$으로 줄게 된다. 따라서 기존 QR iteration보다 효율적인 알고리즘이 된다.

---

결론적으로 이번 포스트에서는 Hessenberg matrix를 iteration 없이 Housholder reflection을 통해 얻을 수 있고, 이 Hessenberg matrix를 Givens rotation을 활용하여 QR iteration을 할 수 있음을 보였다. Hessenberg QR은 반복해도 여전히 Hessenberg matrix 형태를 유지하기 때문에, 반복한다고 특성이 무너지지 않고, 시간 복잡도를 훨씬 줄일 수 있는 알고리즘이 된다.

 

다음 포스트에서는 이전 power method에서 shift를 적용한 것과 같이, QR에서도 shift와 double shift가 적용 가능한데, eigenvalue problem의 마지막 파트로 shift까지 적용한 QR에 대해 정리할 예정이다.