矩阵的QR分解
打开本页，如果没有显示公式，请刷新页面。
QR分解是一种重要的矩阵分解方式，《机器学习数学基础》的第3章3.5.1节“QR分解”对此做了最基本的介绍，此处在该基础上，对QR分解给予适当拓展。
QR分解目前已知三种算法：
- 格拉姆-施密特正交化(Gram-Schmidt)方法，这种方法在《机器学习数学基础》中有详细介绍。
- 豪斯霍尔德变换（Householder transformation）
- 吉文斯旋转法（Givens）
豪斯霍尔德变换
豪斯霍尔德变换（Householder transformation），又称初等反射（elementary reflection）。最初由A.C Aitken在1932年提出。阿尔斯通·斯科特·豪斯霍尔德在1958年指出了这一变换在数值线性代数上的意义 。
通过豪斯霍尔德变换，一个向量能实现“超平面反射”的线性变换，实现这种线性变换的矩阵被称作豪斯霍尔德矩阵，超平面的法向量被称作豪斯霍尔德向量。
定义
设 是单位向量， 是单位矩阵，豪斯霍尔德矩阵为：
其中 是 的共轭转置（在实数范围内，即转置 ）。
设任一向量 ，通过豪斯霍尔德矩阵，可以得到其镜像向量，如下图所示，可以表示为（在实数范围内）：
下面用正交投影推导镜像变换 ：
根据《机器学习数学基础》第3章3.4.4节的投影矩阵，可得：
其中 是单位法向量。
因为镜像超平面是法向量的正交补（参阅“直和与投影”），如上图，向量 至镜面的正交投影为： ，所以 的镜像是：
特征值
对（1.1）式，若 ，则：
由此可知， 有一个特征向量 ，对应的特征值是 。
对于 ，超平面的维度是 ，设此超平面上的 个线性无关的向量 ，则它们满足：
所以：
这说明 有 个重复特征值 ，所以 ， 是可逆矩阵。
性质
- 是对称矩阵，
- 是正交矩阵，
- 是埃尔米特矩阵，
- 是对合的，
应用
豪斯霍尔德变换可以将向量的某些元素变成零，同时保持该向量的范数不变。例如，列向量 ，通过豪斯霍尔德变换，成为单位向量 乘以一个常数的豪斯霍尔德矩阵：
其中豪斯霍尔德向量 ：
对一个矩阵的各个列向量逐一进行相应的豪斯霍尔德变换，可以将这个矩阵变换为上海森伯格矩阵、上三角矩阵等形式。后者就是QR分解的豪斯霍尔德算法。
之所以能如此，原因在于：通过选择适当的超平面法向量 （单位向量），可以使得镜像映射的向量 与单位向量 的方向一致，即除了第一个元之外， 的其他元素都是 。简单论证此中情形的可行性：
设 ，满足 （令 ，此处也可以假设满足 ，如果如此假设，相应符号进行修改），则有：
这说明 和 同向，故可令：
则：
根据假设，可知 ，则：
将上式结果代入到（1.2）式，可得：
由此，可以看出，利用豪斯霍尔德矩阵能够实现对称矩阵的三角化 。
设 的矩阵 ，以列向量的形式表示 。令 ，且：
构建豪斯霍尔德矩阵 ：
用 左乘矩阵 ，得：
其中 ， 为右下 的分块矩阵。
按照上述方式，对 执行类似的正交化简，设计 的豪斯霍尔德矩阵 ：
其中 ，用 左乘 ，得：
若 ，连续左乘 个 的豪斯霍尔德矩阵，可是 化简为：
其中 是 的上三角矩阵。
因为 ，由（1.3）式可得 的QR分解：
用豪斯霍尔德变换对矩阵 进行QR分解
令 为 矩阵 的任一 维列向量（），且 （其中 为标量）。（以下演示中，假设 为实矩阵）
设单位向量 ，令：
则豪斯霍尔德矩阵为：
满足：
例如： ，进行QR分解。
列向量 ，令 ，则：
所以：
从而：
对上述所得矩阵，令 ，则 ，则：
记：
则：
通过上述示例，总结利用豪斯霍尔德变换进行QR分解的步骤：
选矩阵第一列的列向量，计算出相应的豪斯霍尔德矩阵 ；
计算： ，得到第一列除第一个值之外其余都为零的矩阵，如下图所示：
对于上图中的分块矩阵 ，重复执行以上两步。从而得到 ；
加上以上迭代过程为 次，则：
优势
相比于格拉姆-施密特正交化方法，豪斯霍尔德变换具有更好的数值稳定性 。
吉文斯旋转
对 选两个坐标轴 ， 。吉文斯旋转的 阶矩阵：
其中， ，吉文斯旋转矩阵 的所有非零元：
乘积 表示向量 在 平面中逆时针旋转 弧度。
例如 阶吉文斯旋转矩阵：
以向量 为例，分别计算：
吉文斯旋转矩阵 乘以此向量： ，如此将原向量底部的元素转换为 。每次用吉文斯旋转矩阵对向量（矩阵）进行旋转，都可以将一个元素化成 ，直到将原始矩阵转成一个上三角矩阵，则实现了分解。
例如： 阶矩阵：
用吉文斯旋转矩阵的目标是将矩阵主对角线以下的所有元变为 ，按照如下步骤依次进行。
将 的 位置元素变为 ，对应的吉文斯旋转矩阵设为 ，即 。以 的第一列 来设定 的参数：
旋转后得到：
上一步中所得到的矩阵 中 位置的元素再转换为 ，其所在列向量 ，设定相应的吉文斯旋转矩阵 ：
旋转后得：
上面所得矩阵中的 位置的元素，转换为 ，所在列向量 ，则：
旋转后得：
经过连续三次旋转那之后，可以表示为：
则矩阵 可以分解为：
因为吉文斯旋转矩阵是正交矩阵， ，因此矩阵 的QR分解为：
其中 。正交矩阵的积还是正交矩阵，即 。
注意，通过吉文斯旋转得到的 QR分解形式，与格拉姆-施密特正交化所得形式有所不同。
参考文献
[1]. https://ccjou.wordpress.com/2010/02/18/givens-旋轉於-qr-分解的應用/
[2]. https://zh.wikipedia.org/wiki/豪斯霍尔德变换
[3]. 所谓对合（involution），也称为对核函数，即逆（反）函数等于自身的函数。在线性代数中，对合是线性算子 使得 。这种算子可对角化为对角线上有 和 。如果这个算子是正交的（称为正交对合），它是正交可对角化的。
[4]. https://zh.wikipedia.org/wiki/QR分解
[5]. https://ccjou.wordpress.com/2009/09/14/特殊矩陣-四：householder-矩陣/
作者: 老齐
链接: http://math.itdiffer.com/qr_decomposition.html
来源: 机器学习
本文原创发布于「机器学习」,转载请注明出处,谢谢合作!
