avatar

奇异值分解(SVD)

奇异值分解

奇异值分解(Singular Value Decomposition,简称SVD)是在机器学习领域广泛应用的算法,它不光可以用于降维算法中的特征分解,还可以用于推荐系统,以及自然语言处理等领域。是很多机器学习算法的基石。

特征值和特征向量

特征值和特征向量的定义如下:

Ax=λxA x=\lambda 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},以及n个特征值所对应的特征向量{w1,w2,,wn}\left\{w_{1}, w_{2}, \ldots, w_{n}\right\},如果这n个特征向量线性无关,那么这个矩阵A就可以用下式的特征分解表示:

A=WΣW1A = W \Sigma W^{-1}

其中W是这n个特征向量所构成的n * n维矩阵,而Σ\Sigma为这n个特征值为主对角线的n * n 维矩阵。

我们一般会把W这n个特征向量标准化,即满足wi2=1\left\|w_{i}\right\|_{2}=1,或者说wiTwi=1w_{i}^{T}w_{i} = 1,此时W的n个特征向量为标准正交基,满足WTW=IW^{T}W= I,即Wt=W1W^{t} = W^{-1},也就是我们说的右矩阵,

这样特征分解表达式可以表示为:

A=WΣWTA = W \Sigma W^{T}

进行特征分解时,A必须是方阵,如何不是方阵,此时我们的SVD就登场了。

SVD的定义

SVD是对矩阵进行分解,但是和特征分解不同的是,SVD并不要求要分解的矩阵为方阵,假设我们的矩阵A为m * n的矩阵,那么我们定义矩阵A的SVD为:

A=UΣVTA = U\Sigma V^{T}

其中U是一个m * m的矩阵,Σ\Sigma是一个m * n 的矩阵,除了主对角线上的元素,其余为0,主对角向上的袁术都称之为奇异值,V是n * n 的矩阵,U和V都是右矩阵,即满足UtU=I,VTV=IU^{t} U = I,V^{T}V = I

求矩阵U、 Σ\Sigma 、V

如果我们将A的转置和A做矩阵乘法,我们会得到n * n 的一个方阵ATAA^{T}A,那么我们就可以进行特征分解,得到特征向量和特征值,满足下式:

(ATA)vi=λivi(A^{T}A)v_{i} = \lambda_{i}v_{i}

这样我们就可以得到矩阵ATAA^{T}A的n个特征值和对应的n个特征向量v,将ATAA^{T}A的所有特征向量张成一个n * n的矩阵V,就是SVD中的V矩阵,一般我们将V中的每个特征向量叫做A的右奇异向量。

同理,我们将A和A的转置做矩阵乘法,我们会得到一个m * m 的一个方阵AATAA^{T},利用上述方法,可以进行特征分解达到特征值和特征向量。得到特征值和特征向量,将将AATAA^{T}的所有特征向量张成一个m * m的矩阵U,一般我们将U中的每个特征向量叫做A的做奇异向量。

由于矩阵Σ\Sigma除了对角线上是奇异值其他位置都是0.那么我们只需要求出每个奇异值σ\sigma就可以了。

我们注意到:

A=UΣVTAV=UΣVTVAV=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}

这样我们就可以求出我们的每个奇异值,进而求出戚其义值矩阵Σ\Sigma

那么为什么说ATAA^{T}A的特征向量组成的就是我们SVD中V矩阵,而AATAA^{T}的特征向量组成的就是我们SVD中的U矩阵,证明如下:

A=UΣVTAT=VΣTUTATA=VΣTUTUΣVTVΣ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}

上式证明了使用了:UTU=I,ΣTΣ=Σ2U^{T}U = I,\Sigma^{T} \Sigma = \Sigma^{2},可以看出ATAA^{T}A的特征向量组成的就是我们SVD中V矩阵,而AATAA^{T}的特征向量组成的就是我们SVD中的U矩阵。

进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方,也就是说特征值和奇异值满足:

σi=λi\sigma_{i} = \sqrt{\lambda_{i}}

这样我们可以不用σi=Avi/ui\sigma_{i} = Av_{i} / u_{i}来计算奇异值,也可以通过求出ATAA^{T}A的特征值去平方根来求奇异值。

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的缺点是分解出的矩阵解释性往往不强,有点黑盒子的味道,不过这不影响它的使用。

Author: Hui Ning
Link: https://angelni.github.io/SVD/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
    微信
  • 支付宝
    支付宝

Comment