3 ways of QR Decomposition and Hessenberg matrix

QR Decomposition

QR 분해는 세가지 방법이 있다. 가장 기본적인 Gram-Schmidt 방법은 A 의 각 열들을 첫번째 열에 맞추어 차례로 직교화하는 방법을 사용한다. 결과적으로 R 은 Gram-Schmidt 과정에 따라 상삼각행렬이 된다. 나머지 두 방법 (Givens, Householder) 은 Gram-Schmidt 보다 효율적이다. 이 방법들은 가우스 소거 과정에서 나타났던 행 소거행렬 E 대신에 직교행렬 Q 를 이용해 열 소거를 해서 최종적으로 상삼각행렬 R 로 변환한다.

GivensHouseholder 방법은 Q 의 형태가 다르다. 여기서는 Gram-Schmidt 방법은 생략하고 나머지 두 QR 분해 방법들에 대해서 설명한다. Gram-Schmidt 방법에 대해서는 아래의 포스트로 대신한다.

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

Givens Rotation

Givens rotation 행렬은 특정 ij 평면을 기준으로 반시계 방향으로 \theta 만큼 회전시키는 행렬이다. 일반적인 형태는 다음과 같다.

    \[G(i, j, \theta) = \begin{bmatrix} 1 & \dots & 0 & \dots & 0 & \dots & 0 \\ \vdots & \ddots & \vdots & & \vdots & & \vdots\\  0 & \dots & c & \dots & -s & \dots & 0 \\ \vdots & & \vdots & \ddots & \vdots & & \vdots\\  0 & \dots & s & \dots & c & \dots & 0 \\ \vdots & & \vdots & & \vdots & \ddots & \vdots\\  0 & \dots & 0 & \dots & 0 & \dots & 1 \\ \end{bmatrix} \quad \text{s.t. } 1 \leq i < j \leq n\]

    \[\begin{aligned} g_{ii} &= \cos\theta \\ g_{ij} &= -\sin\theta \\ g_{ji} &= \sin\theta \\ g_{jj} &= \cos\theta \\ g_{kl} &= \begin{cases}     0 & \text{if } k \neq l \\     1 & \text{if } k = l  \end{cases} \quad \text{s.t. } k, l \neq i, j \end{aligned}\]

\theta 를 직접 구할 필요없이 \cos\theta, \sin\theta 만 구하면 되므로,

    \[\cos\theta = \pm\frac{\alpha}{\sqrt{\alpha^2 + \beta^2}}\quad \sin\theta = \mp\frac{\beta}{\sqrt{\alpha^2 + \beta^2}}\]

여기서 \alpha 는 회전시켜 소거할 행렬 A 의 성분 a_{ii} 이고, \beta0 으로 만들 성분 a_{ji} 이다.

예를 들어 3\times 3 행렬의 (2, 1) 성분을 0 으로 만들 xy 평면 회전행렬 G_{21} 은 다음과 같다.

    \[G_{21} = G(1, 2, \theta_1) = \begin{bmatrix} \cos\theta_1 & -\sin\theta_1 & 0 \\ \sin\theta_1 & \cos\theta_1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}\]

가우스 소거 행렬 E_{21}(2, 1) 성분을 0 으로 소거했던것 처럼, G_{21}(2, 1) 성분을 0 으로 소거한다.
이어서 G_{21} A(2, 1) 성분을 0 으로 만들 xz 평면 회전행렬 G_{31}G_{31} G_{21} A(3, 2) 성분을 0 으로 만들 yz 평면 회전행렬 G_{32} 는 각각 다음과 같다.

    \[G_{31} = G(1, 3, \theta_2) = \begin{bmatrix} \cos\theta_2 & 0 & -\sin\theta_2 \\ 0 & 1 & 0 \\ \sin\theta_2 & 0 & \cos\theta_2 \\ \end{bmatrix}, \quad G_{32} = G(2, 3, \theta_3) = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \cos\theta_3 & -\sin\theta_3 \\ 0 & \sin\theta_3 & \cos\theta_3 \\ \end{bmatrix}\]

이들을 이용해서 3\times 3 행렬인 A 의 열들을 차례로 모두 소거하면

    \[(G_{32} G_{31} G_{21}) A = R\]

G_{ij} 는 직교행렬이다. 따라서 식을 정리하면,

    \[A = (G_{32} G_{31} G_{21})^T R  = QR\]

아래는 직접 짜본 MATLAB 코드다.

Householder Reflection

Householder reflection 행렬 H \in \mathbb{R}^{m\times n} 는 어떤 벡터에 그 벡터를 \mathbf{u} 로 투영한 벡터의 두배 만큼 뺀다. 즉, \mathbf{u} 가 직선의 단위 직교 벡터 (normal) 라면 H 는 임의의 벡터를 직선에 반사시키는 행렬이다. QR 분해에서는 반사시켜서 축에 정렬시킨다.

householder-reflection-graph

행렬 A 의 첫번째 열 \mathbf{a}_1 은 아래와 같이 소거되어 \mathbf{r}_1 을 만든다.

    \[H_1 = I - 2\mathbf{u}_1\mathbf{u}_1^T \qquad H_1 \mathbf{a}_1 =  \begin{bmatrix} ||\mathbf{a}_1|| \\ 0 \\ \vdots \\ 0 \\ \end{bmatrix} \ \text{or}\  \begin{bmatrix} -||\mathbf{a}_1|| \\ 0 \\ \vdots \\ 0 \\ \end{bmatrix} = \mathbf{r}_1\]

\mathbf{u}_1\mathbf{a}_1 - \mathbf{r}_1 방향이다. H_1 A 의 오른쪽 아래 서브 행렬에 대해서 계속 서브 반사 행렬 Q_k = \begin{bmatrix}I_{k-1} & 0 \\ 0 & H_k\end{bmatrix} 를 곱하면 결과적으로 상삼각화된다.

    \[(Q_{n} \dots Q_3 Q_2 Q_1) A = R\]

H_k, Q_k 는 직교행렬이면서 대칭행렬이다. 따라서 식을 정리하면,

    \[\begin{aligned} A &= (Q_1 Q_2 Q_3 \dots Q_{n}) R = QR \\ A_{m\times n} &= Q_{m\times m}R_{m\times n} \end{aligned}\]

전체 과정은 \mathbb{C}^{m\times n} 에서도 성립한다.

아래는 직접 짜본 MATLAB 코드다.

Hessenberg Decomposition

Hessenberg 행렬이란 sub diagonal 또는 super diagonal 성분까지 포함한 삼각행렬을 말한다. 예를 들어 5\times 5 upper Hessenberg 행렬은 다음과 같은 형태다.

    \[H = \begin{bmatrix} \times & \times & \times & \times & \times \\ \times & \times & \times & \times & \times \\ 0 & \times & \times & \times & \times \\ 0 & 0 & \times & \times & \times \\ 0 & 0 & 0 & \times & \times\\ \end{bmatrix}\]

직교행렬 Q 를 이용해서 정방행렬 A 를 상삼각 형태로 변환했던 것 처럼, 직교행렬 Q 를 이용해서 A 를 upper Hessenberg 형태로 만들 수 있다. Householder reflection 행렬 Q_{k+1} = \begin{bmatrix}I_{k} & 0 \\ 0 & H_{k+1}\end{bmatrix} 을 사용할 수 있다. 원리는 Householder reflection 과 같지만 한단계 아래 성분들에 대해서 소거하는 것이다.

    \[\begin{aligned} Q_2 A &= \begin{bmatrix} 1 & 0^T \\  \mathbf{0} & H_2 \\ \end{bmatrix} \begin{bmatrix} a_{11} & \dots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \dots & a_{nn}   \end{bmatrix} \\ &=  \begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ \multicolumn{4}{c}{H_2 \begin{bmatrix}   a_{21} & \dots & a_{2n} \\   \vdots & \ddots & \vdots \\   a_{n1} & \dots & a_{nn}     \end{bmatrix}} \end{bmatrix} \\ &=  \begin{bmatrix} \times & \times & \dots \\  \times & \times & \dots \\ 0 & \times & \dots \\ \vdots & \vdots & \ddots \\ 0 & \times & \dots \end{bmatrix} \end{aligned}\]

Q_{k+1}k 번째 열을 upper Hessenberg form 으로 만든다. n-2 번 적용하면,

    \[(Q_{n-1} \dots Q_3 Q_2) A = H\]

여기서 H 는 upper Hessenberg 행렬이다.

Similar Hessenberg matrix

Q_{k+1}^T = Q_{k+1} 을 오른쪽에 곱하면 왼쪽 서브 행렬 (n\times k) 을 유지한다. 예를 들어 Q_2 A Q_2 는 결과 행렬의 형태 (왼쪽 서브 행렬 (n\times 1) 에 대해서만 upper Hessenberg form) 를 유지하는 닮음 변환을 나타낸다.

    \[\begin{aligned} Q_2 A Q_2 &= \begin{bmatrix} 1 & 0^T \\  \mathbf{0} & H_2 \\ \end{bmatrix} \begin{bmatrix} a_{11} & \dots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \dots & a_{nn}   \end{bmatrix}  \begin{bmatrix} 1 & 0^T \\  \mathbf{0} & H_2 \\ \end{bmatrix} \\ &=  \begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ H_2 \begin{bmatrix}   a_{21} \\ \vdots \\ a_{n1}   \end{bmatrix} & \multicolumn{3}{c}{H_2 \begin{bmatrix}   a_{22} & \dots & a_{2n} \\   \vdots & \ddots & \vdots \\   a_{n2} & \dots & a_{nn}     \end{bmatrix}} \end{bmatrix}  \begin{bmatrix} 1 & 0^T \\  \mathbf{0} & H_2 \\ \end{bmatrix} \\ &= \begin{bmatrix} a_{11} & \begin{bmatrix}a_{12} & \dots & a_{1n}\end{bmatrix} H_2 \\ H_2 \begin{bmatrix}   a_{21} \\ \vdots \\ a_{n1}   \end{bmatrix} & \multicolumn{3}{c}{H_2 \begin{bmatrix}   a_{22} & \dots & a_{2n} \\   \vdots & \ddots & \vdots \\   a_{n2} & \dots & a_{nn}   \end{bmatrix} H_2 } \end{bmatrix}  =  \begin{bmatrix} \times & \times & \dots \\  \times & \times & \dots \\ 0 & \times & \dots \\ \vdots & \vdots & \ddots \\ 0 & \times & \dots \end{bmatrix} \end{aligned}\]

따라서

    \[(Q_{n-1} \dots Q_3 Q_2) A (Q_2 Q_3 \dots Q_{n-1}) = H\]

upper Hessenberg 행렬 H 는 행렬 A 와 닮음이다. 만약 A 가 대칭행렬이라면 결과는 대칭 삼중 대각 행렬 (symmetric tridiagonal matrix) 이 된다는 것을 알 수 있다.

아래는 직접 짜본 MATLAB 코드다.

Leave a Reply

Your email address will not be published. Required fields are marked *