線性代數/奇異值分解

奇異值分解

對於任何$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}}$.