CS205A Lecture 8 Eigenproblems III; QR iteration, conditioning; singular value decomposition (SVD)

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

这次回顾第八讲,这一讲继续介绍了如何计算特征值,然后介绍了SVD。

克里洛夫(Krylov) 子空间法

考虑如下矩阵:

通过研究上述矩阵来求特征值和特征向量的方法被称为克里洛夫子空间法,事实上,我们有如下算法:

Arnoldi迭代

  1. 选择$\vec q_1 \in \mathbb R^n$为任意单位向量。

  2. 对$k=2,3,…​$

    • 令$\vec a_k =A\vec q_{k-1}$

    • 减去投影:

    • 正规化,计算$\vec q_k =\vec b_k /\Arrowvert \vec b_k\Arrowvert$

由上述正交向量构成的矩阵$Q_k$和$K_k$的列空间相同,所以我们可以通过研究$Q_k^T AQ_k​$来计算特征值,注意到因为使用了Gram-Schmidt正交化方法,所以上述方法不稳定。

(备注:这部分讲的很简略,可以忽略,详细的请参考科学计算导论4.5节)

敏感性

最后一部分,我们来分析求解特征值的敏感性,即:

展开可得

忽略高阶无穷小,我们得到

因为

所以

由(1)可得

因为$\vec x$非零,所以

所以存在$\vec y$,使得

对(2)左乘$\vec y^T$可得

由(3)可得

假设

对(4)两边取模得到

如果$A$对称,那么

上式可化为

Chapter 6 奇异值分解(SVD)

推导SVD

对于矩阵$A\in \mathbb R^{m\times n}$,可以将其视为映射$\mathbb R^n $到$\mathbb R^m$的映射$\vec x \mapsto A\vec x $,我们考虑该映射对向量模长的影响:

注意到我们有

所以我们可以增加限制条件

因此我们可以考虑

由之前章节的内容,我们知道在$\Arrowvert \vec x \Arrowvert =1$条件下研究(1)和特征值有密切关系,即

因为$A^TA$是对称矩阵,所以对$i\neq j​$,我们有

以及

对于$A^TA$的特征向量$\vec x_i$,考虑

我们有

所以$\vec y_i ​$是$AA^T​$对应于特征值$\lambda_i ​$的特征值向量,并且

所以如果$\lambda_i =0​$,那么$\vec y_i =\vec 0​$,因此有如下引理:

引理

令$k​$是$A^TA​$大于$0​$的特征值数量,对应特征值为$\lambda_1,…,\lambda_k​$,相应特征向量为$\vec x_1 ,…,\vec x_k \in \mathbb R^n​$,我们取

如果我们假设

那么我们由(4)可得

并且

所以我们定义

记$\vec e_i$为第$i$个标准正交基向量,考虑$\bar U^T A\bar V$的第$i$列:

那么

由基扩张定理,可以对

补充满足如下条件的正交基

将其扩张为

对于$i\ge k+1$,类似之前讨论,不难得到

因此,如果我们构造矩阵$\Sigma \in \mathbb R^{m\times n}$,其中

那么

上式分解被称为$A$的奇异值分解,$\Sigma $的对角线元素$\sigma_i$被称为$A$的奇异值,实际中我们一般假设$\sigma_1\ge \sigma_2\ge …\ge 0$,$U,V$为正交矩阵,$U$的列被称为$A$的左奇异向量,$V$的列被称为$A$的右奇异向量。

上述分解告诉我们一个事实,每个线性变换都可以表示为旋转——伸缩——旋转的复合。

计算SVD

注意到$V$是$A^TA$的特征向量,所以$V$和$\Sigma$可以用之前介绍的方法计算。因为$A=U\Sigma V^T$,所以

因此非$0​$奇异值对应的$\vec u_i​$即为$AV​$标准化的列,其余的$\vec u_i​$可以利用

计算,这部分可以利用$LU​$分解得到。

本文标题:CS205A Lecture 8 Eigenproblems III; QR iteration, conditioning; singular value decomposition (SVD)

文章作者:Doraemonzzz

发布时间:2019年04月03日 - 00:50:00

最后更新:2019年06月01日 - 09:34:13

原始链接:http://doraemonzzz.com/2019/04/03/CS205A Lecture 8 Eigenproblems III; QR iteration, conditioning; singular value decomposition (SVD)/

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