奇异值分解(SVD)

程序员文章站 2022-07-12 14:11:02

...

奇异值分解

定义

对于矩阵 X ∈ C n × m \mathbf{X} \in \mathbb{C}^{n\times m} X∈Cn×m，存在唯一的矩阵分解：
X = U Σ V ∗ \mathbf{X} = \mathbf{U}\Sigma \mathbf{V}^* X=UΣV∗
其中 U ∈ C n × n \mathbf{U}\in \mathbb{C}^{n\times n} U∈Cn×n 以及 V ∈ C m × m \mathbf{V}\in \mathbb{C}^{m\times m} V∈Cm×m是列正交的酉矩阵， Σ ∈ C n × m \mathbf{\Sigma}\in \mathbb{C}^{n\times m} Σ∈Cn×m为实矩阵，且非零元均位于对角线上，非对角线元均为零。
当 n ≥ m n\ge m n≥m时，矩阵 Σ \mathbf{\Sigma} Σ对角线上最多有 m m m个非零元，可以记作 Σ = [ Σ ^ 0 ] \mathbf{\Sigma} = \left[\begin{array}{c} \hat{\mathbf{\Sigma}}\\ \mathbf{0}\\ \end{array}\right] Σ=[Σ^0]。因此，用经济的SVD精确表示 X \mathbf{X} X是可能的：
X = U Σ V ∗ = [ U ^ U ^ ⊥ ] [ Σ ^ 0 ] V ∗ = U ^ Σ ^ V ∗ \mathbf{X} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^* = \left[ \begin{array}{cc} \hat{\mathbf{U}} & \hat{\mathbf{U}}^{\perp} \end{array}\right]\left[\begin{array}{c} \hat{\mathbf{\Sigma}}\\ \mathbf{0}\\ \end{array}\right]\mathbf{V}^* = \hat{\mathbf{U}}\hat{\mathbf{\Sigma}}\mathbf{V}^* X=UΣV∗=[U^U^⊥][Σ^0]V∗=U^Σ^V∗
矩阵 U ^ ⊥ \hat{\mathbf{U}}^{\perp} U^⊥的列张成的线性空间与矩阵 U ^ \hat{\mathbf{U}} U^张成的线性空间互补且正交。矩阵 U U U的列向量称为 X X X的左奇异向量，矩阵 V V V的列向量称为 X X X的右奇异向量以及矩阵 Σ ^ \hat{\mathbf{\Sigma}} Σ^的对角元称为奇异值。矩阵 X X X的秩与非零奇异值的个数相等。
奇异值分解(SVD)

计算

奇异值分解与矩阵 X X ∗ \mathbf{X}\mathbf{X}^* XX∗和 X ∗ X \mathbf{X}^*\mathbf{X} X∗X的特征值问题密切相关，我们将 X = U Σ V ∗ \mathbf{X}=\mathbf{U}\Sigma \mathbf{V}^* X=UΣV∗代入即可直观的发现两者之间的联系，
X X ∗ = U [ Σ ^ 0 ] V ∗ V [ Σ ^ 0 ] U ∗ = U [ Σ ^ 2 0 0 0 ] U ∗ X ∗ X = V [ Σ ^ 0 ] U ∗ U [ Σ ^ 0 ] V ∗ = V Σ ^ 2 V ∗ \begin{aligned} &\mathbf{X}\mathbf{X}^* = \mathbf{U} \left[\begin{array}{c} \hat{\mathbf{\Sigma}}\\ \mathbf{0}\\ \end{array}\right] \mathbf{V}^* \mathbf{V} \left[\begin{array}{cc} \hat{\mathbf{\Sigma}} & \mathbf{0}\\ \end{array}\right] \mathbf{U}^* =\mathbf{U} \left[\begin{array}{cc} \hat{\mathbf{\Sigma}}^2 & \mathbf{0}\\ \mathbf{0} & \mathbf{0}\\ \end{array}\right] \mathbf{U}^*\\ &\mathbf{X}^*\mathbf{X} =\mathbf{V} \left[\begin{array}{cc} \hat{\mathbf{\Sigma}} & \mathbf{0}\\ \end{array}\right] \mathbf{U}^*\mathbf{U} \left[\begin{array}{c} \hat{\mathbf{\Sigma}}\\ \mathbf{0}\\ \end{array}\right] \mathbf{V}^*=\mathbf{V}\hat{\mathbf{\Sigma}}^2\mathbf{V}^* \end{aligned} XX∗=U[Σ^0]V∗V[Σ^0]U∗=U[Σ^2000]U∗X∗X=V[Σ^0]U∗U[Σ^0]V∗=VΣ^2V∗
由于 U \mathbf{U} U和 V \mathbf{V} V都是酉矩阵，则 U \mathbf{U} U、 Σ ^ \hat{\mathbf{\Sigma}} Σ^和 V \mathbf{V} V即为下面特征值问题的解：
X X ∗ U = U [ Σ ^ 2 0 0 0 ] X ∗ X V = V Σ ^ 2 \begin{aligned} &\mathbf{X}\mathbf{X}^*\mathbf{U} = \mathbf{U} \left[\begin{array}{cc} \hat{\mathbf{\Sigma}}^2 & \mathbf{0}\\ \mathbf{0} & \mathbf{0}\\ \end{array}\right]\\ &\mathbf{X}^*\mathbf{X} \mathbf{V} = \mathbf{V}\hat{\mathbf{\Sigma}}^2 \end{aligned} XX∗U=U[Σ^2000]X∗XV=VΣ^2
故而非零奇异值即为矩阵 X X ∗ \mathbf{X}\mathbf{X}^* XX∗和 X ∗ X \mathbf{X}^*\mathbf{X} X∗X的特征值的正平方根，左奇异矩阵 U \mathbf{U} U为矩阵 X X ∗ \mathbf{X}\mathbf{X}^* XX∗的特征向量，右奇异矩阵 V \mathbf{V} V为矩阵 X ∗ X \mathbf{X}^*\mathbf{X} X∗X的特征向量。

应用举例-图像压缩

Python代码如下，图片尺寸为 500 × 700 500\times700 500×700，来源为百度上随便搜的一张图:

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

flower = mpimg.imread('./flower.jpg')
nx, ny = np.shape(flower)[0], np.shape(flower)[1]

plt.figure()
plt.subplot(221,title="Origin")
plt.imshow(flower)
plt.axis('off')
k=1
for r in [5, 20, 100]:
    flower1 = np.zeros((nx, ny, 3),dtype=float)
    for i in range(3):
        U, S, V = np.linalg.svd(flower[:, :, i]/255, full_matrices=True)
        flower1[:, :, i] = U[:, 0:r] @ np.diag(S[0:r]) @ V[0:r, :]
    plt.subplot(221+k, title = "r={}".format(r))
    plt.imshow(flower1)
    plt.axis('off')
    k+=1
plt.show()

结果如下：
奇异值分解(SVD) 可以看到当 r = 20 r=20 r=20，即取前20个较大的奇异值即可基本还原图像的信息。

参考文献

[1] Brunton S L , Kutz J N . Data-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Control[M]. 2019.

奇异值分解(SVD)