奇异值分解(SVD)
奇异值分解
奇异值分解(Singular Value Decomposition，简称SVD)是在机器学习领域广泛应用的算法，它不光可以用于降维算法中的特征分解，还可以用于推荐系统，以及自然语言处理等领域。是很多机器学习算法的基石。
特征值和特征向量
特征值和特征向量的定义如下：
Ax=λxA x=\lambda xAx=λx
其中A是一个n*n的是对称矩阵，x是一个n维的向量，λ\lambdaλ则是我们说的矩阵A 的一个特征值，而x是矩阵A 的特征值λ\lambdaλ所对应的的特征向量。
求出特征值和特征向量，我们就可以将矩阵A进行特征分解。如果我们求出了矩阵A的n个特征值 λ1≤λ2≤…≤λn\lambda_{1} \leq \lambda_{2} \leq \ldots \leq \lambda_{n}λ1≤λ2≤…≤λn，以及n个特征值所对应的特征向量{w1,w2,…,wn}\left\{w_{1}, w_{2}, \ldots, w_{n}\right\}{w1,w2,…,wn},如果这n个特征向量线性无关，那么这个矩阵A就可以用下式的特征分解表示：
A=WΣW−1A = W \Sigma W^{-1}A=WΣW−1
其中W是这n个特征向量所构成的n * n维矩阵，而Σ\SigmaΣ为这n个特征值为主对角线的n * n 维矩阵。
我们一般会把W这n个特征向量标准化，即满足∥wi∥2=1\left\|w_{i}\right\|_{2}=1∥wi∥2=1，或者说wiTwi=1w_{i}^{T}w_{i} = 1wiTwi=1,此时W的n个特征向量为标准正交基，满足WTW=IW^{T}W= IWTW=I,即Wt=W−1W^{t} = W^{-1}Wt=W−1，也就是我们说的右矩阵，
这样特征分解表达式可以表示为：
A=WΣWTA = W \Sigma W^{T}A=WΣWT
进行特征分解时，A必须是方阵，如何不是方阵，此时我们的SVD就登场了。
SVD的定义
SVD是对矩阵进行分解，但是和特征分解不同的是，SVD并不要求要分解的矩阵为方阵，假设我们的矩阵A为m * n的矩阵，那么我们定义矩阵A的SVD为：
A=UΣVTA = U\Sigma V^{T}A=UΣVT
其中U是一个m * m的矩阵，Σ\SigmaΣ是一个m * n 的矩阵，除了主对角线上的元素，其余为0，主对角向上的袁术都称之为奇异值，V是n * n 的矩阵，U和V都是右矩阵，即满足UtU=I,VTV=IU^{t} U = I,V^{T}V = IUtU=I,VTV=I 。
求矩阵U、 Σ\SigmaΣ 、V
如果我们将A的转置和A做矩阵乘法，我们会得到n * n 的一个方阵ATAA^{T}AATA，那么我们就可以进行特征分解，得到特征向量和特征值，满足下式：
(ATA)vi=λivi(A^{T}A)v_{i} = \lambda_{i}v_{i}(ATA)vi=λivi
这样我们就可以得到矩阵ATAA^{T}AATA的n个特征值和对应的n个特征向量v，将ATAA^{T}AATA的所有特征向量张成一个n * n的矩阵V，就是SVD中的V矩阵，一般我们将V中的每个特征向量叫做A的右奇异向量。
同理，我们将A和A的转置做矩阵乘法，我们会得到一个m * m 的一个方阵AATAA^{T}AAT,利用上述方法，可以进行特征分解达到特征值和特征向量。得到特征值和特征向量，将将AATAA^{T}AAT的所有特征向量张成一个m * m的矩阵U，一般我们将U中的每个特征向量叫做A的做奇异向量。
由于矩阵Σ\SigmaΣ除了对角线上是奇异值其他位置都是0.那么我们只需要求出每个奇异值σ\sigmaσ就可以了。
我们注意到：
A=UΣVT⇒AV=UΣVTV⇒AV=UΣ⇒Avi=σiui⇒σi=Avi/uiA = U \Sigma V^{T} \Rightarrow AV=U \Sigma V^{T}V \Rightarrow AV = U\Sigma \Rightarrow Av_{i} = \sigma_{i}u_{i} \Rightarrow \sigma_{i} = Av_{i} / u_{i}A=UΣVT⇒AV=UΣVTV⇒AV=UΣ⇒Avi=σiui⇒σi=Avi/ui
这样我们就可以求出我们的每个奇异值，进而求出戚其义值矩阵Σ\SigmaΣ。
那么为什么说ATAA^{T}AATA的特征向量组成的就是我们SVD中V矩阵，而AATAA^{T}AAT的特征向量组成的就是我们SVD中的U矩阵，证明如下：
A=UΣVT⇒AT=VΣTUT⇒ATA=VΣTUTUΣVT⇒VΣ2VTA = U \Sigma V^{T} \Rightarrow A^{T}=V \Sigma^{T}U^{T} \Rightarrow A^{T}A = V\Sigma^{T}U^{T}U\Sigma V_{T} \Rightarrow V \Sigma^{2}V^{T}A=UΣVT⇒AT=VΣTUT⇒ATA=VΣTUTUΣVT⇒VΣ2VT
上式证明了使用了：UTU=I,ΣTΣ=Σ2U^{T}U = I,\Sigma^{T} \Sigma = \Sigma^{2}UTU=I,ΣTΣ=Σ2，可以看出ATAA^{T}AATA的特征向量组成的就是我们SVD中V矩阵，而AATAA^{T}AAT的特征向量组成的就是我们SVD中的U矩阵。
进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方，也就是说特征值和奇异值满足：
σi=λi\sigma_{i} = \sqrt{\lambda_{i}}σi=λi
这样我们可以不用σi=Avi/ui\sigma_{i} = Av_{i} / u_{i}σi=Avi/ui来计算奇异值，也可以通过求出ATAA^{T}AATA的特征值去平方根来求奇异值。
python实现SVD图像压缩
import numpy as np
import matplotlib.pyplot as plt
def SVD(origin_image, rate = 0.8):
# 显示原图像
plt.figure(figsize= (12, 12))
plt.title("Origin Image")
plt.imshow(origin_image)
plt.show()
print("\n\n======开始压缩======")
# 提前开辟结果存放空间
result = np.zeros(origin_image.shape)
# 对原图像进行SVD分解
u_shape = 0
s_shape = 0
vT_shape = 0
for chan in range(3):
# 对该层进行SVD分解
U, sigma, V = np.linalg.svd(origin_image[:, :, chan])
n_sigmas = 0
temp = 0
# 计算达到保留率需要的奇异值数量
while (temp / np.sum(sigma)) < rate:
temp += sigma[n_sigmas]
n_sigmas += 1
# 构建奇异值矩阵
S = np.zeros((n_sigmas, n_sigmas))
for i in range(n_sigmas):
S[i, i] = sigma[i]
# 构建结果
result[:, :, chan] = (U[:, 0:n_sigmas].dot(S)).dot(V[0:n_sigmas, :])
u_shape = U[:, 0:n_sigmas].shape
s_shape = S.shape
vT_shape = V[0:n_sigmas, :].shape
# 归一化到[0, 1]
for i in range(3):
MAX = np.max(result[:, :, i])
MIN = np.min(result[:, :, i])
result[:, :, i] = (result[:, :, i] - MIN) / (MAX - MIN)
# 调整到[0, 255]
result = np.round(result * 255).astype('int')
# 显示压缩结果
plt.figure(figsize= (12, 12))
plt.imshow(result)
plt.title("Result Image")
plt.show()
# 计算压缩率
zip_rate =(origin_image.size -3 * (u_shape[0] * u_shape[1] + s_shape[0] * s_shape[1] + vT_shape[0] * vT_shape[1])) / (origin_image.size)
print("保留率： ", rate)
print("所用奇异值数量为：", n_sigmas)
print("原图大小： ", origin_image.shape)
print("压缩后用到的矩阵大小：3 x ({} + {} + {})". format(u_shape, s_shape, vT_shape))
print("压缩率为： ", zip_rate)
# 定义主函数
def main():
# 读入图像
image_path = 'F:\\C-and-Python-Algorithn\\AI_study\\1.jpg'
origin_image = plt.imread(image_path)
# 利用自定义SVD图像压缩模块对图像进行压缩
SVD(origin_image, rate = 0.50)
# 主函数调用
if __name__ == "__main__":
main()原图
效果图
最后
SVD作为一个很基本的算法，在很多机器学习算法中都有它的身影，特别是在现在的大数据时代，由于SVD可以实现并行化，因此更是大展身手。SVD的原理不难，只要有基本的线性代数知识就可以理解，实现也很简单因此值得仔细的研究。当然，SVD的缺点是分解出的矩阵解释性往往不强，有点黑盒子的味道，不过这不影响它的使用。