Householder变换
Householder变换是一种简洁而有意思的线性变换，也可称为镜面反射变换，Householder变换矩阵为
H
=
I
−
w
T
w
H=I-w^Tw
H
=
I
−
w
T
w
考虑向量
α
\alpha
α
和一个单位向量
w
:
w
T
w
=
1
w:w^{T}w=1
w
:
w
T
w
=
1
α
\alpha
α
在
w
w
w
方向上的分量是
α
w
/
/
=
(
w
T
α
)
w
=
w
w
T
α
\alpha _{w_{//}}=\left( w^{T}\alpha \right) w=ww^{T}\alpha
α
w
//
=
(
w
T
α
)
w
=
w
w
T
α
则
α
\alpha
α
关于以
w
w
w
为法向量的平面的镜面反射为
α
−
2
α
w
/
/
=
α
−
2
w
w
T
α
=
(
I
−
2
w
w
T
)
α
=
H
α
\alpha -2\alpha _{w_{//}}=\alpha -2ww^{T}\alpha =\left( I-2ww^{T}\right) \alpha =H\alpha
α
−
2
α
w
//
=
α
−
2
w
w
T
α
=
(
I
−
2
w
w
T
)
α
=
H
α
考虑以下两个特殊向量
H
w
=
(
I
−
2
w
w
T
)
w
=
w
−
2
w
(
w
T
w
)
=
−
w
v
:
w
T
v
=
0
,
H
v
=
(
I
−
2
w
w
T
)
v
=
v
−
2
w
(
w
T
v
)
=
v
\begin{aligned} &Hw=\left( I-2ww^{T}\right) w=w-2w\left( w^{T}w\right) =-w\\ &v:w^{T}v=0,Hv=( I -2ww^{T}) v=v-2w\left( w^{T}v\right) =v \end{aligned}
H
w
=
(
I
−
2
w
w
T
)
w
=
w
−
2
w
(
w
T
w
)
=
−
w
v
:
w
T
v
=
0
,
H
v
=
(
I
−
2
w
w
T
)
v
=
v
−
2
w
(
w
T
v
)
=
v
对于向量
w
w
w
，Householder矩阵的作用是将其反向，对于垂直于向量
w
w
w
的向量
v
v
v
，Householder矩阵对其不产生改变。那么对于一般的向量
α
\alpha
α
，经过Householder矩阵作用后，平行于
w
w
w
的分量反向，垂直于
w
w
w
的分量保持不变。其整体作用是将向量关于法向量为
w
w
w
的平面做镜面对称。
于是也可以得到，Householder变换不改变向量模长，是一种正交变换。两次镜面变换后将反射为自身，同时也是一种对合变换。即
H
H
T
=
I
,
H
2
=
I
HH^{T}=I,H^{2}=I
H
H
T
=
I
,
H
2
=
I
下面从代数层面考虑，上式表明 -1,1为Householder矩阵的特征值。对于向量
w
w
w
,可以找到n-1个向量构成n维欧式空间的一组标准正交基。记
Q
=
[
w
,
v
1
,
v
2
,
…
,
v
n
−
1
]
Q=\left[ w,v_{1},v_{2},\ldots ,v_{n-1}\right]
Q
=
[
w
,
v
1
,
v
2
,
…
,
v
n
−
1
]
，有：
I
=
Q
Q
T
=
w
w
T
+
∑
i
=
1
n
−
1
v
i
v
i
T
H
=
I
−
2
w
w
T
=
−
w
w
T
+
∑
i
=
1
n
−
1
v
i
v
i
T
=
Q
(
−
1
1
⋱
1
)
Q
T
\begin{aligned} I&=QQ^{T}=ww^{T}+\sum ^{n-1}_{i=1}v_{i}v_{i}^{T}\\ H&=I-2ww^{T}=-ww^{T}+\sum ^{n-1}_{i=1}v_{i}v_i^{T}=Q\begin{pmatrix} -1 & & & \\ & 1 & & \\ & & \ddots & \\ & & & 1 \end{pmatrix}Q^{T} \end{aligned}
I
H
=
Q
Q
T
=
w
w
T
+
i
=
1
∑
n
−
1
v
i
v
i
T
=
I
−
2
w
w
T
=
−
w
w
T
+
i
=
1
∑
n
−
1
v
i
v
i
T
=
Q
−
1
1
⋱
1
Q
T
上式给出了Householder的对角化过程，可以看出其更本质的特征。通过秩为1的矩阵
w
w
T
ww^T
w
w
T
改变了单位矩阵的一个特征值，进而改变其一个特征向量上的缩放变换。
Householder变换用于QR分解
可以通过Householder变换可以将向量
x
x
x
变换为任意相同模长的向量
y
y
y
：
H
x
=
y
H x = y
H
x
=
y
其中
H
=
I
−
w
T
w
H=I-w^Tw
H
=
I
−
w
T
w
，由Householder变换的本质是法向量为
w
w
w
的平面的镜像对称可知
x
−
y
=
∥
x
−
y
∥
w
⟹
w
=
x
−
y
∥
x
−
y
∥
x-y=\lVert x-y \rVert w\\ \implies w=\dfrac{x-y}{\lVert x-y \rVert}
x
−
y
=
∥
x
−
y
∥
w
⟹
w
=
∥
x
−
y
∥
x
−
y
而利用Householder变换的上述性质可以进行QR分解：
对于任意非奇异矩阵
A
=
[
a
1
a
2
⋯
a
n
]
A=\begin{bmatrix}a_1&a_2&\cdots & a_n\end{bmatrix}
A
=
[
a
1
a
2
⋯
a
n
]
，首先利用Householder变换将
A
A
A
矩阵的第一列除第一个元素外全部变成0
H
1
a
1
=
β
e
1
H_1 a_1 = \beta e_1
H
1
a
1
=
β
e
1
e
i
e_i
e
i
是第i个元素为1的单位向量。
H
1
A
=
[
H
1
a
1
H
1
A
′
]
=
[
∗
∗
0
A
^
1
]
H_1 A = \begin{bmatrix}H_1 a_1& H_1A’\end{bmatrix}=\begin{bmatrix}*&*\\0&\hat{A}_1\end{bmatrix}
H
1
A
=
[
H
1
a
1
H
1
A
′
]
=
[
∗
0
∗
A
^
1
]
从而我们可以迭代地对维度减一的矩阵
A
^
1
\hat{A}_1
A
^
1
进行上述求解，得到
H
^
2
\hat H_2
H
^
2
，则令
H
2
=
(
1
0
0
H
^
2
)
H_2=\left(\begin{matrix}1 &0 \\0 &\hat H_2\end{matrix}\right)
H
2
=
(
1
0
0
H
^
2
)
，则：
H
^
2
A
^
1
=
[
∗
∗
0
A
^
2
]
\hat{H}_2 \hat{A}_1=\begin{bmatrix}*&*\\0&\hat{A}_2\end{bmatrix}
H
^
2
A
^
1
=
[
∗
0
∗
A
^
2
]
以此类推接着对
A
^
2
\hat{A}_2
A
^
2
做Householder变换将其第一列除第一元素外变为0。
最终迭代可以得到
H
n
−
1
⋯
H
2
H
1
A
=
R
H_{n-1}\cdots H_2H_1 A=R
H
n
−
1
⋯
H
2
H
1
A
=
R
则
Q
T
=
H
n
−
1
⋯
H
2
H
1
Q^T=H_{n-1}\cdots H_2H_1
Q
T
=
H
n
−
1
⋯
H
2
H
1
Givens变换