奇异值分解

矩阵的奇异值分解是指将m×nm \times nm×n实矩阵AAA表示为以下三个实矩阵乘积形式的运算

A=UΣVTA = U \Sigma V ^ { T }A=UΣVT

其中UUU是mmm阶正交矩阵，VVV是nnn阶正交矩阵，Σ\SigmaΣ是m×nm \times nm×n矩形对角矩阵

Σ=diag⁡(σ1,σ2,⋯,σp),p=min⁡{m,n}\Sigma = \operatorname { diag } ( \sigma _ { 1 } , \sigma _ { 2 } , \cdots , \sigma _ { p } ) , \quad p = \operatorname { min } \{ m , n \}Σ=diag(σ1​,σ2​,⋯,σp​),p=min{m,n}

其对角线元素非负，且满足σ1≥σ2≥⋯≥σp≥0\sigma _ { 1 } \geq \sigma _ { 2 } \geq \cdots \geq \sigma _ { p } \geq 0σ1​≥σ2​≥⋯≥σp​≥0

任意给定一个实矩阵，其奇异值分解一定存在，但并不唯一

奇异值分解包括紧奇异值分解和截断奇异值分解

紧奇异值分解是与原始矩阵等秩的奇异值分解，截断奇异值分解是比原始矩阵低秩的奇异值分解

奇异值分解有明确的几何解释

奇异值分解对应三个连续的线性变换：一个旋转变换，一个缩放变换和另一个旋转变换第一个和第三个旋转变换分别基于空间的标准正交基进行

设矩阵AAA的奇异值分解为A=UΣVTA = U \Sigma V ^ { T }A=UΣVT

则有ATA=V(ΣTΣ)VTAAT=U(ΣΣT)UT\left. \begin{array} { l } { A ^ { T } A = V ( \Sigma ^ { T } \Sigma ) V ^ { T } } \\\\ { A A ^ { T } = U ( \Sigma \Sigma ^ { T } ) U ^ { T } } \end{array} \right.ATA=V(ΣTΣ)VTAAT=U(ΣΣT)UT​

即对称矩阵ATAA^TAATA和AATAA^TAAT的特征分解可以由矩阵AAA的奇异值分解矩阵表示

矩阵AAA的奇异值分解可以通过求矩阵ATAA^TAATA的特征值和特征向量得到

ATAA^TAATA的特征向量构成正交矩阵VVV的列

从ATAA^TAATA的特征值λj\lambda _ { j }λj​的平方根得到奇异值σi\sigma _ { i }σi​

即σj=λj,j=1,2,⋯,n\sigma _ { j } = \sqrt { \lambda _ { j } } , \quad j = 1,2 , \cdots , nσj​=λj​​,j=1,2,⋯,n

对其由大到小排列，作为对角线元素，构成对角矩阵Σ\SigmaΣ

求正奇异值对应的左奇异向量，再求扩充的ATA^TAT的标准正交基，构成正交矩阵UUU的列

矩阵A=[aij]m×nA = [ a _ { i j } ] _ { m \times n }A=[aij​]m×n​的弗罗贝尼乌斯范数定义为

∥A∥F=(∑i=1m∑j=1n(aij)2)12\| A \| _ { F } = ( \sum _ { i = 1 } ^ { m } \sum _ { j = 1 } ^ { n } ( a _ { i j } ) ^ { 2 } ) ^ { \frac { 1 } { 2 } }∥A∥F​=(i=1∑m​j=1∑n​(aij​)2)21​

在秩不超过kkk的m×nm \times nm×n矩阵的集合中，存在矩阵AAA的弗罗贝尼乌斯范数意义下的最优近似矩阵XXX

秩为kkk的截断奇异值分解得到的矩阵AkA_kAk​能够达到这个最优值

奇异值分解是弗罗贝尼乌斯范数意义下，也就是平方损失意义下的矩阵最优近似

任意一个实矩阵AAA可以由其外积展开式表示A=σ1u1v1T+σ2u2v2T+⋯+σnunvnTA = \sigma _ { 1 } u _ { 1 } v _ { 1 } ^ { T } + \sigma _ { 2 } u _ { 2 } v _ { 2 } ^ { T } + \cdots + \sigma _ { n } u _ { n } v _ { n } ^ { T }A=σ1​u1​v1T​+σ2​u2​v2T​+⋯+σn​un​vnT​

其中ukvkTu _ { k } v _ { k } ^ { T }uk​vkT​为m×nm \times nm×n矩阵

是列向量uku _ { k }uk​和行向量vkTv _ { k } ^ { T }vkT​的外积，σk\sigma _ { k }σk​为奇异值

uk,vkT,σku _ { k } , v _ { k } ^ { T } , \sigma _ { k }uk​,vkT​,σk​通过矩阵AAA的奇异值分解得到

任意一个mmm x nnn 矩阵，都可以表示为三个矩阵的乘积（因子分解）形式

分别是mmm阶正交矩阵，由降序排列的非负的对角线元素组成的mmm x nnn 矩形对角矩阵

和nnn阶正交矩阵，称为该矩阵的奇异值分解

矩阵的奇异值分解一定存在，但不唯一

奇异值分解可以看作是矩阵数据压缩的一种方法，即用因子分解的方式近似地表示原始矩阵，这种近似是在平方损失意义下的最优近似

矩阵的奇异值分解是指，将一个非零的mmm x nnn 实矩阵A,A∈Rm×nA, A\in R^{m\times n}A,A∈Rm×n表示为一下三个实矩阵乘积形式的运算

A=UΣVTA = U\Sigma V^{T}A=UΣVT,

其中 UUU 是 mmm 阶正交矩阵， VVV 是 nnn 阶正交矩阵，Σ\SigmaΣ 是由降序排列的非负的对角线元素组成的mmm x nnn矩形对角矩阵

称为AAA 的奇异值分解

UUU的列向量称为左奇异向量， VVV的列向量称为右奇异向量

奇异值分解不要求矩阵AAA 是方阵，事实上矩阵的奇异值分解可以看作方阵的对角化的推广

紧奇奇异值分解

紧奇奇异值分解是与原始矩阵等秩的奇异值分解

截断奇异值分解

截断奇异值分解是比原始矩阵低秩的奇异值分解

代码实现

import numpy as np#基于矩阵分解的结果，复原矩阵
def rebuildMatrix(U, sigma, V):a = np.dot(U, sigma)a = np.dot(a, np.transpose(V))return a#基于特征值的大小，对特征值以及特征向量进行排序。倒序排列
def sortByEigenValue(Eigenvalues, EigenVectors):index = np.argsort(-1 * Eigenvalues)Eigenvalues = Eigenvalues[index]EigenVectors = EigenVectors[:, index]return Eigenvalues, EigenVectors#对一个矩阵进行奇异值分解
def SVD(matrixA, NumOfLeft=None):#NumOfLeft是要保留的奇异值的个数，也就是中间那个方阵的宽度#首先求transpose(A)*AmatrixAT_matrixA = np.dot(np.transpose(matrixA), matrixA)#然后求右奇异向量lambda_V, X_V = np.linalg.eig(matrixAT_matrixA)lambda_V, X_V = sortByEigenValue(lambda_V, X_V)#求奇异值sigmas = lambda_Vsigmas = list(map(lambda x: np.sqrt(x)if x > 0 else 0, sigmas))  #python里很小的数有时候是负数sigmas = np.array(sigmas)sigmasMatrix = np.diag(sigmas)if NumOfLeft == None:rankOfSigmasMatrix = len(list(filter(lambda x: x > 0,sigmas)))  #大于0的特征值的个数else:rankOfSigmasMatrix = NumOfLeftsigmasMatrix = sigmasMatrix[0:rankOfSigmasMatrix, :]  #特征值为0的奇异值就不要了#计算右奇异向量X_U = np.zeros((matrixA.shape[0], rankOfSigmasMatrix))  #初始化一个右奇异向量矩阵，这里直接进行裁剪for i in range(rankOfSigmasMatrix):X_U[:, i] = np.transpose(np.dot(matrixA, X_V[:, i]) / sigmas[i])#对右奇异向量和奇异值矩阵进行裁剪X_V = X_V[:, 0:NumOfLeft]sigmasMatrix = sigmasMatrix[0:rankOfSigmasMatrix, 0:rankOfSigmasMatrix]#print(rebuildMatrix(X_U, sigmasMatrix, X_V))return X_U, sigmasMatrix, X_V