Singular Value Decomposition (SVD)是线性代数中十分重要的矩阵分解方法,被称为“线性代数的基本理论”,因为它不仅可以运用于所有矩阵(不像特征值分解只能用于方阵),而且奇异值总是存在的。
其中(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)。
对于奇异值分解可以从两个角度进行理解:一是将SVD视为对基向量组(bases),即坐标系的一顺序变换,二是将SVD视为对于数据点的变换。
一般来说要让矩阵(A)作用于另一个矩阵,都是左乘(A),所以由公式(1)可知道首先是(V^T),然后是(\Sigma),最后是矩阵(U)变换。所以矩阵(A)的变换实际上是经过了三个步骤,如下图所示(为方便理解使用了二维和三维图像进行说明):
假设左上角的单位圆是在(R^n)空间,其标准基用(B=v_1,v_2)表示。左下角的圆也在(R^n)空间里,其标准基用(\tilde{B}=e_1,e_2)表示,右下角的圆在(R^m)空间里,其标准基用(\tilde{C})表示。右上角的圆在(R^m)空间里。
下图更加形象地展示了奇异值分解的作用,变换过程和上面一样,故不再赘述:
本小节内容不证明SVD的存在性。
在介绍SVD如何计算之前,首先回顾一下【Math for ML】矩阵分解(Matrix Decompositions) (下)中介绍过任何对称矩阵都能对角化,其公式如下:
[S=S^T=PDP^T]
所以一个对称矩阵的奇异值分解是十分相似的,即
[S=U\Sigma 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计算的推导过程:
已知(A^TA)可作如下对角化运算,且其特征值(λ_i≥0)
[ \begin{align} A^TA=PDP^T=P \left \begin{matrix} λ_1 & \cdots & 0 \ \vdots & \ddots & \vdots \ 0 & \cdots & λ_n \end{matrix} \right P^T \tag{1.3.1} \ \end{align} ]
因为任何矩阵都可做奇异值分解,故有
[ A^TA=(U\Sigma V^T)^T(U\Sigma V^T)=V\Sigma^TU^TU\Sigma V^T \tag{1.3.2} ]
因为(U)为正交矩阵,所以(U^TU=I),所以(1.3.2)式进一步简化可得
[ \begin{align} A^TA=V\Sigma^T\Sigma V^T=V \left \begin{matrix} \sigma_1^2 & \cdots & 0 \ \vdots & \ddots & \vdots \ 0 & \cdots & \sigma_n^2 \end{matrix} \right V^T \tag{1.3.3} \ \end{align} ]
由(1.3.1)和(1.3.3)可得
[ V=P \ \sigma_i^2=\lambda_i \tag{1.3.4} ]
所以任意矩阵(A)的右奇异矩阵(V)是(A^TA)的特征矩阵(P)。
和求(V)类似,这里不再赘述。(U)即为(AA^T)的特征矩阵。
注意上面两步中已经求出了(\sigma_i^2),接下来要做的就是把上面所求出的(\sigma_i^2)从大到小排序并开根号,且(\Sigma)要与(A)的维度保持一致
具体的SVD计算示例可参见奇异值分解(SVD)计算过程示例。
下面对特征值分解(A=PDP^{-1})和奇异值分解(A=U\Sigma V^T)作如下总结和对比: