奇异值分解 Why What How

💡

本文所述矩阵均为实矩阵；本文所述中，行空间（row space）为矩阵横着的向量（水平方向）组成的线性空间。（在台湾地区竖着的为行，横着的为列）

本文所需预备知识：

掌握矩阵特征值分解；
理解矩阵就是线性变换；
理解矩阵的四个子空间；
了解正交矩阵及施密特正交化

矩阵本质上是一种线性变换，包括了旋转、拉伸等线性操作。一个 $m \times n$ 的矩阵 $A$ 可以被视为一个从 $n$ 维向量空间 $\mathbb {R}^n$ 到 $m$ 维向量空间 $\mathbb {R}^m$ 的线性变换，即 $A\in \mathbb{R}^{m*n}: \mathbb {R}^n --> \mathbb {R}^m$ 。这个变换将 $\mathbb {R}^n$ 中的向量 $\mathbf {x}$ 映射到 $\mathbb {R}^m$ 中的一个向量 $\mathbf {y}$ ，该过程可以用矩阵乘法来表示：

\mathbf {y} = A\mathbf {x}

而不管是特征值分解还是奇异值分解，都是把这个变换拆解开。也就是把一个复杂的变换动作拆解开。例如，对称半正定矩阵的特征值分解是把矩阵的变换动作拆解为旋转、伸缩、旋转三个变换。

例如，矩阵

A=\begin{bmatrix}2&-1\\-1&2\end{bmatrix} =\underbrace{\begin{bmatrix} -\frac{\sqrt{2}}{2}&\frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}&\frac{\sqrt{2}}{2} \end{bmatrix}}_{U\text{：旋转}} \underbrace{\begin{bmatrix}3&0\\0&1\end{bmatrix}}_{\Sigma\text{：拉伸}} \underbrace{\begin{bmatrix} -\frac{\sqrt{2}}{2}&\frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2}&\frac{\sqrt{2}}{2} \end{bmatrix}}_{V^T\text{：旋转}}.

这个例子中， $U$ 和 $V^T$ 都是正交矩阵，只负责旋转； $\Sigma$ 是对角矩阵，只负责沿正交方向进行拉伸或收缩。

Note

注：对角矩阵只有拉伸收缩的效果。（伸缩也包含了将某一个维度缩为0）；单位正交矩阵只有旋转的效果。因此，奇异值分解的本质就是把一个线性变换分解成三个矩阵，分别只有旋转、拉伸、旋转的作用。

然而特征值分解并非对所有矩阵均适用，它要求矩阵是方阵，且矩阵必须是可对角化的。而奇异值分解(SVD)是一种更通用、更强大的矩阵分解方法，可将任意矩阵所表示的线性变换分解为旋转拉伸旋转。（事实上，实对称正定矩阵的特征值分解是奇异值分解的特例）

奇异值分解的本质是找到两组正交基，使得变换可以由一个具有最简形式（即对角形）的矩阵表示。

具体来说，对于一个 $m×n$ 矩阵 $A$ ，矩阵的秩 $r$ 为，SVD 将其分解为三个矩阵的乘积：

A = U\Sigma V^T

其中， $U$ 是一个 $m×m$ 的正交矩阵，即列向量 $u_i$ 相互正交，有 $U^T=U^{-1}$ ； $V$ 是一个 $n×n$ 的正交矩阵，即列向量 $v_i$ 相互正交，有 $V^T=V^{-1}$ ； $\Sigma$ 是一个 $m×n$ 的类对角矩阵，如下：

\Sigma=\begin{bmatrix}\sigma_1&0&0&0&\cdots&0\\0&\ddots&0&\vdots&\cdots&0\\0&0&\sigma_r&0&\cdots&0\\0&\cdots&0&0&\cdots&0\\\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\0&\cdots&0&0&\cdots&0\end{bmatrix}

其对角线上的元素 $\sigma_i >0,i=1,2,...,r; \sigma_{j}=0,j=r+1,...,\min(n,m)$ 是 $A$ 的奇异值。

📢

SVD 的分解不具有唯一性。为了便利应用，通常习惯将奇异值由大至小排序，即 $\sigma_1 ≥ \sigma_2≥…≥\sigma_r$

下图可帮助更好的理解奇异值分解。尤其是 $\Sigma$ 矩阵中大多元素均为0。

$U$ 和 $V$ 的列分别构成了矩阵行空间和列空间的正交基。 $\Sigma$ 的对角线上的非零元素表示对应基向量在变换过程中的伸缩因子。

具体如何求解呢？想要同时找两组正交基满足条件当然不好找，可以先把矩阵 $U$ 消掉，即构造 $A^TA$ 矩阵：

A^TA = V\Sigma^TU^T U\Sigma V^T = V\Sigma^T\Sigma V^T

求解 $A^TA$ 的特征分解，经特征分解，可得特征值 $\lambda_i,…,\lambda_r$ 和特征向量 $\alpha_i, …,\alpha_r$ （由于矩阵A的秩为r, 因此仅有r个特征向量）。

由于矩阵 $A^TA$ 为对称半正定矩阵，因此其特征向量 $\alpha_i$ 必定正交，且特征值必为非负数。

此时，对特征值按照递减进行排序，使其满足：

\begin{aligned} &\lambda_1 \ge \lambda_2 \dots \ge \lambda_r \ge 0\\ & \lambda_s = 0,s=r+1, r+2,...,n\\ \end{aligned}

且对特征值排序后对应的特征向量 $\alpha_i$ 进行标准化，得到一组正交向量 $v_i$

v_i = \frac{\alpha_i}{||\alpha||}

接着，利用 $A^TA$ 的特征向量来构造矩阵 $V$ 。已经有了 $r$ 个正交的特征向量组成了矩阵 $A$ 的行空间，还差零空间中的n-r个的基，该 $n-r$ 个正交基向量可利用施密特正交化来构造，最终可得 $n$ 个正交基 $v_1,v_2,…,v_n$ 。（事实上，这零空间的 $n-r$ 个正交基可以不用求解，因为根本用不到！）因此有矩阵 $V$ ：

V = \begin{bmatrix} \mid & \mid& \mid& \mid \\ v_1& v_2& \cdots& v_n \\ \mid& \mid& \mid& \mid \end{bmatrix}_{n*n}

接下来需要寻找一组正交向量 $u_i$ 来构造矩阵 $U$ 了，此时注意到：

(Av_i)^T (Av_j) = v_i^TA^TAv_j= v_i^T\lambda_iv_j

由于 $v_i，v_j$ 分别为对称半正定矩阵 $A^TA$ 的特征向量的标准化向量，有 $v_i^Tv_j = 0$ , 所以 $(Av_i)^T (Av_j) = 0$

因此， $Av_i$ 和 $Av_i$ 其实就是正交的，也就是想要寻找的正交向量 $u_i$ ，然后，对向量 $Av_i$ 进行标准化，求解 $Av_i$ 的模长平方，有：

||Av_i||^2 = (Av_i)^T (Av_i) = v_i^TA^TAv_i= v_i^T\lambda_iv_i = \lambda_i =\sigma_i^2

对 $Av_i$ 进行标准化，得到 $u_i$ ，有：

u_i = \frac{Av_i}{||Av_i||} = \frac{Av_i}{\sigma_i}\in \mathbf R^m,i=1,2,...,r

列空间为 $m$ 维空间，上述r个u向量仅仅填充了 $r$ 维度，因此还需要剩下的 $m-r$ 个正交基向量，同样采用施密特正交化得到（事实上，这m-r个左零空间的正交基也可以不用求解，因为用不到！）。此时可有 $U$ 矩阵：

U = \begin{bmatrix}  \mid &  \mid&  \mid&  \mid \\  u_1&  u_2&  \cdots&  u_m  \\   \mid&  \mid&  \mid&  \mid\end{bmatrix}_{m*m}

📢

由 $||Av_i||^2 =\sigma_i^2$ 可见，奇异值便是投影过去的向量 $Av_i$ 的长度，而 $Av_i$ 经过标准化后，奇异值表示变换在对应的奇异向量方向上的缩放因子，即 $Av_i = \sigma u_i$

最后，利用求得的两组基向量 $v_i$ 和 $u_i$ 和奇异值 $\sigma_i$ 来形式化描述奇异值分解。如下：

V = \begin{bmatrix} \mid & \mid& \mid& \mid \\ v_1& v_2& \cdots& v_n \\ \mid& \mid& \mid& \mid \end{bmatrix}_{n*n} \\U = \begin{bmatrix} \mid & \mid& \mid& \mid \\ u_1& u_2& \cdots& u_m \\ \mid& \mid& \mid& \mid \end{bmatrix}_{m*m}

\begin{align*} AV & = A \begin{bmatrix} \mid & \mid& \mid& \mid \\ v_1& v_2& \cdots& v_n \\ \mid& \mid& \mid& \mid \end{bmatrix} & \\&= \begin{bmatrix} \mid & \mid& \mid& \mid \\ Av_1& Av_2& \cdots& Av_n \\ \mid& \mid& \mid& \mid \end{bmatrix} & \\&= \begin{bmatrix} \mid & \mid& \mid& \mid &{\color{Red} \mid} &{\color{Red} \mid} & {\color{Red} \mid} \\ Av_1& Av_2& \cdots& Av_r & {\color{Red} 0} & {\color{Red} \cdots} & {\color{Red} 0} \\ \mid& \mid& \mid& \mid &{\color{Red} \mid} &{\color{Red} \mid} &{\color{Red} \mid} \end{bmatrix} \\&= \begin{bmatrix} \mid & \mid& \mid& \mid &{\color{Red} \mid} &{\color{Red} \mid} & {\color{Red} \mid} \\ \sigma_1 u_1& \sigma_2 u_2& \cdots& \sigma_r u_r & {\color{Red} 0} & {\color{Red} \cdots} & {\color{Red} 0} \\ \mid& \mid& \mid& \mid &{\color{Red} \mid} &{\color{Red} \mid} &{\color{Red} \mid} \end{bmatrix}\\ &=\begin{bmatrix} \mid & \mid& \mid& \mid \\ u_1& u_2& \cdots& u_m \\ \mid& \mid& \mid& \mid \end{bmatrix} @ \begin{bmatrix}\def \arraystretch{1.5} \begin{array}{c c c:c} \sigma_1& & & \\ &\ddots & & \Large 0 \\& & \sigma_r & \\ \hdashline & \Large 0 & & \Large{0} \end{array}\end{bmatrix}\\ & = U\Sigma \end{align*}

\begin{bmatrix}\def \arraystretch{1.5} \begin{array}{c c c:c} \sigma_1& & & \\ &\ddots & & \Large 0 \\& & \sigma_r & \\ \hdashline & \Large 0 & & \Large{0} \end{array}\end{bmatrix}

至此，已经完成了矩阵的奇异值分解。

稍微总结一下，SVD 的计算主要是利用下面几个性质：

$A^TA$ 和 $AA^T$ 的非零特征值为 $\lambda_i=\sigma_i^2,i=1,2,\ldots,r,r= \text{rank}{A}$ 。

📢

注， $A^TA$ 和 $AA^T$ 是半正定(positive semi definite)矩阵，其特征值必定非负，且特征向量必然正交。

$A^{T}A$ 的单位特征向量为 $\mathbf{v}_j$

A^TA\mathbf{v}_j=\sigma_j^2\mathbf{v}_j,\quad j=1,2,\ldots,n

$AA^T$ 的单位特征向量为 $\mathbf{u}_j$ ,

AA^T\mathbf{u}_j=\sigma_j^2\mathbf{u}_j,\quad j=1,2,\ldots,m

对于 $j=1,2,\ldots,r,\mathbf{u}_j$ 和 $\mathbf{v}_j$ 具有以下关系：

A\mathbf{v}_j=\sigma_j\mathbf{u}_j\\ A^T\mathbf{u}_j=\sigma_j\mathbf{v}_j

对应奇异值 $\sigma_i$ ， $\mathbf{u}_i$ 称为左奇异向量， $\mathbf{v}_i$ 称为右奇异向量。

矩阵 $A^TA$ $A^{T} A$ 为对称半正定矩阵。证明对称性， $(A^A)^T = A^TA$ $(A^{A})^{T} = A^{T} A$ 证明半正定：对任意非零向量x, 向量Ax的二范数 $||Ax||^2 = (Ax)^TAx= x^TA^Ax$ $∣∣ A x ∣ ∣^{2} = (A x)^{T} A x = x^{T} A^{A} x$ ，因为模长 $||Ax||^2 ≥ 0$ $∣∣ A x ∣ ∣^{2} \geq 0$ , 因此二次型矩阵 $A^TA$ $A^{T} A$ 为半正定矩阵。
- 对称：决定了特征向量为正交的
- 正定：决定了特征值为非负数
矩阵AB的特征值和矩阵BA的特征值是相同的。直觉上理解：矩阵AB和BA表达的是同一种变换，无非是顺序先后的问题。
对称矩阵的特征向量互相正交

宏观理解

对于任意一个 $m*n$ 矩阵 $A$ ，都有四个子空间：行空间、零空间、列空间、左零空间。假设该矩阵的秩 $\text{rank} A = r$ 。则矩阵的四个空间可由下图所示。

📢

注：这张图左右各有两个子空间，这两个子空间是天生正交的，从其中垂直的黑线也可以发现。因此绘制的时候，先画两个垂直线。

其中：

行空间和零空间天然正交，这是由定义所然。
列空间和左零空间也天然正交，这也是定义所然。
行空间的维度和列空间的维度均为 $r$ ，等于矩阵的秩
行空间和零空间共同张成了 $m$ 维空间。
列空间和左零空间共同张成了 $n$ 维空间。
零空间的向量在经过矩阵变换后，塌缩到了m维空间的原点，即 Ax=0, 也因此零空间称为核空间。如果不是方阵或者矩阵不满秩，则零空间维度不是零，此时，线性变换将不再是可逆的，因为塌缩到m维空间的原点的向量回不去了，这种矩阵不可逆。

在经过奇异值分解之后，分别找到了一组行空间的正交基和列空间的一组正交基，且满足 $Av_i = \sigma u_i, i=1, 2, 3,…,r$ 。因此可有如下图所示（下图中红色的向量即为两组正交基）。

通过 SVD，可以清晰地看到矩阵 $A$ 在不同方向上的 “拉伸” 效果，以及它如何将 $\mathbb {R}^n$ 中的向量映射到 $\mathbb {R}^m$ 中。

这样做有什么好处呢？矩阵本身就是线性变换，因此检查一下做奇异值分解前后线性变换的区别，在奇异值分解之前， $n$ 维的向量 $x$ 经过线性变换 $A$ 之后，转到了 $m$ 维空间，如下图所示：

线性变换 $A$ 经过奇异值分解之后，有 $A = U\Sigma V^T$ ，此时，再对 $n$ 维的向量 $x$ 做线性变换就变成了三步走了：

$V^Tx$ ：旋转，变换到 $V^T$ 的坐标系下。
$\Sigma V^Tx$ ：拉伸or收缩某些方向，也有一些方向丢失（变为0）
$U\Sigma V^Tx$ ：旋转，变换到 $U$ 所表示的坐标系下。

即如下图所示：

这样做有什么作用呢？将奇异值分解的结果用秩1矩阵求和形式表示为：

\begin{aligned}A&=\begin{bmatrix}\mathbf{u}_1&\mathbf{u}_2&\cdots&\mathbf{u}_m\end{bmatrix}\begin{bmatrix}\sigma_1\\&\sigma_2\\&&\ddots\\&&&\sigma_r\\&&&&\ddots\end{bmatrix}\begin{bmatrix}\mathbf{v}_1^T\\\mathbf{v}_2^T\\\vdots\\\mathbf{v}_n^T\end{bmatrix}\\&=\begin{bmatrix}\sigma_1\mathbf{u}_1&\sigma_2\mathbf{u}_2&\cdots&\sigma_r\mathbf{u}_r&\mathbf{0}&\cdots&\mathbf{0}\end{bmatrix}\begin{bmatrix}\mathbf{v}_1^T\\\mathbf{v}_2^T\\\vdots\\\mathbf{v}_n^T\end{bmatrix}\\&=\sigma_1\mathbf{u}_1\mathbf{v}_1^T+\sigma_2\mathbf{u}_2\mathbf{v}_2^T+\cdots+\sigma_r\mathbf{u}_r\mathbf{v}_r^T\\&=\sum_{i=1}^{r}\sigma_i u_{i} {v_{i}}^T\end{aligned}

上式指出 $A$ 仅由 $U$ 的前 $r$ 个行向量(以 $U_r$ 表示), $V^T$ 的前 $r$ 列矢量(以 $V_r^T$ 表示), 以及 $\Sigma$ 的左上 $r\times r$ 分块决定(以 $\Sigma_r$ 表示)，称为「瘦」奇异值分解，如下图所示。

这个结果看似不起眼，其实它有重大的意义。矩阵 $A$ 总共有 $m\times n$ 个元， $U_r$ 有 $m\times r$ 个元素， $V_r^T$ 有 $r\times n$ 个元， $\Sigma_r$ 则只需储存主对角的 $r$ 个非零元。若以 SVD 形式储存，总计有 $(m+n+1)\times r$ 个元。当矩阵的秩 $r$ 远小于 $m$ 和 $n$ 时，利用矩阵的 SVD 可以大幅减少储存量。

此外，从 $1$ 到 $r$ ，由于 $\sigma_1 ≥ \sigma_2≥…≥\sigma_r$ ，因此变换产生的的作用原来越小，通常可以用前面几个变换来替代整个线性变换，这便是主成分分析(PCA)的思想。

参考

阳明交通大学, 周志成线性代数 svd奇异值分解

Feature Column from the AMS

shunliz.gitbooks.io

奇异值分解(SVD)原理及应用 - 耐烦不急 - 博客园

奇异值分解(SVD)

特征值分解和奇异值分解 - gao_jian - 博客园

机器学习中的数学(5)-强大的矩阵奇异值分解(SVD)及其应用 - LeftNotEasy - 博客园