奇异值分解的原理与使用

奇异值分解的原理

特征值和特征向量

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

$$
Ax = \lambda x
\tag{1}
$$

其中，$\lambda$是一个标量，$x$是一个向量，$\lambda$称作矩阵$A$的特征值，$x$是其对应的特征向量。

求得所有特征值和特征向量后，我们就可以对矩阵 A 进行特征分解。具体如下：

$$
A = W \Sigma W^{-1}
\tag{2}
$$

其中，$W$是由$A$的所有特征向量组成的$n\times n$维矩阵。$\Sigma$是以$A$的所有特征值$\lambda_1,\lambda_2,\dots,
\lambda_n$为对角线的对角矩阵。我们一般会把$W$的这$n$个特征向量标准化，即满足$||w_i|| = 1$或者$w_i^T \cdot w_i = w_i^T
w_i=1$，此时，$W$的$n$个向量为标准正交基。

故：

$$
W^{-1} = W^T
\tag{3}
$$

这样我们的特征分解表达式可以写成

$$
A = W \Sigma W^T
\tag{4}
$$

$SVD$的定义

$SVD$也是对矩阵进行分解，但是和特征分解不同，$SVD$并不要求要分解的矩阵为方阵。假设我们的矩阵 A
是一个$𝑚×𝑛$的矩阵，那么我们定义矩阵$A$的$SVD$为：

$$
A = U\Sigma V^T
\tag{5}
$$

其中，$U$的形状为：$m \times m$，$\Sigma$的形状为$m \times n$，是一个对角矩阵，对角线上的每一个值都是$A$的一个奇异值
，$V$的形状为$n \times n$，$A$的形状与$\Sigma$的形状一致。在此处，$U$和$V^T$都是酉矩阵，即：

$$
U^TU=I \\ V^TV=I
\tag{6}
$$

$SVD$的求法

$$
\begin{align}
A & = U\Sigma V^T \\
\Rightarrow AV & = U\Sigma V^TV \\
\Rightarrow AV & =U\Sigma \\
\Rightarrow Av_i & = \sigma_i u_i \\
\Rightarrow \sigma_i & = Av_i / u_i
\end{align}
\tag{7}
$$

这样我们可以求出我们的每个奇异值，进而求出奇异值矩阵$\Sigma$。我们说$A^TA$的特征向量
组成的就是我们$SVD$中的$V$矩阵，而$AA^T$的特征向量组成的就是我们$SVD$中的$U$矩阵。

$$
U^TU=I, \Sigma^T\Sigma=\Sigma^2
\tag{8}
$$

$$
\begin{align}
A & =U\Sigma V^T \\
\Rightarrow A^T & = V\Sigma^T U^T \\
\Rightarrow A^TA & = V\Sigma^T U^TU\Sigma V^T \\
&= V\Sigma^2V^T
\end{align}
\tag{9}
$$

可以看出$A^T A$的特征向量组成的的确就是我们$SVD$中的 V 矩阵。类似的方法可以得到$AA^T$的特征向量组成的就是我们$SVD$中的$U$矩阵。

进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方，也就是说特征值和奇异值满足如下关系：

$$
\sigma_i = \sqrt{\lambda_i}
\tag{10}
$$

这样也就是说，我们可以不用$\sigma_i = \frac{Av_i}{u_i}$来计算奇异值，也可以通过求出$A^T A$的特征值取平方根来求奇异值。

$SVD$的使用

$SVD$的使用主要是用在两个方面，一方面是主成分分析。

主成分分析

$$
A_{m \times n} = U_{m \times m}\Sigma_{m \times n} V^T_{n \times n} \approx U_{m \times k}\Sigma_{k \times k} V^T_{k
\times n}
\tag{11}
$$

上式的主要意义在于，使用奇异值去近似的表达一个矩阵，因为$\Sigma$中的奇异值是根据大小排列的，如果舍去较小的奇异值，在将只乘回去，得到的结果与原矩阵十分近似。较大的奇异值组合就变成了原矩阵的主要成分。

降维

也是根据$(11)$式，我们将较小的一部分奇异值舍去的话，在进行矩阵运算的时候可以达到降维的作用。

$SVD$在图像处理中的应用。

先上代码

from PIL import Image
import numpy as np
from numpy import linalg as la


def processImg(img, gate):
    a = np.asarray(img)
    u, sigma, vt = la.svd(a)
    s = np.zeros([u.shape[0], vt.shape[1]])
    c = 0
    gate = (gate / 100) * (u.shape[0] if u.shape[0] < vt.shape[1] else vt.shape[1])
    for i in sigma:
        s[c][c] = i if c < gate else 0
        c = c + 1
    return Image.fromarray(np.dot(np.dot(u, s), vt)).convert('L')


if __name__ == '__main__':
    for image in range(8):
        img = Image.open("source_img/img.%s.jpg" % image)
        r, g, b = img.split()
        for i in [1, 5, 10, 25, 50, 70, 90]:
            print("processing 【image%s】  %s%s ..." % (image, i, '%'))
            nr = processImg(r, i)
            ng = processImg(g, i)
            nb = processImg(b, i)
            img = Image.merge('RGB', [nr, ng, nb])
            img.save('imgs/img.%s.%s.png' % (image, i), "png")
            print("\t【image%s】Done" % image)
    print("done...")

完成后的图片

以下图片均来自网络，若有侵权请联系删除： cyrusky#borgor.cn