新生任务-4

一、奇异值的 \(QR\) 分解算法

和之前利用 \(AA^{\mathrm{T}}\) 的特征值求奇异值不同的是, 这个方法看起来不太能够理解, 在书上的描述也比较简单.

其实就是简单的两步, 第一步通过 \(\mathrm{Household}\) 变换使得矩阵 \(A\) 变成二重对角矩阵. 所谓二重对角矩阵就是除了主对角线以及主对角线上面一条对角线外的其余元素全为 0.

第二步就是反复利用正交变换使得除主对角线外的那些元素逐渐减小靠近 0.

虽然看起来很简单, 但是没有公式和实际例子, 自己也只能慢慢来摸索方法.

二、构造二重对角矩阵并利用 \(QR\) 分解

现有这样一个矩阵 \(A\)

\[ A = \begin{bmatrix} 1 & 2 & 2\\ 2 & 1 & 2\\ 2 & 2 & 1 \end{bmatrix} \]

对第一列进行 \(\mathrm{Householder}\) 变换, 先把第一列提出来

\[ a_1 = \begin{bmatrix} 1\\ 2\\ 2 \end{bmatrix} \]

求 \(a_1\) 的二范数

\[ \alpha_2 = \lVert a_1 \rVert_2 = \sqrt{1^2+2^2+2^2} = \sqrt{1+4+4} = 3 \]

然后有

\[ a_1 - \alpha_2e_2 = \begin{bmatrix} 1\\ 2\\ 2 \end{bmatrix} - 3\begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix} = \begin{bmatrix} -2\\ 2\\ 2 \end{bmatrix} \]

其中 \(e_2\) 是单位向量 \(\begin{bmatrix}1\\0\\0\end{bmatrix}\).

\[ \lVert a_1 - \alpha_2e_2\rVert_2 = \sqrt{(-2)^2+2^2+2^2} = \sqrt{4+4+4} = \sqrt{12} \]

那么就有

\[ u_1 = \frac{a_1 - \alpha_2e_2}{\lVert a_1 - \alpha_2e_2\rVert_2}=\frac{1}{\sqrt{12}} \begin{bmatrix} -2\\ 2\\ 2 \end{bmatrix} \]

根据 \(H_1 = I - 2u_1u_1^{\mathrm{T}}\) 可得

\[ \begin{aligned}H_1 &= \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} - 2 \times \frac{1}{12} \begin{bmatrix} -2\\ 2\\ 2 \end{bmatrix} \begin{bmatrix} -2 & 2 & 2 \end{bmatrix} \\ &= \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix} - \frac{1}{6} \begin{bmatrix} 4 & -4 & -4\\ -4 & 4 & 4\\ -4 & 4 & 4 \end{bmatrix} \\ &= \begin{bmatrix} 1/3 & 2/3 & 2/3\\ 2/3 & 1/3 & -2/3\\ 2/3 & -2/3 & 1/3 \end{bmatrix} \end{aligned} \]

神奇的事情来了, 这里有 \(HA\)

\[ \begin{aligned}H_1A &= \begin{bmatrix} 1/3 & 2/3 & 2/3\\ 2/3 & 1/3 & -2/3\\ 2/3 & -2/3 & 1/3 \end{bmatrix} \begin{bmatrix} 1 & 2 & 2\\ 2 & 1 & 2\\ 2 & 2 & 1 \end{bmatrix} \\ &=\begin{bmatrix} 3 & 8/3 & 8/3\\ 0 & 1/3 & 8/3\\ 0 & 4/3 & 1/3 \end{bmatrix} \end{aligned} \]

然后这里对于一个 \(3 \times 3\) 的矩阵只是将第一列除 \((1,1)\) 位置的元素归 0, 但是并没有完成对第一行除 \((1,1)\) 和 \((1,2)\) 位置的元素归 0. 书上也没有提到这么做的方法, 只是轻描淡写一句还是通过 \(\mathrm{Householder}\) 变换.

无奈这个算法实在搞不懂, 暂且搁置. 未完待续......

三、奇异值分解的右边 \(\mathrm{Jacobi}算法\)

现有矩阵 \(A=\begin{bmatrix} 1& 2\\ 2& 1\end{bmatrix}\), 求其 SVD 分解.

第一步先计算矩阵 \(A^{\mathrm{T}}A\) 的 \((i,j)\) 子矩阵 \(\begin{bmatrix} a& c\\ c& b\end{bmatrix}\), 因为要求 \(i < j\), 那么对于矩阵 \(A^{\mathrm{T}}A\) 就只需要计算 \((1,2)\) 子矩阵

\[ A^{\mathrm{T}}A=\begin{bmatrix} 5 & 4 \\ 4 & 5 \end{bmatrix} \]

\[ a = \sum_{k-1}^{n}A_{ki}^2 = A_{11}^2 + A_{21}^2 = 5^2 + 4^2 = 25 + 16 = 41 \]

\[ b = \sum_{k-1}^{n}A_{kj}^2 = A_{12}^2 + A_{22}^2 = 4^2 + 5^2 = 16 + 25 = 41 \]

\[ c = \sum_{k-1}^{n}A_{ki}*A_{kj} = (A_{11} \times A_{12}) + (A_{21} \times A_{22}) = (5 \times 4) + (4 \times 5) = 20 + 20 = 40 \]

可以得到子矩阵 \(\begin{bmatrix} 80& 60\\ 60& 45\end{bmatrix}\), 计算使其对角化的右边 \(\mathrm{Jacobi}\) 旋转矩阵 \(\begin{bmatrix} cs& -sn\\ sn& cs\end{bmatrix}\)

\[ \xi = (b - a)/(2c) = (45 - 80)/(2 \times 60) = (-35)/(120) = -\frac{7}{24} \]

\[ t = \mathrm{sgn}(\xi)/(|\xi|+ \sqrt{1 + \xi^2}) = \mathrm{sgn}(-\frac{7}{24})/(|-\frac{7}{24}| + \sqrt{1 + (-\frac{7}{24})^2}) = -\frac{3}{4} \]

所以就有

\[ cs = 1/\sqrt{1+t^2} = \frac{1}{\sqrt{1 + \frac{9}{16}}}= \frac{4}{5} \]

\[ sn = cs \times t = \frac{4}{5} \times -\frac{3}{4} = -\frac{3}{5} \]

更新矩阵 \(A\)

\[ A = \begin{bmatrix} 1& 2\\ 2& 1 \end{bmatrix} \longrightarrow \begin{bmatrix} 2& 1\\ 11/5& -2/5 \end{bmatrix} \]

更新右奇异向量的矩阵 \(V\)

\[ V = \begin{bmatrix} 1& 0\\ 0& 1 \end{bmatrix} \longrightarrow \begin{bmatrix} 4/5& -3/5\\ 3/5& 4/5 \end{bmatrix} \]

感觉过程中出现了错误, 和实际奇异值分解有误差. 或许是迭代次数不够, 然而在网上搜索之后说的是可能是印刷问题, 那么这部分内容就还是交到明天去做.