特征值分解，奇异值分解svd_特征值分解和奇异值分解

特征值分解：

特征值分解（Eigen decomposition），又称谱分解（Spectral decomposition）是将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法。需要注意只有方阵才可以施以特征值分解。

N 维非零向量 v 是 N×N 的矩阵 A 的特征向量，当且仅当下式成立：

其中 λ 为一标量，称为 v 对应的特征值。也称 v 为特征值 λ 对应的特征向量​​​​​​​。也即特征向量被施以线性变换 A 只会使向量伸长或缩短而其方向不被改变。因此这里只考虑单位特征向量。

 

假设矩阵A有n个特征无关的特征向量{V1,V 2, …V n},对应的特征值为{λ1，λ2，…λn}。

我们将特征向量连接成一个矩阵，使得每一列是一个特征向量:V={V1, V2…V n}。同

样的，我们将特征值连接成一个向量λ=[λ1，λ2，…λn]。因此我们可以得到下式:

AV = Vdiag(λ)

其中diag(λ)是向量入对应的对角矩阵。

令

此时，矩阵A便可以分解为特征值和特征向量的乘积，称为特征分解。

 

一般我们会把V的这n个特征向量标准化，即满足||vi||2=1或者说viTvi=1，此时V的n个特征向量为标准正交基，满足viTvi=I，即viT=vi-1, 也就是说V为酉矩阵。

这样我们的特征分解表达式可以写成

 

Eigen decomposition举例：

已知

求A的特征值及其对应的特征向量

当λ1=16.1168时，

当λ2=-1.1168时，

当λ3=0时，

最终得到，特征值为

特征向量为，

程序实现：

Python:a*v = v*d

a= np.array([[1,2,3],[4,5,6],[7,8,9]])
d,v=np.linalg.eig(a)

Matlab：a*v = v*d

a=[[1,2,3];[4,5,6];[7,8,9]]
[v,d]=eig(a)

奇异值分解svd

奇异值分解（Singular Value Decomposition）是线性代数中一种重要的矩阵分解，奇异值分解则是特征分解在任意矩阵上的推广。在信号统计、统计学等领域有重要应用。svd分解不要求矩阵必须是方阵。

 

假设M是一个m×n阶矩阵，其中的元素全部属于域 K，也就是实数域或复数域。如此则存在一个分解使得

其中U是m×m阶酉矩阵；Σ是半正定m×n阶对角矩阵；而V*，即V的共轭转置，是n×n阶酉矩阵​​​​​​​。这样的分解就称作M的奇异值分解。Σ对角线上的元素Σi，其中Σi即为M的奇异值。

常见的做法是为了奇异值由大而小排列。如此Σ便能由M唯一确定了。（虽然U和V仍然不能确定）

那么我们如何求出SVD分解后的U,Σ,V这三个矩阵呢？

如果我们将M的转置和M做矩阵乘法，那么会得到n×n的一个方阵MTM。既然MTM是方阵，那么我们就可以进行特征值分解，得到的特征值和特征向量满足下式：

这样我们就可以得到矩阵MTM的n个特征值和对应的n个特征向量v了。将MTM的所有特征向量张成一个n×n的矩阵V，就是我们SVD公式里面的V矩阵了。一般我们将V中的每个特征向量叫做M的右奇异向量。

如果我们将M和M的转置做矩阵乘法，那么会得到m×m的一个方阵MMT。既然MMT是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：

这样我们就可以得到矩阵MMT的m个特征值和对应的m个特征向量u了。将MMT的所有特征向量张成一个m×m的矩阵U，就是我们SVD公式里面的U矩阵了。一般我们将U中的每个特征向量叫做M的左奇异向量。

U和V我们都求出来了，现在就剩下奇异值矩阵Σ没有求出了。由于Σ除了对角线上是奇异值其他位置都是0，那我们只需要求出每个奇异值σ就可以了。

我们注意到:

这样我们可以求出我们的每个奇异值，进而求出奇异值矩阵Σ。

上面还有一个问题没有讲，就是我们说MTM的特征向量组成的就是我们SVD中的V矩阵，而MMT的特征向量组成的就是我们SVD中的U矩阵，这有什么根据吗？这个其实很容易证明，我们以V矩阵的证明为例。

上式证明使用了:

可以看出MTM的特征向量组成的的确就是我们SVD中的V矩阵。类似的方法可以得到MMT的特征向量组成的就是我们SVD中的U矩阵。

进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方，也就是说特征值和奇异值满足如下关系：

σi=sqrt(λi)

这样也就是说，我们可以不用σi=Mvi/ui来计算奇异值，也可以通过求出MTM的特征值取平方根来求奇异值。

svd性质：

对于奇异值，它跟我们特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列，而且奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说，我们也可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说：

其中k要比n小很多，也就是一个大的矩阵A可以用三个小的矩阵Um*k，Σk*k，V*k*n来表示。如下图所示，现在我们的矩阵A只需要灰色的部分的三个小矩阵就可以近似描述了。

由于这个重要的性质，SVD可以用于PCA降维，来做数据压缩和去噪。也可以用于推荐算法，将用户和喜好对应的矩阵做特征分解，进而得到隐含的用户需求来做推荐。同时也可以用于NLP中的算法，比如潜在语义索引（LSI）。

svd举例：

首先定义M，

利用Mvi=σiui，i=1,i=1,2求奇异值：

当然，我们也可以用σi=sqrt(λi)直接求出奇异值为sqrt(3)和1。

最终得到M的奇异值分解为：

程序实现：

Python

a=np.array([[0,1],[1,1],[1,0]])
u,s,v=np.linalg.svd(a)

Matlab：

a=[[0,1];[1,1];[1,0]]
[u,s,v]=svd(a)