하우스홀더 변환(Householder transformation)은 선형대수학에서 사용되는 선형 변환으로, 원점을 지나는 평면 또는 초평면에 대한 반사(reflection)를 나타낸다. 하우스홀더 반사(Householder reflection) 또는 기본 반사자(elementary reflector)라고도 불린다. 이 변환은 1958년 미국의 수학자 앨스턴 스콧 하우스홀더(Alston Scott Householder)가 발표한 논문에서 처음 사용된 것으로 알려져 있다.
정의
내적 공간 V에서 단위 벡터 u가 주어졌을 때, 하우스홀더 연산자는 다음과 같이 정의된다.
H_u(x) := x − 2⟨x, u⟩u
이 연산은 벡터 x를 u에 수직인 초평면에 대해 반사시키는 역할을 한다. 내적 공간이 복소수 공간인 경우에는 켤레 전치(conjugate transpose) 개념이 함께 사용된다.
하우스홀더 행렬
하우스홀더 변환에 대응하는 행렬을 하우스홀더 행렬(Householder matrix)이라고 하며, 단위 벡터 v에 대하여 다음과 같이 표현된다.
P = I − 2vv*
여기서 I는 항등행렬이고, v*는 v의 켤레 전치이다. 하우스홀더 행렬은 다음과 같은 주요 성질을 갖는다.
- 에르미트 행렬이다: P = P*
- 유니터리 행렬이다: P⁻¹ = P*
- 따라서 멱등행렬(involutory)이다: P = P⁻¹
- 고유값은 +1과 −1을 갖는다. v에 수직인 벡터에 대해서는 +1, v 자체에 대해서는 −1의 고유값이 대응한다.
- 행렬식(determinant)은 −1이다.
응용
하우스홀더 변환은 수치 선형대수학에서 널리 사용된다. 특히 다음과 같은 분야에서 활용된다.
- QR 분해(QR decomposition): 행렬을 상삼각행렬로 변환하는 과정에서 한 열씩 처리하여 Q와 R을 구하는 데 사용된다. 그람-슈미트 방법이나 기븐스 회전과 함께 QR 분해의 주요 방법 중 하나로 꼽힌다.
- 대칭 행렬의 3중대각화(tridiagonalization): 대칭 행렬을 하우스홀더 변환의 유사 변환(similarity transformation)을 통해 3중대각행렬로 변환하는 데 사용된다.
- 헤센베르크(Hessenberg) 형태로의 변환
- 고유값 계산을 위한 QR 알고리즘의 첫 단계
하우스홀더 변환의 장점은 행렬을 명시적으로 저장하지 않고 하나의 벡터만으로 표현할 수 있어 저장 공간과 계산량을 크게 줄일 수 있다는 점, 그리고 부동소수점 연산에서 수치적 안정성이 우수하다는 점이다. 하우스홀더 변환은 단일 하우스홀더 변환이 행렬의 모든 열에 동시에 작용할 수 있어 계산 비용이 낮다는 장점이 있으나, 병렬화가 어렵다는 한계가 있다. 이에 비해 기븐스 회전은 희소 행렬이나 병렬 계산 환경에서 선호되는 경향이 있다.
기하 광학에서의 응용
기하 광학에서 정반사(specular reflection)의 벡터 표현이 하우스홀더 행렬의 형태로 표현될 수 있다.
양자 계산에서의 응용
하우스홀더 변환은 유니터리 행렬이므로 양자 계산에서도 유용하게 사용된다. 그로버 알고리즘(Grover's algorithm)에서 오라클 함수의 표현이 하우스홀더 변환의 형태로 나타나는 것으로 알려져 있다.
관련 개념
하우스홀더 변환은 QR 분해, 그람-슈미트 방법, 기븐스 회전, 하우스홀더 행렬, 3중대각행렬, 헤센베르크 행렬, 케일리 변환(Cayley transform) 등과 관련이 있다. SIAM 뉴스는 20세기 최고의 알고리즘 10선 중 하나로 하우스홀더 변환을 선정한 바 있다.
