奇异值分解(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} = 1wiT​wi​=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​=λi​vi​

这样我们就可以得到矩阵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​=σi​ui​⇒σ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的缺点是分解出的矩阵解释性往往不强，有点黑盒子的味道，不过这不影响它的使用。