奇异值分解的原理与使用

奇异值分解的原理与使用

奇异值分解的原理

特征值和特征向量

特征值和特征向量的定义如下:
$$
Ax = \lambda x
\tag{1}
$$
其中,$\lambda$是一个标量,$x$是一个向量,$\lambda$称作矩阵$A$的特征值,$x$是其对应的特征向量。

求得所有特征值和特征向量后,我们就可以对矩阵A进行特征分解。具体如下:
$$
A = W \Sigma W^{-1}
\tag{2}
$$
其中,$W$是由$A$的所有特征向量组成的$n\times n$维矩阵。$\Sigma$是以$A$的所有特征值$\lambda_1,\lambda_2,\dots, \lambda_n$为对角线的对角矩阵。我们一般会把$W$的这$n$个特征向量标准化,即满足$||w_i|| = 1$或者$w_i^T \cdot w_i = w_i^T w_i=1$,此时,$W$的$n$个向量为标准正交基。

故:
$$
W^{-1} = W^T
\tag{3}
$$
这样我们的特征分解表达式可以写成
$$
A = W \Sigma W^T
\tag{4}
$$

$SVD$的定义

$SVD$也是对矩阵进行分解,但是和特征分解不同,$SVD$并不要求要分解的矩阵为方阵。假设我们的矩阵A是一个$𝑚×𝑛$的矩阵,那么我们定义矩阵$A$的$SVD$为:
$$
A = U\Sigma V^T
\tag{5}
$$
其中,$U$的形状为:$m \times m$,$\Sigma$的形状为$m \times n$,是一个对角矩阵,对角线上的每一个值都是$A$的一个奇异值,$V$的形状为$n \times n$,$A$的形状与$\Sigma$的形状一致。在此处,$U$和$V^T$都是酉矩阵,即:
$$
U^TU=I \\ V^TV=I
\tag{6}
$$

$SVD$的求法

$$
\begin{align}
A & = U\Sigma V^T \\
\Rightarrow AV & = U\Sigma V^TV \\
\Rightarrow AV & =U\Sigma \\
\Rightarrow Av_i & = \sigma_i u_i \\
\Rightarrow \sigma_i & = Av_i / u_i
\end{align}
\tag{7}
$$

这样我们可以求出我们的每个奇异值,进而求出奇异值矩阵$\Sigma$。我们说$A^TA$的特征向量组成的就是我们$SVD$中的$V$矩阵,而$AA^T$的特征向量组成的就是我们$SVD$中的$U$矩阵。
$$
U^TU=I, \Sigma^T\Sigma=\Sigma^2
\tag{8}
$$

$$
\begin{align}
A & =U\Sigma V^T \\
\Rightarrow A^T & = V\Sigma^T U^T \\
\Rightarrow A^TA & = V\Sigma^T U^TU\Sigma V^T \\
&= V\Sigma^2V^T
\end{align}
\tag{9}
$$
可以看出$A^T A$的特征向量组成的的确就是我们$SVD$中的V矩阵。类似的方法可以得到$AA^T$的特征向量组成的就是我们$SVD$中的$U$矩阵。

进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方,也就是说特征值和奇异值满足如下关系:
$$
\sigma_i = \sqrt{\lambda_i}
\tag{10}
$$
这样也就是说,我们可以不用$\sigma_i = \frac{Av_i}{u_i}$来计算奇异值,也可以通过求出$A^T A$的特征值取平方根来求奇异值。

$SVD$的使用

$SVD$的使用主要是用在两个方面,一方面是主成分分析。

主成分分析

$$
A_{m \times n} = U_{m \times m}\Sigma_{m \times n} V^T_{n \times n} \approx U_{m \times k}\Sigma_{k \times k} V^T_{k \times n}
\tag{11}
$$

上式的主要意义在于,使用奇异值去近似的表达一个矩阵,因为$\Sigma$中的奇异值是根据大小排列的,如果舍去较小的奇异值,在将只乘回去,得到的结果与原矩阵十分近似。较大的奇异值组合就变成了原矩阵的主要成分。

降维

也是根据$(11)$式,我们将较小的一部分奇异值舍去的话,在进行矩阵运算的时候可以达到降维的作用。

$SVD$在图像处理中的应用。

先上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from PIL import Image
import numpy as np
from numpy import linalg as la


def processImg(img, gate):
a = np.asarray(img)
u, sigma, vt = la.svd(a)
s = np.zeros([u.shape[0], vt.shape[1]])
c = 0
gate = (gate / 100) * (u.shape[0] if u.shape[0] < vt.shape[1] else vt.shape[1])
for i in sigma:
s[c][c] = i if c < gate else 0
c = c + 1
return Image.fromarray(np.dot(np.dot(u, s), vt)).convert('L')


if __name__ == '__main__':
for image in range(8):
img = Image.open("source_img/img.%s.jpg" % image)
r, g, b = img.split()
for i in [1, 5, 10, 25, 50, 70, 90]:
print("processing 【image%s】 %s%s ..." % (image, i, '%'))
nr = processImg(r, i)
ng = processImg(g, i)
nb = processImg(b, i)
img = Image.merge('RGB', [nr, ng, nb])
img.save('imgs/img.%s.%s.png' % (image, i), "png")
print("\t【image%s】Done" % image)
print("done...")

完成后的图片

以下图片均来自网络,若有侵权请联系删除: cyrusky#borgor.cn

结论

我们可以得出以下结论:

保留奇异值的百分比结论
1%细节缺失,无法观察具体图像
5%能够肉眼分辨图像内容,但是噪点特别多
10%有少量噪点,细节可见
>=25%无肉眼可见噪点,细节清晰可见

由具体实验可以观察到,照片中含有的细节较多,所以,在保留相同百分比的奇异值的情况下,较漫画、卡通、手绘等图片的失真率高。

评论

Agile Angularjs Animation Application Artificial Intelligence BP Babel Bokeh Book C4.5 CART CD CLI CSS CentOS Cinder Clipboardjs Concept Continuous Delivery DeepLearning Department DevOps Develop Development Directive Distribution Django Document ES5 ES6 Echarts Engine Entropy Filter Front End Gallery Git Gradient descent Hexo Horizon ID3.5 Icarus JavaScript Javascript KVM LaTeX LibreOffice Linux MNIST Machine Learning Matrix MiddleWare Module Native Network Nginx NodeJS OOP OpenStack OpenStackApi Operations Oprations PDF Pipline Probability Python React Relational algebra Restful Route SVD SVM Scalar Sigmoid Team Tempest Tensor TensorFlow Testing Time TimeMachine Tips Vector Vmware Vue Vuex WSGI Web Word Cut aliyun auth babel certbot decision tree git homebrew jwt keystone loader mathematics migrate openstack pdf2html pm2 singular value decomposition vue-router vue-ssr webpack 事件 事件代理 事件冒泡 事件捕获 低通滤波器 入门 全局变量 全局对象 全栈 公式 决策树 函数 分类器 加速 匹配滤波边缘检测 卷积 卷积核 原型链 双向绑定 反向传播 发布 变量类型 官方示例 对偶形式 对象 平移和查分边缘检测 感知机模型 拉格朗日乘子法 推导 提交阶段 数据绑定 最大似然估计 最小二乘估计 最小二乘法 朴素贝叶斯 机器学习 条件概率 梯度下降 梯度方向边缘检测 概念 概率 求导 流程 源码阅读 生命周期 矩阵 神经网络 私有对象 线性回归 联合概率 识别 贝叶斯判定准则 边缘检测 边际概率 闭包 间隔 高斯分布 高通滤波器
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×