奇异值分解SVD

主要参考https://www.cnblogs.com/pinard/p/6251584.html，
https://www.cnblogs.com/LeftNotEasy/archive/2011/01/19/svd-and-applications.html

奇异值分解(Singular Value Decomposition,SVD)，用于降维算法的特征分解、推荐系统、NLP等

1.特征值和特征向量

A x = λ x

方阵A：n×n
特征向量x：1×n—— $w_{1}, w_{2}, . . ., w_{n}$
特征值： $λ$ —— $λ_{1} \leq λ_{2} \leq . . . \leq λ_{n}$

A = W Σ W^{- 1}

W：n×n，上述特征向量集合
$Σ$ ：n×n，主对角线为n个特征值的对角矩阵
标准化得 $‖ w_{i} ‖_{2} = 1$ ，则 $w_{i}^{T} w_{i} = 1$ ，则 $W^{T} W = I$ ，则 $W^{T} = W^{- 1}$ ，则W为酉矩阵

A = W Σ W^{T}

补充：取topK个特征值对应的特征向量即可实现降维，特征值表示特征的重要性
限制：A必须为方阵

特点：不要求分解的矩阵为方阵

A = U Σ V^{T}

待分解矩阵A：m×n
U：m×m，由左奇异向量组成
$Σ$ ：m×n，主对角线为奇异值，其他为0
V：n×n，由右奇异向量组成
U和V均为酉矩阵，即 $U^{T} U = I, V^{T} V = I$

求解上述三个矩阵：

(A^{T} A) v_{i} = λ_{i} v_{i}

用n×n的方阵

A^{T} A

做特征值分解，得到n个特征值和特征向量v，作为右奇异向量，得到右侧的V矩阵；

(A A^{T}) u_{i} = λ_{i} u_{i}

用m×m的方阵

A A^{T}

做特征值分解，得到n个特征值和特征向量u，作为左奇异向量，得到左侧的U矩阵；

求解奇异值：

A = U Σ V^{T} \Rightarrow A V = U Σ V^{T} V \Rightarrow A V = U Σ \Rightarrow A v_{i} = σ_{i} u_{i} \Rightarrow σ_{i} = A v_{i} / u_{i}

另外：

A = U Σ V^{T} \Rightarrow A^{T} = V Σ^{T} U^{T} \Rightarrow A^{T} A = V Σ^{T} U^{T} U Σ V^{T} \Rightarrow V Σ^{2} V^{T}

则

A^{T} A

的特征向量组成V，同理

A A^{T}

的特征向量组成U。且特征值是奇异值的平方，即

σ_{i} = \sqrt{λ_{i}}

奇异值分解SVD

奇异值和特征值类似，且奇异值减少很快，“在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。”。所以可以用topK个奇异值近似描述矩阵

A_{m \times n} = U_{m \times m} Σ_{m \times n} V_{n \times n}^{T} \approx U_{m \times k} Σ_{k \times k} V_{k \times n}^{T}

则实现用三个小矩阵近似描述大矩阵A，如灰色部分
奇异值分解SVD

如：在PCA中，需要先计算样本协方差矩阵

X^{T} X

，再计算最大的d个特征向量，样本数和特征数多的时候计算量很大。一些SVD实现算法不需要先求出协方差矩阵

X^{T} X

也可以求出右奇异矩阵，sklearn就是使用SVD。另外，左奇异矩阵可以用于行数的压缩

按照参考2的解释，矩阵乘法就是线性变换的过程，特征值大小反映了变换方向的重要性
奇异值分解SVD