SVD(奇异值分解)

1.特征值分解（EVD）

实对称矩阵

在理角奇异值分解之前，需要先回顾一下特征值分解，如果矩阵$A$是一个$m \times m$的实对称矩阵（即$A = A^T$），那么它可以被分解成如下的形式

$A=Q\Sigma Q^T = Q \begin{bmatrix} \lambda_1& \cdots&\cdots&\cdots \\ \cdots &\lambda_2&\cdots&\cdots \\ \cdots &\cdots&\ddots&\cdots \\ \cdots & \cdots &\cdots&\lambda_m \end{bmatrix} Q^T \tag{1-1}$

其中$Q$为标准正交阵，即 Q^T有$QQ^T=I$，$\Sigma$为对角矩阵，且上面的矩阵的维度均为$m\times m$。$\lambda_i$称为特征值，$q_i$是$Q$（特征矩阵）中的列向量，称为特征向量。

$I$ 在这里表示单位阵，有时候也用$E$表示单位阵。

一般矩阵

上面的特征值分解，对矩阵有着较高的要求，它需要被分解的矩阵𝐴为实对称矩阵，但是现实中，我们所遇到的问题一般不是实对称矩阵。那么当我们碰到一般性的矩阵，即有一个$m\times n$的矩阵$A$，它是否能被分解成上面的式（1-1）的形式呢？当然是可以的，这就是我们下面要讨论的内容。

2.奇异值分解（SVD）

2.1 奇异值分解定义

有一个$m \times n$的实数矩阵$A$，我们想要把它分解成如下的形式

$A=U \Sigma V^T \tag{2-1}$

其中$U$和$V$均为单位正交阵，即有$UU^T=I$和 $VV^T=I$ ，$U$称为左奇异矩阵，$V$称为右奇异矩阵，$\Sigma$仅在主对角线上有值，我们称它为奇异值，其它元素均为0。上面矩阵的维度分别为$U\in R^{m\times m}$, $\Sigma \in R^{m\times n}$, $V\in R^{n \times m}$。

一般地$\Sigma$有如下形式

$\Sigma=\begin{bmatrix} \sigma_1&0&0&0&0 \\ 0&\sigma_2&0&0&0 \\ 0&0&\ddots&0&0 \\ 0&0&0&\ddots&0 \end{bmatrix}_{m\times n}$

图1-1 奇异值分解

对于奇异值分解，我们可以利用上面的图形象表示，图中方块的颜色表示值的大小，颜色越浅，值越大。对于奇异值矩阵$\Sigma$，只有其主对角线有奇异值，其余均为0。

2.2 奇异值求解

正常求上面的$U,V,\Sigma$不便于求，我们可以利用如下性质

$AA^T=U\Sigma V^T V\Sigma^T U^T = U\Sigma\Sigma^T U^T \tag{2-2}$ $A^TA=V\Sigma^T U^T U\Sigma V^T = V\Sigma^T \Sigma V^T \tag{2-3}$

需要指出的是，这里 $\Sigma\Sigma^T$ 与$\Sigma^T \Sigma$在矩阵的角度上来讲，它们是不相等的，因为它们的维数不同$\Sigma \Sigma^T\in R^{m\times m}$，而$\Sigma^T \Sigma \in R^{n\times n}$，但是它们在主对角线的奇异值是相等的，即有
$\Sigma\Sigma^T=\begin{bmatrix} \sigma_1^2&0&0&0 \\ 0&\sigma_2^2&0&0\\ 0&0&\ddots&0\\ 0&0&0&\ddots \end{bmatrix}_{m \times m} \qquad \Sigma^T\Sigma=\begin{bmatrix} \sigma_1^2&0&0&0 \\ 0&\sigma_2^2&0&0\\ 0&0&\ddots&0\\ 0&0&0&\ddots \end{bmatrix}_{n \times n}$

可以看到式（2-2）与式（1-1）的形式非常相同，进一步分析，我们可以发现$AA^T$和$A^TA$也是对称矩阵，那么可以利用式（1-1），做特征值分解。利用式（2-2）特征值分解，得到的特征矩阵即为$U$；利用式（2-3）特征值分解，得到的特征矩阵即为$V$；对$\Sigma\Sigma^T$或$\Sigma^T\Sigma$中的特征值开方，可以得到所有的奇异值。

3.奇异值分解的应用

3.1 纯数学例子

假设我们现在有矩阵$A$，需要对其做奇异值分解，已知

$A=\begin{bmatrix} 1&5&7&6&1\\ 2&1&10&4&4\\ 3&6&7&5&2 \end{bmatrix}$

那么可以求出$AA^T$和$A^TA$，如下

$AA^T=\begin{bmatrix} 112&105&114\\ 105&137&110\\ 114&110&123 \end{bmatrix} \qquad A^TA=\begin{bmatrix} 14&25&48&29&15\\ 25&62&87&64&21\\ 48&87&198&117&61\\ 29&64&117&77&32\\ 15&21&61&32&21 \end{bmatrix}$

分别对上面做特征值分解，得到如下结果

U = [[-0.55572489,  0.40548161, -0.72577856],
    [-0.59283199, -0.80531618,  0.00401031],
    [-0.58285511,  0.43249337,  0.68791671]]

VT =  [[-0.18828164, -0.37055755, -0.74981208, -0.46504304, -0.22080294],
       [ 0.01844501,  0.76254787, -0.4369731 ,  0.27450785, -0.38971845],
       [ 0.73354812,  0.27392013, -0.12258381, -0.48996859,  0.36301365],
       [ 0.36052404, -0.34595041, -0.43411102,  0.6833004 ,  0.30820273],
       [-0.5441869 ,  0.2940985 , -0.20822387, -0.0375734 ,  0.7567019 ]]

奇异值$\Sigma$=Diag(18.53581747, 5.0056557 , 1.83490648)

3.2 SVD在图片压缩中的应用

加载相关库

import matplotlib.pyplot as plt
import matplotlib.image as  mpimg
import numpy as np
%matplotlib inline

读取图片

1 2	img_eg = mpimg.imread("view.jpeg") img_eg.shape

(1200, 1920, 3)

进行奇异值分解

1 2	img_temp = img_eg.reshape(1200, 1920*3) U, S, VT = np.linalg.svd(img_temp)

重构图像

sval_num = 60
img_condensed1 = (U[:,0:sval_num]).dot(np.diag(S[0:sval_num])).dot(VT[0:sval_num,:])
img_condensed1 = img_condensed1.reshape(1200, 1920, 3)

sval_num = 200
img_condensed2 = (U[:,0:sval_num]).dot(np.diag(S[0:sval_num])).dot(VT[0:sval_num,:])
img_condensed2 = img_condensed2.reshape(1200, 1920, 3)

对比效果

fig, ax = plt.subplots(1, 3, figsize=(24, 32))
ax[0].imshow(img_eg)
ax[0].set(title='src')
ax[1].imshow(img_condensed1.astype(np.uint8))
ax[1].set(title='nums of sigma = 60')
ax[2].imshow(img_condensed2.astype(np.uint8))
ax[2].set(title='nums of sigma = 120')

图3-1 奇异值分解重构图片

可以看到，当我们取到前面200个奇异值来重构图片时，基本上已经看不出与原图片有多大的差别。

总结

从上面的图片的压缩结果中可以看出来，奇异值可以被看作成一个矩阵的代表值，或者说，奇异值能够代表这个矩阵的信息。当奇异值越大时，它代表的信息越多。因此，我们取前面若干个最大的奇异值，就可以基本上还原出数据本身。

如下，可以作出奇异值数值变化和前部分奇异值和的曲线图，如下图所示

图3-1 奇异值变化图

从上面的第1个图，可以看出，奇异值下降是非常快的，因此可以只取前面几个奇异值，便可基本表达出原矩阵的信息。从第2个图，可以看出，当取到前100个奇异值时，这100个奇异值的和已经占总和的95%左右。