线性代数/奇异值分解

奇异值分解

对于任何$m\times n$矩阵$A$，奇异值分解 (SVD) 是$A=U\Sigma V^{H}$，其中 $U$ 是一个 $m\times m$ 酉矩阵，$V$ 是一个 $n\times n$ 酉矩阵，$\Sigma$ 是一个 $m\times n$ 对角矩阵，所有非对角元素均为 0，对角元素均为非负实数。 $\Sigma$ 的对角元素被称为“奇异值”。

例如，考虑剪切变换 $A={\begin{pmatrix}1&2\\0&1\\\end{pmatrix}}$。 $A$ 的奇异值分解是

${\begin{pmatrix}1&2\\0&1\\\end{pmatrix}}={\begin{pmatrix}0.9239&-0.3827\\0.3827&0.9239\\\end{pmatrix}}{\begin{pmatrix}2.4142&0\\0&0.4142\\\end{pmatrix}}{\begin{pmatrix}0.3827&0.9239\\-0.9239&0.3827\\\end{pmatrix}}$

所有单位长度向量${\vec {v}}$，使得 $|{\vec {v}}|=1$ 形成一个半径为 1 的球体，围绕原点。当 $A$ 应用于该球体时，它将变成一个椭球体。该椭球体的半长轴就是奇异值，它们的方位形成 $U$ 的列向量。

奇异值分解的存在性

一个不那么显而易见的事实是奇异值分解总是存在的

定理（奇异值分解的存在性）

给定任意$m\times n$ 矩阵$A$，存在$m\times m$ 酉矩阵$U$，$n\times n$ 酉矩阵$V$ 和$m\times n$ 对角矩阵$\Sigma$，其中所有非对角线元素为 0，对角线元素均为非负实数，使得$A=U\Sigma V^{H}$.

本质上，任何线性变换都是一个旋转，然后是沿着每个轴的拉伸或收缩（某些维度被添加或归零），最后是另一个旋转。

下面的证明将证明奇异值分解总是存在的。首先将给出证明的提纲

证明提纲

我们需要证明任意线性变换$A$ 是一个旋转：$V^{H}$，然后是沿着每个轴的缩放：$\Sigma$，最后是另一个旋转：$U$，得到$A=U\Sigma V^{H}$.

如果$A$ 的列向量已经是相互正交的，那么第一个旋转就不需要：$V=I$。$\Sigma$ 的元素是 $A$ 的列向量形成的向量的长度，$U$ 是一个旋转，它将$\mathbb {C} ^{m}$ 的基本基向量旋转到与$A$ 的列向量平行。

In most cases however, the columns of $A$ are not mutually orthogonal. In this case, the rotation $V^{H}$ is non-trivial. $A=(AV)V^{H}$, so $V$ must be chosen so that the columns of $AV$ are mutually orthogonal. Let $V={\begin{pmatrix}{\vec {v}}_{1}&{\vec {v}}_{2}&\dots &{\vec {v}}_{n}\end{pmatrix}}$. We need to choose orthonormal vectors ${\vec {v}}_{1},{\vec {v}}_{2},\dots ,{\vec {v}}_{n}$ so that $A{\vec {v}}_{1},A{\vec {v}}_{2},\dots ,A{\vec {v}}_{n}$ are all mutually orthogonal. This can be done iteratively. Imagine that we have chosen ${\vec {v}}_{1}$ so that when given any vector ${\vec {v}}$ that is orthogonal to ${\vec {v}}_{1}$, that $A{\vec {v}}_{1}$ is orthogonal to $A{\vec {v}}$. The effort now switches to finding an orthonormal set of vectors ${\vec {v}}_{2},{\vec {v}}_{3},\dots ,{\vec {v}}_{n}$ confined to the space of vectors that are perpendicular to ${\vec {v}}_{1}$ such that $A{\vec {v}}_{2},A{\vec {v}}_{3},\dots ,A{\vec {v}}_{n}$ are mutually orthogonal.

令 $V_{1}$ 为一个酉矩阵，其第一列为 ${\vec {v}}_{1}$。从 $V$ 左侧提取 $V_{1}$ 得 $V=V_{1}V_{\text{new}}$，这将产生一组新的正交向量，这些向量是 $V_{\text{new}}$ 的列向量。我们的目标是使 $AV$ 的列向量相互正交，这转化为使 $(AV_{1})V_{\text{new}}$ 的列向量相互正交，其中 $AV_{1}$ 有效地替代了 $A$。 ${\vec {v}}_{1}$ 变换为 ${\vec {e}}_{1}$，并且与 ${\vec {v}}_{1}$ 正交的向量空间变换为由标准基向量 ${\vec {e}}_{2},{\vec {e}}_{3},\dots ,{\vec {e}}_{n}$ 张成的空间。 $AV_{1}$ 的第一列是 $A{\vec {v}}_{1}$，因此它与所有其他列向量正交。

如果 $U_{1}$ 是一个酉矩阵，其中 $U_{1}$ 的第一列是 $A{\vec {v}}_{1}$ 归一化为单位长度，那么从 $AV_{1}$ 的左侧提取 $U_{1}$ 得到 $A_{1}=U_{1}^{H}AV_{1}$ 会得到一个矩阵，其第一列与标准基向量 ${\vec {e}}_{1}$ 平行。 $AV_{1}$ 的第一列与所有其他列正交，因此 $A_{1}$ 的第一列与所有其他列正交，因此 $A_{1}$ 的第一行除了第一列之外，其余都包含 0。

${\vec {v}}_{2},{\vec {v}}_{3},\dots ,{\vec {v}}_{n}$ 现在可以通过递归地确定，维度降低到 $n-1$，$A$ 被替换为 $A_{1}$，并删除第一行和第一列。 这形成了即将到来的证明的归纳部分。

最后，我们如何知道存在${\vec {v}}_{1}$，使得当给定任何与 ${\vec {v}}_{1}$ 正交的向量 ${\vec {v}}$ 时，$A{\vec {v}}_{1}$ 与 $A{\vec {v}}$ 正交？答案是使得 $|A{\vec {v}}|$ 最大化的单位长度 ${\vec {v}}$ 是一个有效的 ${\vec {v}}_{1}$。

现在我们准备给出完整的证明细节

奇异值分解存在性的证明

本证明将使用关于 $m$ 和 $n$ 的归纳法进行。

基本情况 $m=1$

$A$ 只有一个行，因此具有形式 $A={\begin{pmatrix}\sigma _{1}{\vec {v}}_{1}^{H}\end{pmatrix}}$，其中 ${\vec {v}}_{1}$ 是一个任意的单位长度向量，而 $\sigma _{1}$ 是一个任意的非负实数。注意，对于任何单行矩阵 $A$，${\vec {v}}_{1}$ 和 $\sigma _{1}$ 都是存在的。

令 $U={\begin{pmatrix}1\end{pmatrix}}$，$\Sigma ={\begin{pmatrix}\sigma _{1}&0&\dots &0\\\end{pmatrix}}$，和 $V={\begin{pmatrix}{\vec {v}}_{1}&{\vec {v}}_{2}&\dots &{\vec {v}}_{n}\end{pmatrix}}$，其中${\vec {v}}_{1},{\vec {v}}_{2},\dots ,{\vec {v}}_{n}$ 共同构成一个长度为 1 的互相正交的向量集。 ${\vec {v}}_{2},{\vec {v}}_{3},\dots ,{\vec {v}}_{n}$ 可以通过 Gram-Schmidt 正交化方法确定。很明显：$A=U\Sigma V^{H}$.

基本情况 $n=1$

$A$ 只有一个列，因此具有形式 $A={\begin{pmatrix}\sigma _{1}{\vec {u}}_{1}\end{pmatrix}}$，其中 ${\vec {u}}_{1}$ 是一个任意的长度为 1 的向量，而 $\sigma _{1}$ 是一个任意的非负实数。请注意，对于任何单列矩阵 $A$，${\vec {u}}_{1}$ 和 $\sigma _{1}$ 都存在。

令 $U={\begin{pmatrix}{\vec {u}}_{1}&{\vec {u}}_{2}&\dots &{\vec {u}}_{m}\end{pmatrix}}$，$\Sigma ={\begin{pmatrix}\sigma _{1}\\0\\\vdots \\0\\\end{pmatrix}}$，以及 $V={\begin{pmatrix}1\end{pmatrix}}$，其中 ${\vec {u}}_{1},{\vec {u}}_{2},\dots ,{\vec {u}}_{m}$ 共同构成一组相互正交的单位长度向量。 ${\vec {u}}_{2},{\vec {u}}_{3},\dots ,{\vec {u}}_{m}$ 可以通过格拉姆-施密特正交化来确定。 很明显： $A=U\Sigma V^{H}$。

归纳情况 $m,n\geq 2$

令 ${\vec {e}}_{k,i}$ 表示 $\mathbb {C} ^{k}$ 的第 $i^{\text{th}}$ 个标准基向量。 令 $\mathbf {0} _{k\times l}$ 表示一个 $k\times l$ 的零矩阵。

在约束条件 $|{\vec {v}}|=1$ 下，最大化 $|A{\vec {v}}|$。令 ${\vec {v}}_{1}$ 为最大化 $|A{\vec {v}}|$ 的单位长度向量，并令 $\sigma _{1}=|A{\vec {v}}_{1}|$。令 ${\vec {u}}_{1}={\frac {A{\vec {v}}_{1}}{\sigma _{1}}}$（如果 $\sigma _{1}=0$，那么 ${\vec {u}}_{1}$ 是一个任意的单位长度向量）。

使用格拉姆-施密特正交化，可以确定酉矩阵 $U_{1}$ 和 $V_{1}$，使得 $U_{1}$ 和 $V_{1}$ 的第一列分别为 ${\vec {u}}_{1}$ 和 ${\vec {v}}_{1}$：$U_{1}{\vec {e}}_{m,1}={\vec {u}}_{1}$ 和 $V_{1}{\vec {e}}_{n,1}={\vec {v}}_{1}$。 $A=U_{1}A_{1}V_{1}^{H}$ 其中 $A_{1}=U_{1}^{H}AV_{1}$。现在将证明 $A_{1}$ 的第一列和第一行除了 (1,1) 位置的元素为 $\sigma _{1}$ 外，其余元素均为 0：$A_{1}={\begin{pmatrix}\sigma _{1}&\mathbf {0} _{1\times (n-1)}\\\mathbf {0} _{(m-1)\times 1}&A_{\text{reduced}}\end{pmatrix}}$.

$A{\vec {v}}_{1}=\sigma _{1}{\vec {u}}_{1}\implies U_{1}A_{1}V_{1}^{H}{\vec {v}}_{1}=\sigma _{1}{\vec {u}}_{1}\implies A_{1}{\vec {e}}_{n,1}=\sigma _{1}{\vec {e}}_{m,1}$。这意味着 $A_{1}$ 的第一列是 $\sigma _{1}{\vec {e}}_{m,1}={\begin{pmatrix}\sigma _{1}\\\mathbf {0} _{(m-1)\times 1}\end{pmatrix}}$。

为了说明 $A_{1}$ 的第一行是 $\sigma _{1}{\vec {e}}_{n,1}^{H}={\begin{pmatrix}\sigma _{1}&\mathbf {0} _{1\times (n-1)}\end{pmatrix}}$，我们将证明 $A_{1}$ 的第一列与 $A_{1}$ 的所有其他列正交。这将需要利用以下事实：在约束条件 $|{\vec {v}}|=1$ 下，${\vec {v}}={\vec {e}}_{n,1}$ 使 $|A_{1}{\vec {v}}|$ 最大化。

令 $v(t)$ 是一个参数化的单位长度向量。令 $v(0)={\vec {e}}_{n,1}$。

对约束条件 $v^{H}v=1$ 求导得到 ${\frac {dv^{H}}{dt}}v+v^{H}{\frac {dv}{dt}}=0$

$|A_{1}{\vec {v}}|$ 在 ${\vec {e}}_{n,1}$ 处取得最大值，得到

${\frac {d}{dt}}(|A_{1}{\vec {v}}|^{2}){\bigg |}_{t=0}=0\iff {\frac {d}{dt}}({\vec {v}}^{H}A_{1}^{H}A_{1}{\vec {v}}){\bigg |}_{t=0}=0\iff {\frac {d{\vec {v}}^{H}}{dt}}{\bigg |}_{t=0}A_{1}^{H}A_{1}{\vec {e}}_{n,1}+{\vec {e}}_{n,1}^{H}A_{1}^{H}A_{1}{\frac {d{\vec {v}}}{dt}}{\bigg |}_{t=0}=0$

$\iff \Re \left({\vec {e}}_{n,1}^{H}A_{1}^{H}A_{1}{\frac {d{\vec {v}}}{dt}}{\bigg |}_{t=0}\right)=0$

($\Re$ 和 $\Im$ 分别表示复数的实部和虚部。)

令 $i=2,3,\dots ,n$ 为任意值。令 ${\frac {d{\vec {v}}}{dt}}{\bigg |}_{t=0}={\vec {e}}_{n,i}$。 ${\vec {e}}_{n,1}$ 和 ${\vec {e}}_{n,i}$ 是正交的。

这给出了：$\Re ({\vec {e}}_{n,1}^{H}A_{1}^{H}A_{1}{\vec {e}}_{n,i})=0$。

现在令 ${\frac {d{\vec {v}}}{dt}}{\bigg |}_{t=0}=i{\vec {e}}_{n,i}$，其中下标外的 $i$ 是虚数单位。 ${\vec {e}}_{n,1}$ 和 $i{\vec {e}}_{n,i}$ 是正交的。

这给出了：$\Re ({\vec {e}}_{n,1}^{H}A_{1}^{H}A_{1}(i{\vec {e}}_{n,i}))=0\implies \Im ({\vec {e}}_{n,1}^{H}A_{1}^{H}A_{1}{\vec {e}}_{n,i})=0$。

因此：$(A_{1}{\vec {e}}_{n,1})^{H}(A_{1}{\vec {e}}_{n,i})={\vec {e}}_{n,1}^{H}A_{1}^{H}A_{1}{\vec {e}}_{n,i}=0$。

因此， $A_{1}$ 的第一列与 $A_{1}$ 的所有其他列正交，并且 $A_{1}$ 具有以下形式：$A_{1}={\begin{pmatrix}\sigma _{1}&\mathbf {0} _{1\times (n-1)}\\\mathbf {0} _{(m-1)\times 1}&A_{\text{reduced}}\end{pmatrix}}$。

$A_{\text{reduced}}$ 是一个 $(m-1)\times (n-1)$ 矩阵，因此，通过归纳推理，$A_{\text{reduced}}=U_{r}\Sigma _{r}V_{r}^{H}$。最后，

$A=U\Sigma V^{H}$ 其中 $U=U_{1}{\begin{pmatrix}1&\mathbf {0} _{1\times (m-1)}\\\mathbf {0} _{(m-1)\times 1}&U_{r}\end{pmatrix}}$，$\Sigma ={\begin{pmatrix}\sigma _{1}&\mathbf {0} _{1\times (n-1)}\\\mathbf {0} _{(m-1)\times 1}&\Sigma _{r}\end{pmatrix}}$，和 $V=V_{1}{\begin{pmatrix}1&\mathbf {0} _{1\times (n-1)}\\\mathbf {0} _{(n-1)\times 1}&V_{r}\end{pmatrix}}$.