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

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

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

克里洛夫(Krylov) 子空间法

考虑如下矩阵：

$$K_k=\left( \begin{matrix} \vec b & A\vec b & A^2 \vec b& \ldots & A^{k-1}\vec b \end{matrix} \right)$$

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

Arnoldi迭代

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

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

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

   • 减去投影：

     $$\vec b_k =\vec a_{k}-\text{proj}_{\text{span}\{\vec q_1,...,\vec q_{k-1}\}} \vec a_{k}$$
   • 正规化，计算$\vec q_k =\vec b_k /\Arrowvert \vec b_k\Arrowvert$

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

（备注：这部分讲的很简略，可以忽略，详细的请参考科学计算导论4.5节）

敏感性

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

$$(A+\delta A)(\vec x + \delta \vec x)=(\lambda+\delta \lambda)(\vec x +\delta \vec x)$$

展开可得

$$A\vec x+A\delta \vec x + \delta A.\vec x + \delta A.\delta \vec x=\lambda\vec x +\lambda \delta \vec x+\delta \lambda.\vec x +\delta \lambda.\delta \vec x$$

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

$$A\vec x+A\delta \vec x + \delta A.\vec x \approx \lambda\vec x +\lambda \delta \vec x+\delta \lambda.\vec x$$

因为

$$A\vec x =\lambda \vec x \tag 1$$

所以

$$A\delta \vec x + \delta A.\vec x \approx \lambda \delta \vec x+\delta \lambda.\vec x \tag 2$$

由(1)可得

$$(A-\lambda I_n ) \vec x =\vec 0$$

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

$$|A^T-\lambda I_n|=|A-\lambda I_n| =0$$

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

$$\begin{eqnarray*} (A^T -\lambda I_n) \vec y&& =\vec 0\\ A^T \vec y &&=\lambda \vec y\\ \vec y^T A&&=\lambda \vec y^T \tag 3 \end{eqnarray*}$$

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

$$\vec y^T(A\delta \vec x + \delta A.\vec x) \approx \vec y^T(\lambda \delta \vec x+\delta \lambda.\vec x )$$

由(3)可得

$$\begin{eqnarray*} \vec y^T\delta A.\vec x &&\approx \delta \lambda\vec y^T\vec x \\ \delta \lambda &&\approx \frac{\vec y^T(\delta A)\vec x}{\vec y^T\vec x} \tag 4 \end{eqnarray*}$$

假设

$$\Arrowvert \vec x \Arrowvert =\Arrowvert \vec y \Arrowvert =1$$

对(4)两边取模得到

$$|\delta \lambda| \underset \approx \le \frac{\Arrowvert \delta A\Arrowvert_2}{|\vec y^T\vec x|}$$

如果$A$对称，那么

$$\vec x = \vec y$$

上式可化为

$$|\delta \lambda| \underset \approx \le {\Arrowvert \delta A\Arrowvert_2}$$

Chapter 6 奇异值分解(SVD)

推导SVD

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

$$R(\vec x) =\frac{\Arrowvert A\vec x \Arrowvert}{\Arrowvert \vec x \Arrowvert}$$

注意到我们有

$$R(\alpha\vec x)= \frac{\Arrowvert A.\alpha \vec x \Arrowvert}{\Arrowvert \alpha \vec x \Arrowvert}= \frac{|\alpha |.\Arrowvert A\vec x \Arrowvert}{|\alpha |.\Arrowvert \vec x \Arrowvert}=R(\vec x)$$

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

$$\Arrowvert \vec x \Arrowvert =1$$

因此我们可以考虑

$$|R(\vec x)|^2= \Arrowvert A\vec x \Arrowvert^2 = \vec x^T A^T A \vec x \tag 1$$

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

$$A^T A \vec x_i= \lambda \vec x_i \tag 2$$

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

$$\vec x_i . \vec x_j =0$$

以及

$$\lambda_i \ge 0$$

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

$$\vec y_i =A\vec x_i \tag 3$$

我们有

$$\begin{aligned} \lambda_i \vec y_i &=\lambda_i. A\vec x_i\\ &=A(\lambda_i \vec x_i)\\ &=A(A^T A \vec x_i) &由(2)\\ &=(AA^T)(A\vec x_i)\\ &=(AA^T) \vec y_i \end{aligned}$$

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

$$\begin{eqnarray*} \Arrowvert \vec y_i\Arrowvert &&=\Arrowvert A\vec x_i\Arrowvert \\ &&=\sqrt{\Arrowvert A\vec x_i\Arrowvert^2}\\ &&=\sqrt{ \vec x_i^TA^T A \vec x_i}\\ &&= \sqrt{\lambda_i \vec x_i^T \vec x_i} &&由(1)\\ &&=\sqrt {\lambda_i} \Arrowvert \vec x_i \Arrowvert \tag 4 \end{eqnarray*}$$

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

引理

$$如果\vec x_i是A^TA属于\lambda_i的特征向量，\\ 那么\vec y_i =A\vec x_i或者是\vec 0，或者是AA^T属于\lambda_i的特征向量$$

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

$$\vec y_i =\frac1 {\sqrt {\lambda_i}} A\vec x_i \in \mathbb R^m \tag 5$$

如果我们假设

$$\Arrowvert \vec x_i\Arrowvert =1$$

那么我们由(4)可得

$$\Arrowvert \vec y_i\Arrowvert =\frac1 {\sqrt {\lambda_i}}\Arrowvert A\vec x_i\Arrowvert= \frac1 {\sqrt {\lambda_i}}\sqrt {\lambda_i} \Arrowvert \vec x_i \Arrowvert =1$$

并且

$$\begin{eqnarray*} A^TA\vec x_i &&=\lambda_i \vec x_i\tag 6\\ AA^T\vec y_i &&=\lambda_i \vec y_i\tag 7 \end{eqnarray*}$$

所以我们定义

$$\begin{eqnarray*} \bar V&&= \left( \begin{matrix} \vec x_1 & \ldots & \vec x_k \end{matrix} \right)\in \mathbb R^{n\times k} \tag 8\\ \bar U&&= \left( \begin{matrix} \vec y_1 & \ldots & \vec y_k \end{matrix} \right)\in \mathbb R^{m\times k}\tag 9 \end{eqnarray*}$$

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

$$\begin{aligned} \bar U^T A\bar V \vec e_i &=\bar U^T A \vec x_i &由\bar V的定义\\ &=\frac 1 {\lambda_i}\bar U^T A (\lambda_i\vec x_i )\\ &=\frac 1 {\lambda_i} \bar U^T A(A^TA\vec x_i) &由(2)\\ &=\frac 1 {\lambda_i}\bar U^T (AA^T)A\vec x_i \\ &=\frac 1 {\sqrt {\lambda_i}}\bar U^T (AA^T)\vec y_i &由(5)\\ &=\frac 1 {\sqrt {\lambda_i}}\bar U^T \lambda_i \vec y_i &由(7)\\ &={\sqrt {\lambda_i}}\bar U^T \vec y_i \\ &={\sqrt {\lambda_i}} \vec e_i&由(9) \end{aligned}$$

令

$$\bar \Sigma =\text{diag}\{\sqrt{\lambda_1},...,\sqrt{\lambda_k}\} \in \mathbb R^{k\times k}$$

那么

$$\bar U^T A\bar V = \bar \Sigma$$

由基扩张定理，可以对

$$\vec x_1 ,...,\vec x_k \\ \vec y_1 ,...,\vec y_k$$

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

$$\begin{aligned} A^TA\vec x_i &=0 &i&=k+1,...,n\\ AA^T\vec y_j &=0 &j&=k+1,...,m \end{aligned}$$

将其扩张为

$$\vec x_1 ,...,\vec x_k, \vec x_{k+1},...,\vec x_{n} \\ \vec y_1 ,...,\vec y_k, \vec y_{k+1},...,\vec y_{m}$$

记

$$\begin{eqnarray*} V&&= \left( \begin{matrix} \vec x_1 & \ldots & \vec x_n \end{matrix} \right)\in \mathbb R^{n\times n} \tag {10}\\ U&&= \left( \begin{matrix} \vec y_1 & \ldots & \vec y_m \end{matrix} \right)\in \mathbb R^{m\times m}\tag {11} \end{eqnarray*}$$

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

$$U^T A V \vec e_i =\vec 0$$

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

$$\begin{aligned} \Sigma_{ij}=\begin{cases} \sqrt{\lambda_i } &i=j,i\le k\\ 0& 其他 \end{cases} \end{aligned}$$

那么

$$\begin{aligned} U^T AV&=\Sigma \\ A&=U\Sigma V^T \end{aligned}$$

上式分解被称为$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$，所以

$$AV=U\Sigma$$

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

$$AA^T\vec u_i=\vec 0$$

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