6.50 하우스홀더 변환과 기븐스 회전

1. 도입

수치 선형대수학에서 행렬을 점진적으로 단순한 형태로 변환하는 직교 변환은 핵심적인 도구이다. 그러한 변환은 노름과 조건수를 보존하므로 수치적으로 매우 안정하며, 다양한 행렬 분해와 고유값 계산 알고리듬의 토대를 이룬다. 그 중에서도 가장 중요한 두 가지 도구가 하우스홀더 변환(Householder transformation)과 기븐스 회전(Givens rotation)이다. 하우스홀더 변환은 한 번의 적용으로 한 벡터의 여러 원소를 동시에 영으로 만들 수 있는 거울 반사이며, 기븐스 회전은 한 번에 두 원소 중 하나만을 영으로 만드는 평면 회전이다. 이 두 도구는 서로 보완적인 성질을 가지며, 응용의 특성에 따라 적절히 선택된다.

2. 하우스홀더 변환의 정의

정의. 비영벡터 $\mathbf{v} \in \mathbb{R}^n$ 가 주어졌을 때, 하우스홀더 변환은 다음과 같이 정의되는 행렬이다.

$H(\mathbf{v}) = I - 2 \frac{\mathbf{v}\mathbf{v}^\top}{\mathbf{v}^\top \mathbf{v}}$

벡터 $\mathbf{v}$ 를 하우스홀더 벡터(Householder vector) 또는 반사 벡터라 한다. 이 정의는 $\mathbf{v}$ 의 스칼라 배에 의존하지 않으므로 종종 단위 벡터 $\hat{\mathbf{v}} = \mathbf{v}/\|\mathbf{v}\|$ 를 사용하여 다음과 같이 단순화된다.

$H = I - 2 \hat{\mathbf{v}} \hat{\mathbf{v}}^\top$

3. 하우스홀더 변환의 핵심 성질

하우스홀더 변환은 다음의 핵심 성질들을 가진다.

3.1 대칭성

$H^\top = (I - 2\hat{\mathbf{v}}\hat{\mathbf{v}}^\top)^\top = I - 2\hat{\mathbf{v}}\hat{\mathbf{v}}^\top = H$

따라서 하우스홀더 변환은 대칭 행렬이다.

3.2 직교성

$H^\top H = H^2 = (I - 2\hat{\mathbf{v}}\hat{\mathbf{v}}^\top)(I - 2\hat{\mathbf{v}}\hat{\mathbf{v}}^\top) = I - 4\hat{\mathbf{v}}\hat{\mathbf{v}}^\top + 4\hat{\mathbf{v}}\hat{\mathbf{v}}^\top \hat{\mathbf{v}}\hat{\mathbf{v}}^\top$

$\hat{\mathbf{v}}^\top \hat{\mathbf{v}} = 1$ 이므로 $\hat{\mathbf{v}}\hat{\mathbf{v}}^\top \hat{\mathbf{v}}\hat{\mathbf{v}}^\top = \hat{\mathbf{v}}\hat{\mathbf{v}}^\top$ 이고, 따라서 $H^\top H = I$ 이다. 즉, 하우스홀더 변환은 직교 행렬이다.

3.3 멱등성과 자기 역

대칭이면서 직교이므로 $H^{-1} = H^\top = H$ 가 성립한다. 즉, 하우스홀더 변환은 자기 자신이 역행렬이다. 이는 한 번의 변환을 두 번 적용하면 원래 상태로 되돌아간다는 의미이며, 거울 반사의 본질적인 성질이다.

3.4 행렬식

하우스홀더 변환의 행렬식은 항상 $-1$ 이다. 이는 거울 반사가 좌표계의 방향성을 반전시키기 때문이다.

$\det H = -1$

3.5 고유값과 고유벡터

하우스홀더 변환은 고유값으로 $-1$ 을 한 번, $+1$ 을 $n-1$ 번 가진다. 고유값 $-1$ 에 대응하는 고유벡터는 $\hat{\mathbf{v}}$ 자신이며, 고유값 $+1$ 에 대응하는 고유 공간은 $\hat{\mathbf{v}}$ 에 직교하는 $n-1$ 차원 부분 공간이다.

4. 하우스홀더 변환의 기하학적 의미

하우스홀더 변환은 $\hat{\mathbf{v}}$ 에 수직인 초평면에 대한 거울 반사이다. 임의의 벡터 $\mathbf{x}$ 는 다음과 같이 분해될 수 있다.

$\mathbf{x} = (\hat{\mathbf{v}}^\top \mathbf{x}) \hat{\mathbf{v}} + \mathbf{x}_\perp$

여기서 $\mathbf{x}_\perp$ 는 $\hat{\mathbf{v}}$ 에 수직인 성분이다. 하우스홀더 변환을 적용하면

$H\mathbf{x} = -(\hat{\mathbf{v}}^\top \mathbf{x}) \hat{\mathbf{v}} + \mathbf{x}_\perp$

이 된다. 즉, $\hat{\mathbf{v}}$ 방향 성분의 부호만이 반전되고, 수직 성분은 그대로 유지된다. 이는 정확히 $\hat{\mathbf{v}}$ 에 수직인 초평면을 거울로 한 반사이다.

5. 하우스홀더 벡터의 구성

수치 선형대수학의 응용에서 가장 흔히 마주치는 문제는 주어진 벡터 $\mathbf{x}$ 를 단위 좌표 벡터의 양의 배수, 즉 $\alpha \mathbf{e}_1$ 로 사상하는 하우스홀더 변환을 구성하는 것이다. 이를 위한 표준 절차는 다음과 같다.

1단계. 부호 함수를 정의한다. 일반적으로 $\mathrm{sign}(0) = 1$ 로 약속한다.

2단계. 하우스홀더 벡터를 다음과 같이 구성한다.

$\mathbf{v} = \mathbf{x} + \mathrm{sign}(x_1) \|\mathbf{x}\| \mathbf{e}_1$

부호의 선택은 매우 중요하다. 만약 $\mathbf{v} = \mathbf{x} - \|\mathbf{x}\|\mathbf{e}_1$ 로 정의하면 $\mathbf{x}$ 가 $\mathbf{e}_1$ 에 가까울 때 두 양이 거의 상쇄되어 자릿수 손실이 발생한다. 위와 같이 부호를 선택하면 자릿수 손실을 항상 회피할 수 있다.

3단계. 결과로 얻는 변환은 다음과 같이 작용한다.

$H\mathbf{x} = -\mathrm{sign}(x_1) \|\mathbf{x}\| \mathbf{e}_1$

이로써 첫 번째 성분만 비영이고 나머지가 모두 영인 벡터가 얻어진다.

6. 하우스홀더 변환의 효율적 적용

하우스홀더 변환을 행렬의 모든 원소에 적용할 때 명시적으로 $H = I - 2\frac{\mathbf{v}\mathbf{v}^\top}{\mathbf{v}^\top\mathbf{v}}$ 를 형성한 후 곱셈을 수행하는 것은 비효율적이다. 대신 다음과 같은 구조를 활용한다.

행렬 $A$ 에 하우스홀더 변환을 좌측에서 적용한다고 하자.

$HA = A - 2\frac{\mathbf{v}(\mathbf{v}^\top A)}{\mathbf{v}^\top \mathbf{v}}$

이를 두 단계로 계산한다.

$\mathbf{w}^\top = \frac{2}{\mathbf{v}^\top\mathbf{v}} \mathbf{v}^\top A$ (행 벡터의 계산)
$HA = A - \mathbf{v}\mathbf{w}^\top$ (랭크 1 갱신)

이 계산은 $O(mn)$ 의 연산만을 요구하며, 명시적인 행렬 형성보다 훨씬 효율적이다. 또한 하우스홀더 벡터 $\mathbf{v}$ 만을 저장하면 변환을 재현할 수 있으므로 저장 공간도 절약된다.

7. 기븐스 회전의 정의

정의. 두 인덱스 $i < j$ 와 각도 $\theta$ 에 대하여 기븐스 회전 행렬 $G(i, j, \theta) \in \mathbb{R}^{n \times n}$ 는 단위 행렬에서 $(i,i), (i,j), (j,i), (j,j)$ 성분을 다음과 같이 변경한 행렬이다.

$G_{ii} = \cos\theta, \quad G_{ij} = -\sin\theta, \quad G_{ji} = \sin\theta, \quad G_{jj} = \cos\theta$

다른 모든 비대각 성분은 영이고, 다른 대각 성분은 $1$ 이다. 즉, 기븐스 회전은 $i$ 번째와 $j$ 번째 좌표가 형성하는 평면에서의 회전이며, 다른 좌표는 영향을 받지 않는다.

8. 기븐스 회전의 핵심 성질

기븐스 회전은 다음과 같은 핵심 성질들을 가진다.

8.1 직교성과 행렬식

기븐스 회전은 직교 행렬이며, 행렬식은 $+1$ 이다. 즉, 특수 직교 행렬에 속한다. 이는 회전이 좌표계의 방향성을 보존하기 때문이다.

8.2 역행렬

기븐스 회전의 역은 같은 평면에서의 반대 방향 회전이며, 단순히 부호를 반전시킨 형태이다.

$G(i, j, \theta)^{-1} = G(i, j, -\theta) = G(i, j, \theta)^\top$

8.3 한 원소의 영화

기븐스 회전의 가장 중요한 응용은 벡터의 한 원소를 영으로 만드는 것이다. 벡터 $\mathbf{x} \in \mathbb{R}^n$ 의 $j$ 번째 원소를 영으로 만들기 위해서는 $i$ 번째와 $j$ 번째 원소의 값을 이용하여 다음과 같이 회전 매개 변수를 결정한다.

$c = \frac{x_i}{\sqrt{x_i^2 + x_j^2}}, \qquad s = \frac{x_j}{\sqrt{x_i^2 + x_j^2}}$

이 매개 변수로 구성된 기븐스 회전 $G$ 를 적용하면

$(G\mathbf{x})_i = \sqrt{x_i^2 + x_j^2}, \qquad (G\mathbf{x})_j = 0$

이 된다. 다른 원소들은 변하지 않는다.

9. 기븐스 회전의 효율적 적용

기븐스 회전을 행렬에 적용할 때에도 명시적인 행렬 형성을 피할 수 있다. 행렬 $A$ 의 $i$ 행과 $j$ 행만이 변하므로, 다음의 계산만 수행하면 된다.

$A_{i,k}^{\text{new}} = c \cdot A_{i,k} + s \cdot A_{j,k}$

$A_{j,k}^{\text{new}} = -s \cdot A_{i,k} + c \cdot A_{j,k}$

각 열 $k$ 에 대하여 4번의 곱셈과 2번의 덧셈만이 필요하므로 총 비용은 $O(n)$ 이다.

10. 안정한 매개 변수 계산

$\sqrt{x_i^2 + x_j^2}$ 를 직접 계산하면 큰 값에 대해서는 오버플로우, 작은 값에 대해서는 언더플로우가 발생할 수 있다. 이를 방지하기 위한 안정한 알고리듬은 다음과 같이 구현된다.

만약 $|x_j| > |x_i|$ 이면 $t = x_i/x_j$ , $s = 1/\sqrt{1+t^2}$ , $c = ts$ .

그렇지 않으면 $t = x_j/x_i$ , $c = 1/\sqrt{1+t^2}$ , $s = tc$ .

이 방식은 항상 절댓값이 작은 비를 사용하므로 수치적으로 안정하다.

11. 두 도구의 비교

항목	하우스홀더	기븐스
종류	거울 반사 (행렬식 $-1$ )	회전 (행렬식 $+1$ )
한 번에 영화하는 원소 수	다수	하나
영향을 받는 행 또는 열	모두	두 개
한 번의 적용 비용	$O(mn)$	$O(n)$
희소 행렬 처리	부적합	매우 적합
점진적 갱신	어려움	자연스러움
병렬 처리	가능	가능

두 도구는 서로 보완적인 성질을 가지므로, 응용에 따라 적절한 선택이 필요하다.

12. QR 분해에서의 활용

12.1 하우스홀더 기반 QR 분해

하우스홀더 변환을 활용한 QR 분해는 다음의 절차를 따른다. $k$ 번째 단계에서 현재 행렬의 $k$ 번째 열 중 대각 아래 부분 벡터에 대한 하우스홀더 변환을 구성하고, 이를 $k$ 열부터 $n$ 열까지의 부분 행렬에 적용한다. 이 절차는 한 번의 변환으로 한 열의 모든 대각 아래 원소를 영으로 만든다.

전체 QR 분해의 비용은 약 $2mn^2 - \frac{2}{3}n^3$ 의 부동 소수점 연산이다. 이는 그람-슈미트 방법과 유사한 비용이지만, 수치적 안정성은 훨씬 우수하다.

12.2 기븐스 기반 QR 분해

기븐스 회전을 활용한 QR 분해는 한 번에 한 원소만을 영으로 만들면서 진행된다. 모든 대각 아래 원소들을 차례로 영으로 만들기 위해서는 약 $mn$ 개의 기븐스 회전이 필요하며, 총 비용은 약 $3mn^2$ 이다.

기븐스 방법은 하우스홀더보다 약간 느리지만, 두 가지 중요한 이점을 제공한다. 첫째, 희소 행렬에서 비영 원소의 패턴을 잘 보존한다. 둘째, 점진적 갱신이 자연스럽게 가능하여 새로운 행이 추가될 때 효율적으로 분해를 갱신할 수 있다.

13. 헤센버그 형식과 이대각 형식

하우스홀더 변환과 기븐스 회전은 행렬을 헤센버그 형식(Hessenberg form)이나 이대각 형식(bidiagonal form)으로 변환하는 데에도 사용된다. 헤센버그 형식은 부분 대각 아래 원소들이 영인 형식으로, 일반 행렬의 고유값 계산을 위한 QR 알고리듬의 전처리 단계로 사용된다. 이대각 형식은 위쪽 부분 대각만을 가지는 형식으로, SVD 계산의 전처리 단계로 사용된다.

14. 응용 사례별 선택 지침

다음은 두 도구의 선택에 대한 일반적인 지침이다.

밀집 행렬의 QR 분해: 하우스홀더가 표준이다.
희소 행렬의 QR 분해: 기븐스가 선호된다.
점진적 데이터의 처리: 기븐스가 자연스럽다.
고유값 계산의 전처리: 하우스홀더가 일반적이다.
GPU 병렬 구현: 기븐스가 더 적합하다.
새 행렬 생성보다는 변환만 필요한 경우: 둘 다 가능, 응용에 따라 선택.

15. 로봇공학에서의 응용

15.1 칼만 필터의 제곱근 형식

칼만 필터의 제곱근 형식 구현에서 기븐스 회전과 하우스홀더 변환이 모두 활용된다. 측정 갱신 단계에서 제곱근 공분산 행렬을 효율적으로 갱신하는 데 기븐스 회전이 자주 사용되며, 이는 공분산 행렬의 양정치성을 자동으로 보존한다.

15.2 시각 SLAM의 묶음 조정

시각 SLAM의 묶음 조정에서 형성되는 정규 방정식은 매우 큰 희소 행렬을 포함한다. 이를 효율적으로 처리하기 위하여 기븐스 회전 기반의 QR 분해가 사용되며, 이는 희소성 패턴을 보존하면서 점진적 갱신을 가능하게 한다.

15.3 자코비안의 효율적 갱신

매니퓰레이터의 자코비안이 인접한 자세 사이에서 점진적으로 변화하는 상황에서, 기븐스 회전을 활용하면 분해를 효율적으로 갱신할 수 있다. 이는 실시간 제어 루프에서 계산 부담을 크게 절감한다.

15.4 회전 행렬의 분해와 합성

3차원 회전 행렬을 일련의 기븐스 회전 또는 하우스홀더 변환으로 분해하는 것은 자세 표현과 조작에서 활용된다. 특히 기븐스 회전은 오일러 각 표현과 자연스러운 관계를 가진다.

15.5 적응형 신호 처리와 시스템 식별

로봇 센서의 적응형 신호 처리와 모델 식별에서 기븐스 회전 기반의 점진적 QR 분해가 사용된다. 새로운 측정이 도착할 때마다 분해를 갱신함으로써 실시간 처리가 가능해진다.

15.6 그래프 SLAM의 정보 행렬 처리

그래프 SLAM에서 정보 행렬에 대한 기븐스 회전 기반 QR 분해는 새로운 측정의 효율적인 통합과 최적화 변수의 갱신을 가능하게 한다. 또한 변수의 제거(marginalization)에서도 직교 변환이 핵심적인 역할을 수행한다.

15.7 모델 예측 제어의 활성 집합 방법

모델 예측 제어에서 등장하는 이차 계획법 문제의 활성 집합 방법은 제약의 추가와 제거에 따른 분해의 갱신을 요구한다. 기븐스 회전은 이러한 갱신을 효율적으로 수행하는 표준적인 도구이다.

참고문헌

Householder, A. S. (1958). Unitary triangularization of a nonsymmetric matrix. Journal of the ACM, 5(4), 339-342.
Givens, W. (1958). Computation of plane unitary rotations transforming a general matrix to triangular form. Journal of the SIAM, 6(1), 26-50.
Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
Trefethen, L. N., & Bau, D. (2022). Numerical Linear Algebra (25th Anniversary ed.). SIAM.
Demmel, J. W. (1997). Applied Numerical Linear Algebra. SIAM.
Higham, N. J. (2002). Accuracy and Stability of Numerical Algorithms (2nd ed.). SIAM.

Version: 1.0