矩阵的奇异值分解（SVD）（理论）
矩阵的奇异值分解(Singular Value Decomposition,SVD)是数值计算中的精彩之处，在其它数学领域和机器学习领域得到了广泛的应用，如矩阵的广义逆，主分成分析(PCA),自然语言处理(NLP)中的潜在语义索引（Latent Semantic Indexing）,推荐算法等。
鉴于实际应用，本次分享中的数域为实数域，即我们只在实数范围内讨论。我们假定读者具有大学线性代数的水平。那么，矩阵的奇异值分解定理如下：
（定理）（奇异值分解定理）任意一个m×n矩阵A可分解为
其中P是m×m正交矩阵，D是m×n对角阵，Q是n×n正交矩阵。
证明：矩阵ATA是n×n对称矩阵，因为(ATA)T=AT(AT)T=ATA.又因为
所以ATA是半正定矩阵，从而，ATA的特征值为非负数。
假设ATA的特征值为σ21,σ22,...,σ2n,其中，σ21,σ22,...,σ2r都是正的，σ2r+1,σ2r+2,...,σ2n都是0，r为ATA的秩。设{u1,u2,...,un}为ATA的标准正交特征向量集，则
于是(Aui)T(Aui)=uTi(ATA)ui=uTiσ2iui=σ2i.当i≥r+1时，σi=0,从而Aui=0.
用{uT1,uT2,...,uTn}作为行构成一个n×n矩阵Q.接着，定义
当1≤i,j≤r时，vi构成一个标准正交系，这是因为
其中δij为Kronecker符号，即当i=j时，δ=1,当i≠j时，δ=0.
我们选择额外的向量vi使得{v1,v2,...,vm}为Rm的标准正交基。设P是m×m矩阵，其列是v1,v2,...,vm.设D是m×n对角阵，σ1,σ2,...σr在其对角线上，其余地方均为0.于是有
这是因为(PTAQT)ij=vTiAuj,当j≥r+1时，该式为0，当j≤r时，该式为vTiσvj=σjδij,从而PTAQT=D.又因P,Q为正交矩阵，因此
证毕。
在上面证明中，我们称实数 σ1,σ2,...,σn(取非负数)为矩阵A的奇异值，它们是 ATA的特征值的非负平方根。定理中的分解 A=PDQ就是一个奇异值分解。由上面的证明，我们可以知道：矩阵的奇异值分解并不唯一，因为 σ1,σ2,...,σn的次序及 vr+1,vr+2,...,vn的选择并不唯一。
在Python中的Numpy模块中，已经实现了矩阵的奇异值分解。以下为示例的应用代码：
import numpy as np
#generate a random 3*4 matrix
A = np.random.randint(5, size=(3, 4))
#parameter full_matrices: control the size of P and Q
#d returns as numpy.ndarray, not matrix
P,d,Q = np.linalg.svd(A, full_matrices=True)
print('A:',A)
print('P:',P)
#D return as diagonal 3*4 matrix
D = np.zeros(12).reshape(3,4)
for i in range(len(d)):
D[i][i] = d[i]
print('D:',D)
print('Q:',Q)
#check if P*D*Q == A
print('P*D*Q:',np.dot(P,np.dot(D,Q)))输入结果如下：
至于如何用原始算法来实现矩阵的SVD，也是需要考虑的，有机会的话，可以交流哦~~
本次分享到此结束，欢迎大家批评与交流~~
参考文献：
- SVD 维基百科：https://en.wikipedia.org/wiki/SVD
- 数值分析 机械工业出版社 作者：萨奥尔(Timothy Sauer) 译者：裴玉茹
numpy的svd实现函数： https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.svd.html - 奇异值分解(SVD)原理与在降维中的应用：https://www.cnblogs.com/pinard/p/6251584.html
- 奇异值分解SVD应用——LSI：http://blog.csdn.net/abcjennifer/article/details/8131087
论文：CALCULATING THE SINGULAR VALUES AND PSEUDO-INVERSE OF A MATRIX, G. GOLUB AND W. KAHAN, J. SIAM llrM,B. AfeArd.Ser. B, Vol. 2, No. 2, 1965
