特征值分解与奇异值分解原理与计算_特征值分解算法计算量

（一）特征值

如果一个非零向量v是方阵A的特征向量，将一定可以表示成下面形式，而λ是特征向量v对应的特征值：

 

特征值分解是将一个矩阵分解成下面的形式：

 

Q代表这个矩阵A组成的特征向量，Σ是一个对角阵，每一个对角线上的值代表特征向量对应的特征值。

求解过程例题：

 

 

 

方阵的特征值表示什么含义呢，我们通过一组向量图表示。初始状态下，i（红色）和j（蓝色）表示二维坐标平面下的两个单位向量，v是空间上任意一条向量（绿色）

 

用方阵左乘向量，即可得到一个新的向量

 

接下来，在二维空间上手动移动v，会存在两个时刻即v与Av共线，差了一个λ倍。

 

那么说这个时候的v为方阵A的特征向量，特征值大小为λ。特征向量之间组成了方阵的特征空间。

 

特征值有如下性质：

设n阶矩阵A=(aij) 的特征值为λ1,λ2,...λn
（1）λ1+λ2+...+λn = a11+ a22+…+ann，trail(A)=特征值的和。
（2）λ1λ2… λn =|A|，特征值的乘积=A的行列式

若λ是方阵A的特征值
（1）λ^2是A^2的特征值
（2）A可逆时，λ^(-1)是A^(-1)的特征值
（3）kλ是kA的特征值，k∈R。
 

设方阵A的m个特征值λ1,λ2 ,...,λm，与之对应的特征向量是p1,p2,...,pm，若λ1,λ2 ,...,λm各不相等，则p1,p2 ,...,pm线性无关。（不同特征值对应的特征向量线性无关），实对称矩阵不同特征值的特征向量相互正交。

（二）特征值分解

 

 

如果M是对称矩阵，则相当于对坐标轴进行伸缩，若M不是对称矩阵，则相当于在平面上对一个轴进行拉伸变换，如何描述这个变换则需要明确变换的方向（特征向量代表的方向）

 

分解得到的Σ矩阵是一个对角阵，若Σ里面的特征值是由大到小排列的，这些特征值所对应的特征向量就是描述这个矩阵变化方向（从主要变化到次要变化排列）

当矩阵是高维的情况下，那么这个矩阵A就是高维空间下的一个线性变换，这个变换也同样有很多的变换方向，通过特征值分解得到的前N个特征向量，对应了矩阵最主要的N个变化方向。我们利用这前N个变化方向，就可以近似这个矩阵（变换）。

也就是说：提取这个矩阵最重要的特征。

特征值分解的局限：变换的矩阵必须是方阵！！

（三）奇异值与奇异值分解

在现实的世界中，遇到的大部分矩阵都不是方阵，比如说有N个学生，每个学生有M科成绩；有N个用户，每个用户购买了M件商品，这样形成的一个N * M的长方形矩阵。

怎样描述这样普通的矩阵的重要特征？

可以使用奇异值分解来解决

A是一个N * M的矩阵，那么得到的U是一个N * N的方阵（里面的向量是正交的，称为左奇异向量），Σ是一个N * M的对角矩阵（除了对角线的元素都是0，对角线上的元素称为奇异值），VT是一个N * N的矩阵（里面的向量也是正交的，称为右奇异向量）

 

 

 

右奇异向量求解：矩阵A左乘转置转置AT，会得到一个方阵（m*m），用这个方阵求特征值与特征向量，就能得到V与对应的特征值。

 

根据?求出的特征值λ，计算奇异值σ，以及左奇异向量U。

 

求解A的奇异值

 

 

 

 

最终结果：

 

（四）奇异值numpy计算

用numpy中自带的np.linalg.svd(matrix)可以计算

 

奇异值σ与特征值类似，矩阵Σ中也是从大到小排列，而且σ的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前r大的奇异值来近似描述矩阵，这里定义一下部分奇异值分解，这里r是一个远小于m、n的数。

右边的三个矩阵相乘的结果将会是一个接近于A的矩阵。而这三个矩阵的“面积”之和要远小于原始的矩阵A，可以压缩空间来表示原矩阵A，只存储三个矩阵U、Σ、V即可。

 

（五）奇异值进行图片压缩

我们利用SVD分解进行图片压缩，其实主要是保留系数矩阵中较大的值，舍掉较小的值，从而达到压缩图像的作用。

在Python中，SVD分解非常简单，可利用np.linalg.svd()函数，比如u,sigma,v=np.linalg.svd(A)，则u，v分别返回A的左右奇异向量，而sigma返回的并不是系数矩阵，而是一个奇异值从大到小排列的一个向量。然后对于图像而言，其实就是RGB三个图层上矩阵的叠加，每个元素的值 为0到255之间的整数，在Python中读取图像可以通过plt.imread()函数，这样直接得到了一个a*b*3的矩阵，然后对三个图层分别处理就行。

现在来整理一下思路：

1 读取图片，分解成RGB三个矩阵。

2 对三个矩阵分别进行SVD分解，得到对应的奇异值和奇异向量。

3 按照一定标准进行奇异值的筛选（整体数量的一定百分比，或者奇异值和的一定百分比）

4 恢复矩阵，并将RGB三个矩阵叠加起来。

5 保存图像。
 

代码如下：

import numpy as np
import matplotlib.pyplot as plt
 
def svd_image(filename,percent):
    input = plt.imread(filename)
    R_origin = np.array(input[:,:,0])
    G_origin = np.array(input[:,:,1])
    B_origin = np.array(input[:,:,2])
    u0,sigma0,v0 = np.linalg.svd(R_origin)
    u1,sigma1,v1 = np.linalg.svd(G_origin)
    u2,sigma2,v2 = np.linalg.svd(B_origin)
    num0 = int(percent*len(sigma0)+1)
    num1 = int(percent*len(sigma1)+1)
    num2 = int(percent*len(sigma2)+1)
    R_transfer = np.zeros(R_origin.shape)
    G_transfer = np.zeros(G_origin.shape)
    B_transfer = np.zeros(B_origin.shape)
    for i in range(num0):
        R_transfer += sigma0[i] * np.dot(u0[:,i].reshape(-1,1),v0[i,:].reshape(1,-1))
    for i in range(num1):
        G_transfer += sigma1[i] * np.dot(u1[:,i].reshape(-1,1),v1[i,:].reshape(1,-1))
    for i in range(num2):
        B_transfer += sigma2[i] * np.dot(u2[:, i].reshape(-1, 1),v2[i,:].reshape(1,-1))
    final = np.stack((R_transfer,G_transfer,B_transfer),2)
    final[final>255]= 255
    final[final<0] = 0
    final = np.rint(final).astype('uint8')
    return final
 
if __name__ == "__main__":
    filename = 'test.jpg'
    for p in np.arange(.1, 1, .1):
        after = svd_image(filename, p)
        plt.imsave(str(p) + '_0.jpg', after)

那么我贴一张取奇异值整体数量的0.1 ,0.2,0.5 ,0.9来看吧

0.1:还是比较模糊的

0.2:

0.5:

0.9:

可以看出0.2的时候基本已经还原图片了，0.5的时候与0.9基本已经相同啦！这样我们就起到了压缩图片的作用！