CS205A Lecture 5 Column spaces and QR

课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第五讲,这一讲主要介绍了$QR$分解。

Chapter 4 列空间和$QR$分解

正规方程的结构

上一讲主要介绍了对称矩阵的一些性质,现在考虑$A^TA$的条件数:

这说明如下方程更加不稳定:

注意到

所以如果我们有

那么就不会有不稳定的情形发生,这就引入了正交性的概念。

正交性

对于矩阵

我们计算$Q^T Q$

如果

那么

我们给出如下定义:

定义 4.1 (正交性,正交矩阵)

一组向量$\{\vec v_1,…,\vec v_k \}$正交当且仅当

如果一个方阵的列向量正交,那么称其为正交矩阵。

性质

正交矩阵有如下一些性质:

  1. 这一点是显然的,由逆矩阵的定义即可得到。这个性质告诉我们正交矩阵的逆可以直接得到,大大减少了运算量。

  2. 这个性质表明正交矩阵保持内积不变。

  3. 对性质2中取$\vec x =\vec y$,那么

    这个性质表明正交矩阵保持模长不变。

由性质2,3,我们知道$Q$对应于几何变换,即保持长度和角度不变。

对非正交矩阵的处理

首先回顾我们一直讨论的问题:

从几何角度来看,可以理解为上述问题是在将$\vec b$投影到$A$的列空间,所以这一部分主要从列空间的角度讨论,我们先给出如下引理:

引理 4.1 (列空间的不变性)

对于任意$A\in \mathbb R^{m\times n}$和可逆矩阵$B\in \mathbb R^{n\times n}$,我们有

证明:$\forall \vec b \in \text{col }A​$,存在$\vec x​$,使得

因为$B​$可逆,所以

所以

$\forall \vec c \in \text{col }AB​$,存在$\vec y​$,使得

所以

因此

上述性质提醒我们可以使用初等列变换对$A$进行操作,直至其变成正交矩阵,即

如果$E_i$可逆,那么上述引理告诉我们

那么

如果得到上述分解,考虑正规方程

那么我们有

或者等价的

如果我们设计$R$为三角阵,那么求解$R\vec x = Q^T \vec b$只是在执行back-substitution。关于$QR$分解,常见的有两种方法,分别在后面介绍。

Gram-Schmidt正交化

介绍Gram-Schmidt正交化之前,首先考虑投影问题。

投影

投影问题的形式如下:对于向量$\vec a ,\vec b$,下式何时最小

这是$A\vec x =\vec b$的特殊形式,我们知道上述问题的解为

我们称如下量为$\vec b $在$\vec a$上的投影:

接着,我们考虑残差$\vec b - \text{proj}_{\vec a} \vec b$和$\vec a ​$的关系:

上述事实告诉我们,我们将$\vec b$分解为平行于$\vec a $的部分和正交于$\vec a​$的部分。

现在,假设向量$\hat a_1 ,\hat a_2,…,\hat a_k​$正交($||\hat a_i ||=1​$),那么对于每个$i​$,我们有

进一步,我们可以将$\vec b$投影到$\{\hat a_1 ,\hat a_2,…,\hat a_k\}$张成的子空间,通过对下式关于$c_1,…,c_k \in \mathbb R$最小化,

最后一步是因为

对上式关于$c_i$求偏导,不难得到

所以

并且不难得到

将上述内容整理一下即得到Gram-Schmidt正交化方法:

输入:线性独立的向量$\{\vec v_1 ,…\vec v_k\}​$

输入:正交基$\{\hat v_1 ,…\hat v_k\}$

  1. 对$i=2…k$

    1. 计算

不难发现,对所有的$i$,我们有

Gram-Schmidt正交化可以解决很多问题,但有时候会产生数值不稳定性,考虑如下列子

此时显然有正交基

但是如果使用Gram-Schmidt正交化,则有

注意到

如果$\epsilon $很小,那么除以上述量会产生计算问题。

Householder变换

Householder变换采取高斯消元法的思路,我们不断左乘正交矩阵$Q_i$,最终将$A$变为上三角矩阵,具体形式如下

所以

注意正交矩阵有无数种,Householder变换选择特殊的正交矩阵——反射矩阵,这是因为反射矩阵可以很方便的用投影表示出来。事实上,$2\text{proj}_{\vec v} \vec b -\vec b$为$\vec b$关于$\vec v $的反射向量,并且

所以反射可以看成对$\vec b​$做线性变换,事实上,我们还有

从而$H_{\vec v}$为正交矩阵,我们利用这一点来介绍Householder变换。

假设我们在做高斯消元法forward substitution的第一步,记矩阵$A$的第一列为$\vec a $,第一个单位向向量为$\vec e_1$,那么第一步消元的效果为除了第一行第一列元素以外都变成$0​$,即

所以

移项可得

所以$\vec v$平行于$\vec a -c\vec e_1$,因为$\vec v$的模长不改变$H_{\vec v}$,所以不妨选择

从而

现在将上述步骤推广,假设进行到第$k$步,记$A$的第$k​$列为

其中$\vec a _1 \in \mathbb R^{k-1},\vec a _2 \in \mathbb R^{n-k+1}$,$a_0$是实数,消元以后的结果为

所以

同之前讨论,我们取

所以

所以最终结果为

约化的$QR$分解

之前讨论的操作都是在方阵上,对于非方阵$A\in \mathbb R^{m\times n }$也可以进行同样的操作,但是Gram-Schmidt正交化和Householder变换的结果有一些不同:

  • 如果使用Gram-Schmidt正交化,因为使用的是列变换,所以最终结果为

  • 如果使用Householder变换,因为是使用正交矩阵进行消元,所以最终结果为

假设现在有$m\gg n$,因为数值稳定性,我们更倾向于使用Householder变换,但是$m\times m$的矩阵可能非常大,幸运的是,我们知道$R$为上三角矩阵,所以

因此

这里

这种形式被称为$A$的约化的$QR$分解。

本文标题:CS205A Lecture 5 Column spaces and QR

文章作者:Doraemonzzz

发布时间:2019年03月27日 - 00:59:00

最后更新:2019年03月27日 - 01:31:43

原始链接:http://doraemonzzz.com/2019/03/27/CS205A Lecture 5 Column spaces and QR/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。