奇异值分解定理

性质 7：如果矩阵 A 对称，存在特征值分解A = UΔU T ，其中Δ = diag(λ1 , λ2 , … , λn )， U = [ u1 , u2 , … , un ]且UU T = I。则 A 的一个奇异值分解是 A= UΣV T ，其中σi = |λi |。当 A 是正定 矩阵时，特征值分解和奇异值分解相同。
n ∗n � = [U U � T AV = � Σ � � � ]。U 将矩阵 U 补充成正交矩阵U (m −n)∗ n � ≡ Σ，则 rank(A)=rank(Σ)。 0 � 和 V 非奇异，则 rank(A)=rank(U � T AV)=r。 因为U
σ 0 1 0 1 0 �� � � �V � ��。即若(m-1)*(n-1)阶的矩阵存在奇异值分解，则 m*n 阶矩 A = �U � 0 V1 0 U1 0 Σ1
σ1 w σ1 σ2 + ww T 2 2 � � ≥ σ1 + ww T = �σ1 + ww T � � T � � �� � � = � � 1 T B wT w 2 2 Bw 2 σ1 ‖ Sx ‖2 � S �w T � �2 2 σ1 = ��|A|�� = ��|S|�� = maxx ≠0 ≥ ≥ �σ1 + ww T σ1 ‖x ‖2 2 2 �� T � � w 2 所以 w=0 . σ 0 σ 0 故U T AV = � �� = �0 B�。 � T AV 0 U
U = [ u1 , u2 , … , un ]和V = [ν1 , ν2 , … , νn ]。则 H 的 2n 个特征值是±σi ，具有相应的单位特征向量 νi 1 �±μ �。 2 √ i
T 其中 A 为 m*m 阶矩阵且A = UΣV T 是 A 的 SVD。 性质 6： 设H = � 0 A � ， 设Σ = diag(σ1 , … , σn )， A 0

矩阵奇异值分解定理的直观证明
矩阵奇异值分解（Singular Value Decomposition，SVD）是线性代数中的一个重要概念，它为各种机器学习和数据挖掘技术提供了基础。

其独特之处在于把一个矩阵分解为三个矩
阵的乘积，因此又被称为三角分解或者三因子分解。

它的定理被称为矩阵奇异值分解定理，是关于任意实矩阵M可以分解为三个矩阵乘积的一个重要结论。

矩阵奇异值分解定理的证明过程涉及到一些数字计算，它的证明可以分为多个步骤：
1）将M矩阵以特征值分解的形式写出：M=UΣV'，其中U是特征向量矩阵，Σ是特征值所组成的对角矩阵，V'是转置矩阵。

2）首先，将M矩阵看作是U列空间和V行空间组成的两个子空间。

3）从U空间中选取最大特征值对应的特征向量u1，此向量与V空间中相关的特征向量v1
正交，故令v1与u1的点积为0，则u1'V=0。

4）又因为V剩下的特征向量组成的子空间可以被U剩下的特征向量组成的原子空间（超
平面）正交，可以得到U剩下的特征向量的线性相关，即U剩下的特征向量也可以写成U1的线性组合。

5）通过这几个步骤，得出结论M可以分解成三个矩阵的乘积：M=UΣV'，其中U和V分别
是M的左奇异矩阵和右奇异矩阵，Σ是M的特征值所组成的对角矩阵。

经过以上证明，矩阵奇异值分解定理得以证明，它提供了矩阵M可以分解成低秩矩阵的一
种方法。

SVD可以用来对矩阵进行降维，可以有效削减矩阵的维数，减少计算量，提高程
序的运行速度，广泛应用于机器学习和数据挖掘技术，是一种重要而有用的数学计算方法。

奇异值分解（Singular Value Decomposition，简称SVD）是一种常用的矩阵分解方法，广泛应用于数据降维、特征提取、推荐系统等领域。

在实际应用中，使用奇异值分解进行数据预处理能够提高数据的质量和准确性。

本文将介绍使用奇异值分解进行数据预处理的技巧，并探讨其在实际问题中的应用。

一、奇异值分解的基本原理奇异值分解是一种将一个矩阵分解为三个矩阵乘积的方法，其基本原理是将原始矩阵分解为三个矩阵的乘积：A=UΣV^T，其中A是一个m×n的矩阵，U是一个m×m的正交矩阵，Σ是一个m×n的对角矩阵，V^T是一个n×n的正交矩阵。

其中，U的列向量称为左奇异向量，V的列向量称为右奇异向量，Σ的对角线元素称为奇异值。

二、数据降维与特征提取在实际应用中，奇异值分解常用于数据降维和特征提取。

通过对原始数据矩阵进行奇异值分解，可以得到数据的主要特征和结构信息，进而实现数据的降维和特征提取。

通过保留最重要的奇异值和对应的奇异向量，可以实现数据的降维，减少数据的维度和复杂度，同时保留数据的主要特征。

此外，奇异值分解还可以用于特征提取，通过提取奇异值和对应的奇异向量，获取数据的主要特征和结构信息，进而实现数据的特征提取和表征。

三、推荐系统中的应用奇异值分解在推荐系统中有着重要的应用。

在推荐系统中，用户-物品矩阵是一个非常稀疏的矩阵，通过对用户-物品矩阵进行奇异值分解，可以实现对用户和物品的隐含特征的提取和表征，进而实现对用户的个性化推荐。

通过奇异值分解，可以将用户-物品矩阵分解为用户特征矩阵和物品特征矩阵的乘积，从而实现对用户和物品的特征表征和推荐。

四、数据预处理中的技巧在实际应用中，使用奇异值分解进行数据预处理时，有一些技巧和注意事项需要注意。

首先，对原始数据矩阵进行中心化处理，即将每个特征的均值减去，使得数据的均值为0，这样可以消除数据的偏置影响。

其次，对数据矩阵进行标准化处理，即将每个特征的方差归一化为1，使得数据的尺度一致，进而提高奇异值分解的稳定性和准确性。

奇异值分解及行转置矩阵与行反对称矩阵的奇异值分解定理的证明1.奇异值分解（Smgluar Value Decompositiong ）设M 是一个m n ⨯矩阵，则有M=*U V ∑其中U 是m m ⨯阶酉矩阵，∑是半正定m n ⨯阶对角矩阵，V 是n n ⨯阶酉矩阵，*V 表示V 的共轭转置（下文中都是如此表示），称上述分解为M 的奇异值分解，∑对角线上的元素ii ∑称为M 的奇异值。

U （左奇异向量）系列是*MM 系特征向量； V （右奇异向量）系列是*M M 系特征向量；∑（非零奇异值）的非零元素是*M M 或*MM 中非零特征值的平方根。

例：求矩阵A=101011010⎛⎫⎪⎪ ⎪⎝⎭的奇异值分解.解：由*A A =101011112⎛⎫ ⎪⎪ ⎪⎝⎭可求得*A A 的特征值为1λ=3，2λ=1，3λ=0，对应的特征向量依次为1x =()1,1,2T ，2x =()1,1,0T -，3x =()1,1,1T-，于是可得rank （A ）=2，001⎫∆=⎪⎝⎭，令()12,V V V =，其中1V =，)23V x =，计算*11=00U AV =∆ ⎪ ⎪⎝⎭，构造()2=0,0,1TU ，则()120=,0001U U U ⎫⎪⎪⎪=⎪⎪ ⎪ ⎪⎝⎭,从而可得A 的奇异值分解*00A=U 010000V ⎫⎪ ⎪ ⎪⎝⎭2.下面对矩阵的行转置与行反对称矩阵的定义与它们的奇异值分解定理的证明下面所用公式的表达方式与上稍有不同，但所用理论相同.用n J J =表示反对角线元素全为1，其余元素全为0的n 阶方阵；m I I =为m 阶单位阵；T A ，*A 分别表示矩阵A 的转置、共轭转置.显然21,,T J J J I J J -===. 行转置矩阵与行反对称矩阵定义1 设()m nij A a R ⨯=∈，则称,1,21,11,21,2122211121m m mn m m m n R n n a a a a a a A a a a a a a ---⎛⎫⎪ ⎪ ⎪= ⎪ ⎪ ⎪⎝⎭为矩阵A 的行转置矩阵并记为RA .特别，若RA A =，则称A 为行对称矩阵；若R A A =-，则称A 为行反对称矩阵.显然：行反对称矩阵只有两种类型B JB ⎛⎫ ⎪ ⎪ ⎪-⎝⎭或0B JB ⎛⎫ ⎪⎪⎪-⎝⎭定理1 设*,,m n B C m n B UDV ⨯∈≥=为B 的奇异值分解，其中2酉阵m n U C ⨯∈，n n V C ⨯∈，0D ∑⎛⎫= ⎪⎝⎭,12(,,,)n diag σσσ∑= ，120n σσσ≥≥≥≥ ，则行反对称矩阵2m n m B A CJ B ⨯⎛⎫=∈ ⎪-⎝⎭存在一个奇异值分解HA PTV =,其中00T ⎫⎫==⎪⎪⎝⎭⎝⎭，m mU m U J P J I ⎛⎫=⎪-⎭. 证明：因为()***m m B A A B B J J B ⎛⎫=- ⎪-⎝⎭***22B B VD DV ===()2*2V V ∑，222122,2,,2nσσσ 为*A A12,n 为A 的奇异值.又 ****20120m m m m m mm m UJ UU J U U P P I J U I J I I ⎛⎫⎛⎫-⎛⎫===⎪ ⎪⎪-⎝⎭⎝⎭⎝⎭， 因而P 为酉矩阵，且****0m m m m m UJ B UDV PTV V A J UI J B J UDV ⎫⎛⎫⎫⎛⎫====⎪ ⎪⎪ ⎪---⎭⎝⎭⎝⎭⎝⎭ 证毕.定理 2 设*,,m n B C m n B UDV ⨯∈≥=为B 的奇异值分解，其中2酉阵m n U C ⨯∈，n nV C⨯∈，0D ∑⎛⎫= ⎪⎝⎭,12(,,,)n diag σσσ∑= ，120n σσσ≥≥≥≥ ，则行反对称矩阵(21)0m n m B A C J B +⨯⎛⎫ ⎪=∈ ⎪ ⎪-⎝⎭，存在一个奇异值分解*A PTV =,其中000T ⎫⎫⎪==⎪ ⎪⎝⎭ ⎪⎝⎭,0000m mm U J P J UI ⎛⎫⎪=⎪⎪-⎭. 证明：因为()******2*0022(2)m m B A A B B J B B VD DV V V J B ⎛⎫⎪=-===∑ ⎪ ⎪-⎝⎭,222122,2,,2nσσσ 为*A A12,n 为A 的奇异值.又****21000010000010200m m m m m m m m U U J UJ U U P P I J I J U I I +⎛⎫-⎛⎫⎛⎫⎪ ⎪ ⎪=== ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭， 因而P 为酉矩阵，且****00000000m m m m m UJ UDV B PTV V A J U I J UDV J B ⎛⎫⎛⎫⎛⎫⎪ ⎪ ⎪====⎪⎪ ⎪ ⎪ ⎪⎪⎪ ⎪---⎝⎭⎝⎭⎭⎝⎭证毕.。

奇异值分解定理奇异值分解（Singular Value Decomposition，简称SVD）是线性代数中一种重要的矩阵分解方法，常用于数据分析、信号处理、图像压缩等领域。

SVD的定理表明，任何矩阵都可以分解成三个矩阵的乘积，其中一个矩阵是正交矩阵，另外两个矩阵是对角矩阵，且对角线上的元素称为奇异值。

奇异值分解定理的数学概念比较复杂，需要一定的线性代数基础。

下面将对奇异值分解定理进行详细解释。

给定一个m行n列的实数矩阵A，假设rank(A)为r.那么存在两个实数方阵U(m×r)和V(n×r)，使得：A = UΣV^T其中，U的每一列是A^TA的特征向量，V的每一列是AA^T的特征向量，Σ是一个对角矩阵，对角线上的元素称为奇异值。

奇异值分解定理的证明比较复杂，这里只给出一个简要的证明思路。

假设A的列向量为{a1, a2, ..., an}，它们构成了一个n维向量空间的一组基。

我们可以将这组基转化为标准正交基，得到一组正交矩阵U和V。

然后我们可以通过对U和V进行一些数学操作，得到UΣV^T形式的矩阵。

最后，我们可以证明这个矩阵确实满足奇异值分解定理的要求。

奇异值分解定理在数据分析中有广泛的应用。

例如，在推荐系统中，我们可以通过SVD将用户对物品的评分矩阵分解，得到用户和物品的特征矩阵，从而进行个性化推荐。

在语音识别中，我们可以通过SVD将语音信号分解成一组基本声音的叠加，从而实现语音信号的降噪和特征提取。

在图像压缩中，我们可以通过SVD将图像分解成一组基本的图像模式，从而实现图像的降噪和压缩。

奇异值分解定理的应用不仅局限于上述领域，还可以应用于信号处理、图像处理、文本处理等其他领域。

通过奇异值分解，我们可以将复杂的问题转化为简单的线性代数运算，从而大大简化问题的求解过程。

然而，奇异值分解也有一些限制。

首先，奇异值分解是一种数值方法，对计算精度要求较高。

其次，奇异值分解的计算复杂度较高，对于大规模矩阵的分解可能会很耗时。

svd 矩阵的奇异值分解奇异值分解（Singular Value Decomposition，SVD）是一种重要的矩阵分解方法，可以将一个矩阵分解为三个矩阵的乘积，其中一个矩阵是正交矩阵，另外两个矩阵是对角矩阵。

SVD在数据分析、图像处理、信号处理等领域有着广泛的应用。

1. SVD的定义对于一个m\times n的实数矩阵A，它的奇异值分解是指将它分解为以下形式的乘积：A=U\Sigma V^T其中，U是一个m\times m的正交矩阵，V是一个n\times n的正交矩阵，\Sigma是一个m\times n的对角矩阵，对角线上的元素称为A的奇异值。

2. SVD的求解SVD的求解可以通过奇异值分解定理来实现。

奇异值分解定理指出，对于任意一个实数矩阵A，都存在一个奇异值分解A=U\Sigma V^T，其中U和V都是正交矩阵，\Sigma是一个对角矩阵，对角线上的元素是A的奇异值。

具体地，SVD的求解可以分为以下几个步骤：（1）计算A^TA和AA^T的特征值和特征向量。

（2）根据特征值和特征向量，求出A^TA和AA^T的特征分解。

（3）根据A^TA和AA^T的特征分解，求出A的奇异值分解。

3. SVD的应用SVD在数据分析、图像处理、信号处理等领域有着广泛的应用。

（1）数据分析在数据分析中，SVD可以用来降维和去噪。

通过SVD分解，可以将高维数据降到低维，从而减少数据的冗余信息，提高数据的处理效率。

同时，SVD还可以用来去除数据中的噪声，提高数据的质量。

（2）图像处理在图像处理中，SVD可以用来压缩图像和去噪。

通过SVD分解，可以将图像压缩为较小的尺寸，从而减少存储空间和传输带宽。

同时，SVD还可以用来去除图像中的噪声，提高图像的质量。

（3）信号处理在信号处理中，SVD可以用来分解信号和去噪。

通过SVD分解，可以将信号分解为多个频率分量，从而更好地理解信号的特性。

同时，SVD还可以用来去除信号中的噪声，提高信号的质量。

奇异值分解原理1 什么是奇异值分解奇异值分解（Singular Value Decomposition，SVD）是一种用于变换技术，它可以将任意一个方阵（matrix）分解成三个单独的反映它特征的矩阵：左奇异矩阵，右奇异矩阵，和奇异值矩阵。

分解后，可以用这三个矩阵的乘积来重构原矩阵，并用这些矩阵来解释矩阵的特征。

2 奇异值分解的数学原理奇异值分解的数学原理是特征值分解的一个推广，本质上将一个矩阵分解成一个“基正交正交矩阵”、一个可正交矩阵和另一个“基正交反正交矩阵”的三元组称为“奇异值元组”。

也就是把一个方阵A，分解成下面三个矩阵乘积：A = U*S*V'其中U为左奇异矩阵，S为奇异值矩阵，V'为右奇异矩阵，前后的矩阵是对称轴对称的，中间的矩阵是对角矩阵。

U和V是秩为m的正交矩阵，S是秩为n的“奇异值矩阵，D是一个证明SVD有效的参数，它是为了满足SVD中各矩阵乘积等于原矩阵A。

3 奇异值分解的应用奇异值分解在很多研究领域都有应用，比如自然语言备注、机器学习、数据挖掘等，它也成为自然语言处理中常见的基础算法，通过SVD，可以将一个原本比较复杂的单词语料库转换成更多的向量；另外，在数据挖掘领域中，SVD也可以用来识别历史模式以及未来趋势，从而实现营销预测等目的。

4 总结总之，奇异值分解是一种广泛用于数据分析和计算机技术的数学方法，它可以将任意一个矩阵（matrix）分解成三个单独的矩阵，分别反映它的特征。

它已经被广泛应用于自然语言处理、机器学习、数据挖掘等领域，能帮助研究人员从数据中挖掘更多信息以及实现营销预测等目的。

称上式为矩阵A的奇异值分解 .
推论 在矩阵A的奇异值分解A=UDVH中，U的列向量 为AAH的特征向量， V的列向量为AHA的特征向量.
证明 AAH (UDV H )(UDV H )H
UDV HVDU H UD2U H
(AAH )U UD2 Udiag(1, 2, , r ,0, ,0)
O
O
O
②
将 V 分块为
V (V1 V2 )
其中 V1 ，V2 分别是V 的前 r 列与后 n r 列.
并改写②式为
则有
AH AV
V
2
O
O
O
AH AV1 V1 2， AT AV2 O
③
由③的第一式可得
V1H AH AV1 2， 或者( AV1 1)H ( AV1 1) Ir
由③的第二式可得
即： AHA与AAH非0特征值相同，并且非零特 征值的个数为rank( A)
奇异值的定义
设A Crmn , 且AH A的特征值为
1 2 r r1 m 0
称i i ,i 1, , r,为矩阵A的正奇异值，
简称奇异值
说明：A的正奇异值个数等于rank( A)，并且A与AH有相同的奇
于是可得：rankA 2,
3 0
10,
令 V V1,V2 ,
其中
V1
1 6 x1,
1 2
x2
,
V2
1 3
x3
1 2
计算：
U1
AV11
1 2
0
1
2 1
2
0
构造：U2 0,0,1T 则
1 1 0
2 2
U
U1,U2
1 2

奇异值分解计算齐次方程解一、奇异值分解的原理和步骤A=UΣV^T其中，A是一个m×n的实数矩阵，U是一个m×m的正交矩阵，Σ是一个m×n的对角矩阵，V^T是一个n×n的正交矩阵。

具体的奇异值分解步骤如下：1.对矩阵A进行转置，得到A^T。

2.计算A^TA，得到一个n×n的对称矩阵B。

3.对B进行特征值分解，得到特征值和特征向量，即B=QΛQ^T。

4.计算矩阵A的奇异值和左奇异向量。

奇异值是特征值的平方根，即σi=√(λi)，左奇异向量是特征向量Q的列向量。

5.构造矩阵U和V。

U的列向量是A^TA的特征向量除以奇异值，V的列向量是A的特征向量除以奇异值。

6.将奇异值按照从大到小的顺序排列，并对U和V进行相应的调整。

二、使用奇异值分解计算齐次方程的解假设我们有一个线性齐次方程Ax=0，其中A是一个m×n的矩阵，x 是一个n×1的向量。

我们要找到满足方程的解x。

根据奇异值分解的原理，矩阵A可以分解为A=UΣV^T。

将这个分解代入方程Ax=0中，我们可以得到：UΣV^Tx=0由于U和V是正交矩阵，它们的逆矩阵和转置矩阵相等，即U^T=U^-1，(V^T)^T=V^-1将上述等式两边同时乘以V，我们可以得到：UΣ(V^Tx)=0由于Σ是一个对角矩阵，只有对角线上的元素不为零，因此我们可以将方程进一步简化为：(Σ(V^Tx))=0由于Σ是对角矩阵，它的对角线上的元素是奇异值。

我们可以将方程进一步简化为：(σ1(v1^Tx), σ2(v2^Tx), ..., σn(vn^Tx)) = 0根据上述方程，我们可以得到n个独立的方程：σ1(v1^Tx)=0σ2(v2^Tx)=0...σn(vn^Tx) = 0这些方程可以写成一个齐次线性方程组的形式：Mx=0其中，M是一个n×n的矩阵，每一行是一个方程。

x是一个n×1的向量。

我们可以使用奇异值分解来计算上述齐次线性方程组的解。

线性代数中的奇异值分解方法及应用奇异值分解（Singular Value Decomposition，简称SVD）是一种重要的矩阵分解方法，它可以将任意一个矩阵分解成三个矩阵的乘积，从而实现对矩阵的特征信息的提取和分析。

在线性代数、数据分析、信号处理、图像处理等领域都有着广泛的应用。

一、SVD的定义及原理SVD将一个m×n的矩阵A分解成：A=UΣV^T其中，U是一个m×m的正交矩阵，Σ是一个m×n的矩阵，其主对角线上的元素为实数且非负，称为奇异值（Singular Value）且按递减顺序排列，其余元素均为零，V是一个n×n的正交矩阵，T表示矩阵的转置。

对矩阵A进行SVD分解的过程可以用以下的几个步骤来描述：1. 计算矩阵A×A^T和A^T×A的特征值和特征向量；2. 将特征值按从大到小的顺序排列，得到奇异值的列表；3. 计算左奇异向量和右奇异向量，构成矩阵U和V。

由于SVD分解的特殊形式，U和V是正交矩阵，能够方便地与其他矩阵相乘和求逆。

而Σ是一个对角矩阵，它的主对角线上的元素正是矩阵A的奇异值，可以用来描述矩阵A的主要特征。

二、SVD的应用1. 数据降维由于奇异值按从大到小排列，因此前k个奇异值对应的列向量就是矩阵A的主要特征。

这使得SVD 分解成为一种有效的数据降维技术，可以减少数据的维度，改进模型的训练速度和精度。

2. 图像处理在图像处理中，SVD可以应用于图像的压缩、噪声滤除、图像变形、图像分解等方面。

例如，对于一张灰度图像，可以将其表示为一个矩阵，然后对矩阵进行SVD分解，取前k个奇异值和对应的左右奇异向量，就可以将图像压缩成一个较小的矩阵，从而减少存储和传输的开销。

而且，这种压缩方式对图像信息的损失很小，可以保持图像的很好质量。

3. 推荐系统在推荐系统中，SVD可以应用于用户行为分析和产品推荐等方面。

例如，假设有一个网站获得了大量的用户评价数据，可以将这些数据构成一个评价矩阵，然后对该矩阵进行SVD分解，从而得到用户和产品的特征向量。

矩阵的奇异值分解高等代数知识点详解矩阵的奇异值分解（Singular Value Decomposition，简称SVD）是一种重要的矩阵分解方法，它在高等代数中具有广泛应用。

本文将详细介绍矩阵的奇异值分解原理、性质以及在实际问题中的应用。

一、奇异值分解的原理奇异值分解是将一个复杂的矩阵分解为三个简单矩阵的乘积，其基本原理可以用以下公式表示：A = UΣV^T在公式中，A是一个m×n的实数矩阵，U是一个m×m的正交矩阵，Σ是一个m×n的对角矩阵，V^T是一个n×n的正交矩阵，其中^T表示转置。

二、奇异值分解的性质1.奇异值在奇异值分解中，Σ是一个对角矩阵，对角线上的元素称为奇异值。

奇异值是非负实数，按照大小排列，通常用σ1 ≥ σ2 ≥ ... ≥ σr来表示。

其中r是矩阵A的秩。

2.奇异向量在奇异值分解中，U的列向量称为左奇异向量，V的列向量称为右奇异向量。

左奇异向量和右奇异向量都是单位向量，且对应不同的奇异值。

3.特征值与奇异值对于一个方阵A，奇异值与它的特征值有一定的联系。

若A是一个n×n的方阵，那么它的非零奇异值是A^T × A的非零特征值的平方根。

三、奇异值分解的应用奇异值分解在数据降维、图像压缩、推荐系统等领域具有广泛的应用。

1.数据降维在高维数据分析中，经常需要将高维数据转化为低维，以便于可视化和分析。

奇异值分解可以对数据矩阵进行降维，得到矩阵的主要特征。

通过保留较大的奇异值和对应的奇异向量，可以实现对数据的有效降维。

2.图像压缩奇异值分解可以对图像进行压缩，将原始图像表示为几个主要特征的叠加。

通过保留较大的奇异值和对应的奇异向量，可以在减小图像存储空间的同时，尽可能地保留图像的主要信息。

3.推荐系统在推荐系统中，奇异值分解可以对用户-物品评分矩阵进行分解，得到用户和物品的隐含特征。

通过计算用户-物品评分的近似矩阵，可以预测用户对未评分物品的评分，从而实现个性化推荐。

奇异值分解时间复杂度计算奇异值分解（Singular Value Decomposition, SVD）是一种常用的矩阵分解方法，广泛应用于数据降维、图像压缩、推荐系统等领域。

SVD能够将一个矩阵分解为三个矩阵的乘积，从而提取出矩阵的主要特征和结构。

本文将从奇异值分解的原理、计算方法和时间复杂度等方面进行介绍。

我们来了解一下奇异值分解的原理。

给定一个m×n的矩阵A，其奇异值分解可以表示为A=UΣVᵀ，其中U和V是正交矩阵，Σ是一个对角矩阵。

U的列向量称为左奇异向量，V的列向量称为右奇异向量，Σ的对角线上的元素称为奇异值。

奇异值分解的计算方法有多种，其中最常用的是基于Jacobi迭代的方法。

该方法首先将矩阵A转化为对称矩阵AᵀA，然后通过迭代的方式逐步求解出AᵀA的特征值和对应的特征向量，再根据特征值和特征向量计算出奇异值和奇异向量。

接下来，我们来分析奇异值分解的时间复杂度。

假设矩阵A的大小为m×n，其中m>n（即A是一个长方形矩阵）。

那么奇异值分解的计算过程可以分为三个步骤：计算AᵀA的特征值和特征向量、计算奇异值和奇异向量、计算U和V。

计算AᵀA的特征值和特征向量。

由于AᵀA是一个n×n的对称矩阵，其计算特征值和特征向量的时间复杂度为O(n³)。

这个步骤的计算量主要取决于矩阵A的列数n。

然后，计算奇异值和奇异向量。

根据特征值和特征向量的关系，我们可以通过AᵀA的特征值和特征向量来计算出A的奇异值和奇异向量。

由于AᵀA是一个n×n的对称矩阵，所以计算奇异值和奇异向量的时间复杂度同样为O(n³)。

计算U和V。

计算U的时间复杂度为O(mn²)，计算V的时间复杂度为O(n²)。

这两个步骤的计算量主要取决于矩阵A的行数m和列数n。

奇异值分解的时间复杂度主要取决于矩阵A的大小。

当矩阵A的行数m和列数n都较大时，奇异值分解的计算时间将会非常耗时。

第1部分方法介绍奇异值分解（SVD ）定理：设m n A R ⨯∈，则存在正交矩阵m m V R ⨯∈和n n U R ⨯∈，使得TO A V U O O ∑⎡⎤=⎢⎥⎣⎦其中12(,,,)r diag σσσ∑= ，而且120r σσσ≥≥≥> ，(1,2,,)i i r σ= 称为A 的奇异值，V 的第i 列称为A 的左奇异向量，U 的第i 列称为A 的右奇异向量。

注：不失一般性，可以假设m n ≥，（对于m n <的情况，可以先对A 转置，然后进行SVD 分解，最后对所得的SVD 分解式进行转置，就可以得到原来的SVD 分解式）方法1：传统的SVD 算法主要思想：设()m n A R m n ⨯∈≥，先将A 二对角化，即构造正交矩阵1U 和1V 使得110T B n U AV m n⎡⎤=⎢⎥-⎣⎦其中1200n n B δγγδ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦然后，对三角矩阵T T B B =进行带Wilkinson 位移的对称QR 迭代得到:T B P BQ =。

当某个0i γ=时，B 具有形状12B O B O B ⎡⎤=⎢⎥⎣⎦，此时可以将B 的奇异值问题分解为两个低阶二对角阵的奇异值分解问题；而当某个0i δ=时，可以适当选取'Given s 变换，使得第i 行元素全为零的二对角阵，因此，此时也可以将B 约化为两个低阶二对角阵的奇异值分解问题。

在实际计算时，当i B δε∞≤或者()1j j j γεδδ-≤+（这里ε是一个略大于机器精度的正数）时，就将i δ或者i γ视作零，就可以将B 分解为两个低阶二对角阵的奇异值分解问题。

主要步骤：（1）输入()m n A R m n ⨯∈≥及允许误差ε（2）计算Householder 变换1,,,n P P ⋅⋅⋅，12,,n H H -⋅⋅⋅，使得112()()0Tn n B nP P A H H m n -⎡⎤⋅⋅⋅⋅⋅⋅=⎢⎥-⎣⎦其中1200n n B δγγδ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦ 12:n U PP P =⋅⋅⋅，122:.n V H H H -=⋅⋅⋅ （3）收敛性检验：（i ）将所有满足()1j j j γεδδ-≤+的j γ置零；（ii ）如果0,2,,j j n γ== ，则输出有关信息结束；否则，1:0γ=，确定正整数p q <，使得10p q n γγγ+==⋅⋅⋅==，0j γ≠，p j q <≤；（iii ）如果存在i 满足1p i q ≤≤-使得i B δε∞≤，则:0i δ=，1:i x γ+=，1:i y δ+=，1:0i γ+=，:1l =，转步（iv ）；否则转步（4） （iv ）确定cos ,sin c s θθ==和σ使0c s x s c y σ⎡⎤⎡⎤⎡⎤=⎢⎥⎢⎥⎢⎥-⎣⎦⎣⎦⎣⎦这也相应于0Tc s y s c x σ⎡⎤⎡⎤⎡⎤=⎢⎥⎢⎥⎢⎥-⎣⎦⎣⎦⎣⎦所以可以直接调用'Given s 变换算法得到:i l δσ+=，:(,,)T U UG i i l θ=+这相当于(1:;,)(1:;,)(1:;,)Tc s c s U n i i l U n i i l U n i i l s c s c -⎡⎤⎡⎤+=+=+⎢⎥⎢⎥-⎣⎦⎣⎦（v ）如果l q i <-，则1:i l x s γ++=，11:i l i l c γγ++++=，1:i l y δ++=，:1l l =+转步（iv ），否则转步（i ）（4）构造正交阵P 和Q ，使12=T P B Q B 仍为上双对角阵，其中112100pp p p q q B δγδγγδ+++⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦， 得121:=T B B P B Q =，:(,,)p n p q U Udiag I P I --=，:(,,)p n p q V Vdiag I Q I --=然后转步（3）。

奇异值分解定理：设，则存在m 阶正交矩阵U 和n 阶正交矩阵V ，使得，其中为矩阵A 的全部非零奇异值，满足0r 21>≥≥⋯≥≥，σσσ，前几个值比较大，它们包含了矩阵A 的大部分信息。

U 的列向量（左奇异向量）是的特征向量，V 的列向量（右奇异向量）是的特征向量。

奇异值分解的性质：1. 奇异值的稳定性定理1：假设, A 和 B 的SVD 分别为和,其中p =min ( m , n) ,则有。

定理1表明当矩阵A 有微小扰动时,扰动前后矩阵奇异值的变化不会大于扰动矩阵的-2范数。

这个性质表明,对于存在灰度变化、噪声干扰等情况的图像,通过SVD 后,图像的特征向量不会出现大的变化。

这一性质放宽了对图像预处理的要求, 并使匹配结果的准确性得到了保证。

2. 奇异值的比例不变性因此，为了消除幅度大小对特征提取的影响，所进行的归一化处理不会从本质改变奇异值的相对大小。

3. 奇异值的旋转不变性图像奇异值特征向量不但具有正交变换、旋转、位移、镜像映射等代数和几何上的不变性,而且具有良好的稳定性和抗噪性，广泛应用于模式识别与图像分析中。

对图像进行奇异值分解的目的是：得到唯一、稳定的特征描述；降低特征空间的维数；提高抵抗干扰和噪声的能力。

欧氏距离（Euclidean distance ）欧氏距离定义：欧氏距离（Euclidean distance）是一个通常采用的距离定义，它是在m维空间中两个点之间的真实距离。

欧氏距离看作信号的相似程度，距离越近就越相似。

设x，y是M× N 维的两幅图像，那么其在图像空间中可以表示为：式中为图像x，y的第（k，l）个像素点。

则图像的欧氏距离定义为根据上述定义，一幅M×N 的图像可以看作M×N 维欧氏空间中的一点，每个坐标对应于一个像素的灰度值。

特征匹配算法采用遍历搜索法，计算特征向量两两间的欧氏距离，确定向量之间的最近邻距离（MD）第二近邻距离（SMD），并计算二者的比值：MD/ SMD。

0 0
(2)
A

0 2
1 0
1 0
解： （1）由于
5
AAH 0
0 0
0 0
显然 AAH的特征值
为5，0，0，所以
0 0 0 A的奇异值为 5
（2）由于
AAH的H 特征值为2，4，所以 的奇A异
值为 2 , 。2
定义2:设 A, B C m,若n
1 0 0
1 0 ,2 1 ,3 0
0 0 1
由这三个标准正交特征向量组成矩阵 ，所U以有
1 0 0 UV 0 1 0
0 0 1
1 0
令
U1 0 1
0 0
1
V1

AHU1 H
O
从而：A H U 2

O
U
H 2
A

O
所以
U
H 2
AV1

O
,
U
H 2
AV2

O
又因为 V1 AHU1 H
所以，V1 H AHU，1 得出
UH 1
A

V1H
所以
U1H AV2 O
UH
AV

O
O O
A

U

O
O O
V
H
1, 求出 AAH , AH 的A 全部特征值 ,则i i i
(1)

0
1
0

1 0 1
(2)
0 2
1 0
1 0
二,矩阵的极分解
定理1:设与正A定的CHn，n-那矩n 么阵必存在酉矩阵 H1, H2
使得: A H1U UH2

我所理解的奇异值分解我所理解的奇异值分解SVD1、奇异值与奇异值分解定理奇异值定理：设m n A C ?∈，r=rank(A)，则⼀定存在m 阶⾣矩阵U 和n 阶⾣矩阵V 和对⾓矩阵1212(,,,)(1,2,,)r r i diag i r σσσσσσσ∑=≥≥≥=，且，⽽，使得H A U V =∑，称为A 的奇异值分解。

复数域内的奇异值：设(0)m n H r A C r A A ?∈>，的特征值为1210r r n λλλλλ+≥≥≥>===则称1,2,,)i i n σ==为A 的正奇异值；当A 为零矩阵时，它的奇异值都是零。

易见，矩阵A 的奇异值的个数等于A 的列数，A 的⾮零奇异值的个数等于rank(A)。

2、奇异值分解的理解奇异值σ跟特征值类似，在矩阵Σ中也是从⼤到⼩排列，⽽且σ的减少特别的快，在很多情况下，前10%甚⾄1%的奇异值的和就占了全部的奇异值之和的99%以上了。

也就是说，我们也可以⽤前r ⼤的奇异值来近似描述矩阵。

r r r T r r r T v u v u v u V U V U A σσσ+++=∑=∑= 222111即A 可表⽰为r 个秩为⼀的举证的和，这是A 得奇异值分解的紧凑格式。

3、奇异值分解特征奇异值分解的第⼀个特征是可以降维。

A 表⽰ n 个 m 维向量 ,通过奇异值分解可表⽰成 m + n 个 r 维向量 ,若A 的秩 r 远远⼩于m 和 n ,则通过奇异值分解可以⼤⼤降低 A 的维数。

可以计算出 ,当 r奇异值分解的第⼆个特征是奇异值对矩阵的扰动不敏感 ,⽽特征值对矩阵的扰动敏感。

在数学上可以证明 ,奇异值的变化不会超过相应矩阵的变化 ,即对任何相同阶数的实矩阵A 、B ,按从⼤到⼩排列的奇异值i σ和i ω,有2B A i i i -≤-∑ωσ.奇异值的第三个特征是奇异值的旋转不变性。

即若 P 是正交阵 ,PA 的奇异值与A 的奇异值相同。

同理如果将 V 划分为以下的形式 V = (V1 , V2 ) 其中 V1 为 n × r 的矩阵，则 V1 的列向量构成矩阵 A 的行空间的正交向量
⊥ 基。且 RA = V1V1T 为投影到矩阵 A 的行空间上的正交投影算子；而 RA = V2V2T 则是到矩阵 A 行空间的正交补空间上的投影。 (3) 最小二乘法问题(LS 问题)
i =1 r
其中 ( A) ， ( A) 分别指得是 A 的零空间和值域。 为了方便，我们采用如下表示奇异值的记号： σ i ( A)＝A 的第 i 大奇异值；
σ max ( A)＝A 的最大奇异值； σ min ( A)＝A 的最小奇异值。
现在来考察矩阵奇异值的几何意义[1,2]，不妨设 m = n ，此时有 En =∈ y Cn : y = Ax, x ∈ C n , x 2 = 1
SVD（奇异值分解）算法及其评估 本文第一部分对 SVD 进行了简单的介绍，给出了定义和奇异值分解定理；第二 部分简要地列举了 SVD 的应用；第三部分则构造和分析了各种求解 SVD 的算法， 特别对传统 QR 迭代算法和零位移 QR 迭代算法进行了详细完整的分析；第四部分 给出了复矩阵时的处理办法；第五部分是对各种算法的一个简要的总结。 一、 SVD 简介
首先来对 SVD 算法的发展来做简单的回顾[11,12]：关于 SVD 算法的研究最早 可以追溯到 1873 年 Beltrami 所做的工作， 这中间在理论方面进行了大量的工作， 这 个历史过程可以参考 Stewart 的文献[8]。 但是直到 1965 年 Golub 和 Kahan 才在 SVD 的数值计算领域取得突破性进展[9]，并且于 1969 给出了比较稳定的算法[10]（以下 简称传统 QR 迭代算法） ，这也是后来在 LINPACK 中所采用的方法[3]。它的中心思 想是用正交变换将原矩阵化为双对角线矩阵，然后再对双对角线矩阵迭代进行 QR 分解。 六十年代一份没有出版的技术报告中，Kahan 证明了双对角线矩阵的奇异值可 以精确地计算，具有和原矩阵元素的相对的精确度；进一步，1990 年 Demmel 和 Kahan 给出了一种零位移的 QR 算法(zero-shift QR algorithm)，这种算法计算双对角 矩阵的奇异值具有很高的相对精度[13]，并且由此得到的奇异向量也具有很高的精 度[14]。 Fernando 和 Parlett 在 1994 年将 qd 算法应用到奇异值的计算上，从而得到了一 种全新的比 zero-shift QR algorithm 更加精确和快速的计算奇异值的算法[15,16]。 而 Demmel 和 Veselic 在文献[17]中则说明了用 Jacobi 方法与其它方法相比计算 所得到的奇异值和奇异向量具有更高的精度，可惜 Jacobi 算法比 DK 算法速度要慢 的多；在文献[18]中对 Jacobi 方法进行了改进使得其在速度上几乎和 DK 算法相当。 和 Strassen 算法类似，SVD 问题也有快速的分而制之算法，在文献[19,20]对其 有详细的介绍， 由此得到的算法在总计算量上比现有的 LAPACK 软件包中所采用的 方法要少的多。 在文献[21,22]中给出的 bisection 算法也可以对双对角线矩阵计算得到具有相对 精度的全部奇异值。 以下就开始对各种算法原理进行详细说明，并分析它们的计算量，计算的精确 度，以及所占得内存。