矩阵的奇异值分解（SVD）（理论）

水深无声 2022-06-03 03:59 349阅读 0赞

矩阵的奇异值分解(Singular Value Decomposition,SVD)是数值计算中的精彩之处，在其它数学领域和机器学习领域得到了广泛的应用，如矩阵的广义逆，主分成分析(PCA),自然语言处理(NLP)中的潜在语义索引（Latent Semantic Indexing）,推荐算法等。  
　　鉴于实际应用，本次分享中的数域为实数域，即我们只在实数范围内讨论。我们假定读者具有大学线性代数的水平。那么，矩阵的奇异值分解定理如下：

（定理）（奇异值分解定理）任意一个m×n矩阵A可分解为

A=PDQ

其中P是m×m正交矩阵，D是m×n对角阵，Q是n×n正交矩阵。

证明：矩阵ATA是n×n对称矩阵，因为(ATA)T=AT(AT)T=ATA.又因为

xT（ATA）x=(Ax)T(Ax)≥0,

所以ATA是半正定矩阵，从而，ATA的特征值为非负数。  
　　假设ATA的特征值为σ21,σ22,...,σ2n,其中，σ21,σ22,...,σ2r都是正的，σ2r\+1,σ2r\+2,...,σ2n都是0，r为ATA的秩。设\{ u1,u2,...,un\}为ATA的标准正交特征向量集，则

ATAui=σ2iui(i=1,2,...,n)

于是(Aui)T(Aui)=uTi(ATA)ui=uTiσ2iui=σ2i.当i≥r\+1时，σi=0,从而Aui=0.

用\{ uT1,uT2,...,uTn\}作为行构成一个n×n矩阵Q.接着，定义

vi=σ−1iAui(1≤i≤r).

当1≤i,j≤r时，vi构成一个标准正交系，这是因为

vTivj=σ−1i(Aui)Tσ−1j(Auj)=(σiσj)−1(uTiATAuj)=(σiσj)−1(uTiσ2juj)=δij,

其中δ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.于是有

A=PDQ.

这是因为(PTAQT)ij=vTiAuj,当j≥r\+1时，该式为0，当j≤r时，该式为vTiσvj=σjδij,从而PTAQT=D.又因P,Q为正交矩阵，因此

A=PDQ.

证毕。  
　　在上面证明中，我们称实数  σ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)))

输入结果如下：  
![这里写图片描述][SouthEast]

至于如何用原始算法来实现矩阵的SVD，也是需要考虑的，有机会的话，可以交流哦~~  
　　本次分享到此结束，欢迎大家批评与交流~~

--------------------

参考文献：

1.  SVD 维基百科：[https://en.wikipedia.org/wiki/SVD][https_en.wikipedia.org_wiki_SVD]
2.  数值分析 机械工业出版社 作者：萨奥尔(Timothy Sauer) 译者：裴玉茹  
    numpy的svd实现函数： [https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.svd.html][https_docs.scipy.org_doc_numpy_reference_generated_numpy.linalg.svd.html]
3.  奇异值分解(SVD)原理与在降维中的应用：[https://www.cnblogs.com/pinard/p/6251584.html][https_www.cnblogs.com_pinard_p_6251584.html]
4.  奇异值分解SVD应用——LSI：[http://blog.csdn.net/abcjennifer/article/details/8131087][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

[SouthEast]: /images/20220603/2de73fc00c3441d6b439be10a6f45682.png
[https_en.wikipedia.org_wiki_SVD]: https://en.wikipedia.org/wiki/SVD
[https_docs.scipy.org_doc_numpy_reference_generated_numpy.linalg.svd.html]: https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.svd.html
[https_www.cnblogs.com_pinard_p_6251584.html]: https://www.cnblogs.com/pinard/p/6251584.html
[http_blog.csdn.net_abcjennifer_article_details_8131087]: http://blog.csdn.net/abcjennifer/article/details/8131087