I. 奇异值分解(Singular Value Decomposition)

1. 定义

Singular Value Decomposition (SVD)是线性代数中十分重要的矩阵分解方法，被称为“线性代数的基本理论”，因为它不仅可以运用于所有矩阵(不像特征值分解只能用于方阵)，而且奇异值总是存在的。

SVD定理

设一个矩阵(A^{m×n})的秩为(r∈[0,min(m,n)]),矩阵(A)的奇异值分解形式如下:

[A=USigma V^T ag{1.1.1} ]

其中(U∈R^{m×m})是一个正交矩阵(即列向量(u_i,i=1,...,m)互相正交)，(V∈R^{n×n})也是一个正交矩阵(即列向量(v_i,i=1,...,n)互相正交),(Sigma)是一个(m×n)的矩阵，且满足$$Sigma_{ii}=sigma_i≥0 Sigma_{ij}=0,i≠j$$

上面的(sigma_i)称为奇异值(singular values),(u_i)称为左奇异值(left-singular values),(v_i)称为右奇异值(right-singular values)。另外通常默认有(sigma_1≥...≥sigma_r≥0) 。

注意：矩阵(A)是一个长方形矩阵，不一定是方阵，另外(Sigma)和矩阵(A)的维度相同，并且其包含一个对角子矩阵(diagonal submatrix)。

2. 图解SVD

对于奇异值分解可以从两个角度进行理解：一是将SVD视为对基向量组(bases)，即坐标系的一顺序变换，二是将SVD视为对于数据点的变换。

一般来说要让矩阵(A)作用于另一个矩阵，都是左乘(A),所以由公式(1)可知道首先是(V^T)，然后是(Sigma),最后是矩阵(U)变换。所以矩阵(A)的变换实际上是经过了三个步骤，如下图所示(为方便理解使用了二维和三维图像进行说明)：

假设左上角的单位圆是在(R^n)空间，其标准基用(B=[v_1,v_2])表示。左下角的圆也在(R^n)空间里，其标准基用( ilde{B}=[e_1,e_2])表示，右下角的圆在(R^m)空间里，其标准基用( ilde{C})表示。右上角的圆在(R^m)空间里。

由左上角到左下角：可以很清楚的看到(V^T∈R^{n×n})的作用是对最开始的坐标轴(或标准基)((B))还原成canonical basis(( ilde{B}))。所以(V^T)的作用是将坐标轴由(B)转变成( ilde{B})。
由左下角到右下角：经过(Sigma)矩阵变换后从(R^n)空间转换到了(R^m)空间。上图是从二维空间变成了三维空间，即增加了z轴。当然维度也可以减少。此外单位圆还是处在([e_1,e_2])空间内(即(x,y)轴组成的空间内)，而且还会根据奇异值的大小做相应比例的伸缩。
右下角到右上角: 矩阵(U)继续对([e_1,e_2])基做变换，增加的那个维度(z轴)方向不做变化。

下图更加形象地展示了奇异值分解的作用，变换过程和上面一样，故不再赘述：

3. SVD计算

本小节内容不证明SVD的存在性。

在介绍SVD如何计算之前，首先回顾一下【Math for ML】矩阵分解(Matrix Decompositions) （下）中介绍过任何对称矩阵都能对角化，其公式如下：

[S=S^T=PDP^T ]

所以一个对称矩阵的奇异值分解是十分相似的，即

[S=USigma V^T ]

对比之后可知有(U=P,V=P,Sigma=D)

另外我们还需要知道的是对于任意矩阵(A∈R^{m×n}),其转置矩阵和其本身相乘之后得到的矩阵都是对称矩阵，即(A^TA∈R^{n×n})和(AA^T∈R^{m×m})均为对称矩阵。(证明略)

接下来结合SVD公式给出对任意矩阵(A∈R^{m×n})SVD计算的推导过程：

计算(V)

已知(A^TA)可作如下对角化运算，且其特征值(λ_i≥0)

[egin{align} A^TA=PDP^T=P left[ egin{matrix} λ_1 & cdots & 0 \ vdots & ddots & vdots \ 0 & cdots & λ_n end{matrix} ight] P^T ag{1.3.1} \ end{align} ]

因为任何矩阵都可做奇异值分解，故有

[A^TA=(USigma V^T)^T(USigma V^T)=VSigma^TU^TUSigma V^T ag{1.3.2} ]

因为(U)为正交矩阵，所以(U^TU=I),所以(1.3.2)式进一步简化可得

[egin{align} A^TA=VSigma^TSigma V^T=V left[ egin{matrix} sigma_1^2 & cdots & 0 \ vdots & ddots & vdots \ 0 & cdots & sigma_n^2 end{matrix} ight] V^T ag{1.3.3} \ end{align} ]

由(1.3.1)和(1.3.3)可得

[V=P \ sigma_i^2=lambda_i ag{1.3.4} ]

所以任意矩阵(A)的右奇异矩阵(V)是(A^TA)的特征矩阵(P)。

计算(U)

和求(V)类似，这里不再赘述。(U)即为(AA^T)的特征矩阵。

计算(Sigma)

注意上面两步中已经求出了(sigma_i^2),接下来要做的就是把上面所求出的(sigma_i^2)从大到小排序并开根号，且(Sigma)要与(A)的维度保持一致

具体的SVD计算示例可参见奇异值分解(SVD)计算过程示例。

4. 特征值分解（EVD） vs. 奇异值分解（SVD）

下面对特征值分解(A=PDP^{-1})和奇异值分解(A=USigma V^T)作如下总结和对比：

SVD对于任意矩阵都存在；而EVD只能在n阶方阵的基础上才能被定义，而且只有当方阵满秩，即有n个独立的特征向量条件下才可以做特征值分解；
特征值分解后得到的矩阵(P)不必须是正交矩阵，也就是说(P)可以起到伸缩和旋转的作用；而SVD中的(U,V)矩阵都必须是正交矩阵，所以这两个矩阵只能起到旋转变换的作用，起伸缩变换作用的是矩阵(Sigma)。
特征值分解和奇异值分解都由以下三个线性映射步骤组成：
1.Change of basis in the domain
2.Independent scaling of each new basis vector and mapping from domain to co-domain
3.Change of basis in the co-domain