矩阵的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分解的步骤:

  1. 选矩阵第一列的列向量,计算出相应的豪斯霍尔德矩阵

  2. 计算: ,得到第一列除第一个值之外其余都为零的矩阵,如下图所示:

  3. 对于上图中的分块矩阵 ,重复执行以上两步。从而得到

  4. 加上以上迭代过程为 次,则:

优势

相比于格拉姆-施密特正交化方法,豪斯霍尔德变换具有更好的数值稳定性

吉文斯旋转

选两个坐标轴 。吉文斯旋转的 阶矩阵:

其中, ,吉文斯旋转矩阵 的所有非零元:

乘积 表示向量 平面中逆时针旋转 弧度。

例如 阶吉文斯旋转矩阵:

以向量 为例,分别计算:

吉文斯旋转矩阵 乘以此向量: ,如此将原向量底部的元素转换为 。每次用吉文斯旋转矩阵对向量(矩阵)进行旋转,都可以将一个元素化成 ,直到将原始矩阵转成一个上三角矩阵,则实现了分解。

例如 阶矩阵:

用吉文斯旋转矩阵的目标是将矩阵主对角线以下的所有元变为 ,按照如下步骤依次进行。

  1. 位置元素变为 ,对应的吉文斯旋转矩阵设为 ,即 。以 的第一列 来设定 的参数:

    旋转后得到:

  2. 上一步中所得到的矩阵 位置的元素再转换为 ,其所在列向量 ,设定相应的吉文斯旋转矩阵

    旋转后得:

  3. 上面所得矩阵中的 位置的元素,转换为 ,所在列向量 ,则:

    旋转后得:

经过连续三次旋转那之后,可以表示为:

则矩阵 可以分解为:

因为吉文斯旋转矩阵是正交矩阵, ,因此矩阵 的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
来源: 老齐教室-机器学习数学基础
本文原创发布于「老齐教室-机器学习数学基础」,转载请注明出处,谢谢合作!

https://gitee.com/qiwsir/images/raw/master/2021-2-15/1613357594979-1.png

results matching ""

    No results matching ""