奇异值分解

发表于 分类于 阅读次数：

分步到达奇异值分解

前置证明

对称矩阵具有实特征值，有正交的特征向量（实谱定理）

实特征值的证明： 假设对于非零向量 \(x\)，\(Sx = \lambda x\)，则我们有 \(S \bar x = \bar \lambda \bar x\),即 \(\bar x ^\text T S = \bar \lambda \bar x^\text T\)。

对于第一个式子左乘 \(\bar x ^\text T\)，最后一个式子右乘 \(x\)，得到：

\[ \lambda \bar x^\text T x = \bar x ^\text T Sx = \bar \lambda \bar x^\text T x \]

由于 \(x\) 非 0，因此 \(\bar x ^\text T x = \Vert x\Vert^2 \ne 0\)。则 \(\lambda = \bar \lambda\)，即 \(\lambda\) 是实数。

正交特征向量的证明：

若两个特征向量 \(x_1,x_2\) 对应不同的特征值 \(\lambda_1, \lambda_2\)，则有 \(Sx_1 = \lambda_1 x_1\)，左乘 \(x_2 ^\text T\) 得到 \(x_2 ^\text T S x_1 = \lambda_1 x_2 ^\text T x_1\)。同样有 \(Sx_2 = \lambda_2 x_2\)，对它取转置，得到 \(x_2 ^\text TS = \lambda_2 x_2 ^\text T\)，右乘 \(x_1\)，得到 \(x_2 ^\text TSx_1 = \lambda_2 x_2 ^\text Tx_1\)。

此时，我们有：

\[ \lambda_1 x_2 ^\text Tx_1 = x_2 ^\text TSx_1 = \lambda_2 x_2 ^\text Tx_1 \]

由于 \(\lambda_1 \ne \lambda_2\)，得到 \(x_2 ^\text Tx_1 = 0\)，即 \(x_1, x_2\) 正交。

由于至少有一个特征值 \(\lambda\)，我们一定可以至少取出一个特征向量 \(u\)，则可以在此基础上构造一组规范正交基 \(u, u_2, \cdots u_n\)。构造 \(U = [u, u_2, \cdots u_n]\)，则 \(U\) 正交，且

\[ SU = [\lambda u, Su_2, \cdots, Su_n] = U\begin{bmatrix}\lambda & \beta^\text T \\ 0 & S_{n-1}\end{bmatrix} \]

用 \(U^\text T\) 右乘，得到：

\[ \begin{aligned} S &= U \begin{bmatrix}\lambda & \beta^\text T \\ 0 & S_{n-1}\end{bmatrix} U^\text T \\ S ^\text T &= U \begin{bmatrix}\lambda & 0 \\ \beta & S_{n-1}^\text T\end{bmatrix} U^\text T \end{aligned} \]

由于 \(S\) 对称，则 \(\beta = 0, S_{n-1} = S_{n-1}^\text T\)。

不难发现 \(n=1\) 时，存在规范正交的 \(U_1\) 使得 \(S_1 = U_1\operatorname{diag}(\lambda) U_1^\text T\)。

\(n > 1\) 时，存在规范正交的 \(U\) 使得：

\[ \begin{aligned} S_n &= U\begin{bmatrix}\lambda_1 & 0 \\ 0 & U_{n-1}\operatorname{diag}(\lambda_{n-1}) U_{n-1}^\text T\end{bmatrix} U^\text T\\ &= U\begin{bmatrix}1 & 0 \\ 0 & U_{n-1}\end{bmatrix}\operatorname{diag}(\lambda_n)\begin{bmatrix}1 & 0 \\ 0 & U_{n-1}^\text T\end{bmatrix}U^\text T \end{aligned} \]

令 \(U_n = U\begin{bmatrix}1 & 0 \\ 0 & U_{n-1}\end{bmatrix}\)，则存在规范正交的 \(U_n\) 使得 \(S = U_n\operatorname{diag}(\lambda_n)U_n^\text T\)。

使用归纳法即可完成证明。

半正定矩阵有非负特征值

半正定矩阵定义：若 \(\forall u \in \mathbb R^n,u \ne 0\)，\(u^\text TAu \ge 0\)，则 \(A\) 被称为半正定矩阵。

感性理解：\(Au\) 把 \(u\) 映射到新向量，\(u^\text T Au \ge 0\) 说明新向量和原向量的夹角不大于 90 度，即在相同的方向上，这就叫“半正”。如果严格小于 90 度，即 \(u^\text T Au > 0\) 则 \(A\) 被叫做“正定”。

非负特征值就显然了。对于特征向量 \(x\)，\(x^\text T Ax = \lambda x^\text T x = \lambda \Vert x\Vert^2 \ge 0\)，说明 \(\lambda \ge 0\)。

对于任意实矩阵 \(A \in \mathbb R^{m \times n}\)，\(A^\text T A\) 为对称半正定矩阵

首先是对称：\((A^\text T A)^\text T = A^\text T A\)。

接下来是半正定：对于任意非零向量 \(u\)，\(u^\text T A^\text T Au = (Au)^\text T (Au) \ge 0\)。则 \(A^\text TA\) 半正定。

特别地，若 \(A\) 满秩，则 \(Au \ne 0\)，此时 \(A^\text TA\) 正定。

\(AA^\text T\) 与 \(A^\text T A\) 有相同的非零特征值

设 \(A^\text T Ax = \lambda x, \lambda \ne 0\)，则 \(AA^\text T(Ax) = \lambda (Ax)\)。

因为 \(A^\text T(Ax) = \lambda x \ne 0\)，则 \((Ax) \ne 0\)。说明 \(AA^\text T\) 有特征值 \(\lambda\) 和特征向量 \(Ax\)。

构造 \(V_r\)

对于 \(A^\text T A\) 做特征值分解得到 \(V\Lambda_v V^\text T\)。

不妨令 \(\Lambda_v\) 对角线元素从大到小排序。假设 \(A\) 的秩为 \(r\)，构造 \(\Sigma_r \in R^{r \times r}\)，其中主对角线元素是 \(\Lambda_v\) 前 \(r\) 个主对角线元素的算术平方根（即非零元素）。

同样地，取 \(V_r \in \mathbb R^{n \times r}\)，则有 \(A^\text T A= V_r\Sigma_r^2V_r^\text T\)。也即 \(V_r^\text T A^\text T AV_r = \Sigma_r^2\)。

构造 \(U_r\)

接下来构造 \(U_r = AV_r\Sigma_r^{-1}\)。则：

\[ U^\text TU = \Sigma_r^{-1}V_r^\text T A^\text TAV_r\Sigma_r^{-1} = \Sigma_r^{-1}\Sigma_r^2\Sigma_r^{-1} = I \]

说明 \(U_r\) 是规范正交的。

\(A = U_r\Sigma_r V_r^\text T\)

证明：

\[ U_r\Sigma_r V_r^\text T = AV_r\Sigma_r^{-1}\Sigma_r V_r^\text T = A \]

此时，我们已经得到了 \(A\) 的一种按秩奇异值分解。接下来我们将说明 \(U_r\) 是 \(AA^\text T\) 的非零特征值对应的特征向量，进而给出完整的奇异值分解，同时说明：

  • \(U_r\) 是 \(A\) 列空间的一组基。
  • \(V_r\) 是 \(A\) 行空间的一组基。

构造完整的 \(U,\Sigma,V\)

由于 \(U_r, V_r\) 都是规范正交的，自然可以在他们的基础上各补全出唯一一组完整的规范正交基。\(V_r\) 的补全结果就是先前特征值分解得到的 \(V\)，我们先把 \(U_r\) 的补全结果记作 \(U\)，再将 \(\Sigma_r\) 通过补零的方法得到 \(\Sigma \in \mathbb R^{m\times n}\)。由于 \(\Sigma\) 多出来的行列都是 0,我们仍然有：\(A = U\Sigma V^\text T\)。

则我们有：

\[ AA^\text T = U\Sigma V^\text T V\Sigma ^\text T U^\text T = U\Sigma \Sigma^TU^\text T \]

记 \(\Lambda_u = \Sigma \Sigma^\text T\)。不难发现 \(\Lambda_u\) 的非零元素和 \(\Lambda_v\) 相同，都是 \(AA^\text T\) 以及 \(A\text T A\) 的特征值。因此我们得到：\(U\) 是 \(AA^\text T\) 特征值分解的结果。

综上，我们可以得到以下性质：

  • 任意实矩阵都可以分解为 \(U \Sigma V^\text T\) 的形式。其中，\(U\) 是 \(AA^\text T\) 的特征向量，\(V\) 是 \(A^\text TA\) 的特征向量。\(\Sigma\) 的非零值是 \(A^\text TA\) 特征值的算术平方根。
  • \(U,V\) 中有效的向量数是 \(A\) 的秩 \(r\)，可以将非零的特征值对应的向量取出构成 \(A = U_r\Sigma_r V_r^\text T\)。
  • \(U_r\) 是 \(A\) 的列空间的一组基，\(V_r\) 是 \(A\) 的列空间的一组基。
  • 将剩下的 0 特征值对应的向量取出构成 \(U_e, V_e\)，\(U_e\) 是 \(A\) 的左零空间的一组基（\(A^\text T U_e = 0\)），\(V_e\) 是 \(A\) 的零空间的一组基（\(AV_e = 0\)）。

复数？

上述证明可以直接扩展到复数：只需将所有的转置变成共轭转置，并注意到前置证明：

  • 自伴矩阵具有实特征值和酉特征向量（\(UU^*=I\)）。（复谱定理）
  • 半正定矩阵有非负特征值。
  • 对于任意复矩阵，\(AA^*\) 是半正定矩阵。
  • \(AA^*\) 与 \(A^* A\) 有相同的非零特征值。

就可以自然地把接下来的证明拓展到复数。所有性质仍然成立：

  • 任意复矩阵都可以分解为 \(U \Sigma V^*\) 的形式。其中，\(U\) 是 \(AA^*\) 的特征向量，\(V\) 是 \(A^*A\) 的特征向量。\(\Sigma\) 的非零值是 \(A^*A\) 特征值的算术平方根。
  • \(U,V\) 中有效的向量数是 \(A\) 的秩 \(r\)，可以将非零的特征值对应的向量取出构成 \(A = U_r\Sigma_r V_r^*\)。
  • \(U_r\) 是 \(A\) 的列空间的一组基，\(V_r\) 是 \(A\) 的列空间的一组基。
  • 将剩下的 0 特征值对应的向量取出构成 \(U_e, V_e\)，\(U_e\) 是 \(A\) 的左零空间的一组基（\(A^* U_e = 0\)），\(V_e\) 是 \(A\) 的零空间的一组基（\(AV_e = 0\)）。