本文所述矩阵均为实矩阵； 本文所述中，行空间（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} $$
而不管是特征值分解还是奇异值分解，都是把这个变换拆解开。也就是把一个复杂的变换动作拆解开。例如，对称半正定矩阵的特征值分解是把矩阵的变换动作拆解为旋转、伸缩、旋转三个变换。
注：对角矩阵只有拉伸收缩的效果。（伸缩也包含了将某一个维度缩为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^A)^T = A^TA$
证明半正定：对任意非零向量x, 向量Ax的二范数$||Ax||^2 = (Ax)^TAx= x^TA^Ax$， 因为模长$||Ax||^2 ≥ 0$, 因此二次型矩阵 $A^TA$ 为半正定矩阵。
- 对称：决定了特征向量为正交的
- 正定：决定了特征值为非负数
- 矩阵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)的思想。