SVD Singular Value Decomposition 奇异值分解

直接感受:将一个矩阵写成以下形式
$$A = U\Sigma V^T$$
其中A为需要奇异值分解的矩阵,\(\Sigma\)为对角矩阵,由奇异值组成对角线,其它元素均为0。U 称为左奇异矩阵,V称为右奇异矩阵。$U \in R^{m\times m},\ \Sigma \in R^{m\times n},\ V \in R^{n\times n}$

用途:可以应用于数据降维,如PCA、图片压缩处理等

SVD基于特征值分解 Eigendecomposition EVD

在python numpy 库中,可以分别用numpy.linalg.svd()求得,使用方式: U,Sigma,VT = np.linalg.svd(A)

特征值分解 EVD

将一个矩阵写成以下形式:
$$A = U\Sigma U^T$$
其中A为需要奇异值分解的矩阵,\(\Sigma\)为对角矩阵,由特征值组成对角线,其它元素均为0。U为特征值对应的特征向量组成的特征矩阵,并且为正交矩阵,$UU^T = E$

在python numpy 库中,可以分别用numpy.linalg.eig()求得,使用方式: U,Sigma = np.linalg.eig(A)

数学原理

定义

设A是n阶矩阵,如果数\(\lambda\)和n维非零列向量\(\boldsymbol{x}\)使关系式:
$$A\boldsymbol{x}=\lambda\boldsymbol{x}$$
成立,那么这样的数\(\lambda\)称为矩阵A的特征值,非零向量\(\boldsymbol{x}\)称为A的对应于\(\lambda\)的特征向量。

求解

  1. 解特征值,特征向量

$$A\boldsymbol{x}=\lambda\boldsymbol{x}\implies (A-\lambda I)\boldsymbol{x}=0$$

$$\implies |A-\lambda I|=0\implies $$

$$\left[ \begin{matrix} a_{11}-\lambda&a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22}-\lambda&\cdots & a_{2n}\\ \cdots & \cdots & \ddots & \cdots\\ a_{n1} & a_{n2}& \cdots&a_{nn}-\lambda\end{matrix} \right]=0$$

该步骤可以解出n个复数根,也就是n阶矩阵的n个特征值。将解代入下式,求出对应的特征向量。

$$\implies (A-\lambda_iI)x=0 \implies x=p_i,p_i!=0$$

\(\boldsymbol{p}_i\)的特征向量。

  1. 推导公式

$$A\boldsymbol{x}=\lambda\boldsymbol{x}$$ \(x\)为特征向量

同样\(x\)(列向量)组成的矩阵也一样满足该式,即:

$$\implies AU=(Ap_1,Ap_2,Ap_3,…,Ap_n)$$ $$= (\lambda_1 p_1,\lambda_2 p_2,\lambda_3 p_3,…,\lambda_b p_n)$$

$$=(p_1,p_2,…,p_n)\left[ \begin{matrix} \lambda_1 & \cdots & \cdots & \cdots\\ \cdots & \lambda_2 & \cdots & \cdots \\ \cdots & \cdots & \ddots & \cdots \\ \cdots & \cdots & \cdots & \lambda_m \end{matrix} \right]=U \Sigma $$ \(\Sigma\) 为\(\lambda\)组成的对角矩阵

两边右乘一个\(U^{-1}\),得:

$$A = U\Sigma U^{-1}$$

\(U\)为正交矩阵,\(UU^T = E,UU^{-1}=E,U^{-1}=U^T\)

$$A = U\Sigma U^T= U\left[ \begin{matrix} \lambda_1 & \cdots & \cdots & \cdots\\ \cdots & \lambda_2 & \cdots & \cdots\\ \cdots & \cdots & \ddots & \cdots\\ \cdots & \cdots & \cdots & \lambda_m\ \end{matrix} \right]U^T $$

即:

$$A = U\Sigma U^T$$

奇异值分解 SVD

特征值分解需要被分解的矩阵\(A\)为实对称矩阵。对于一般\(m * n\)矩阵则需要通过SVD进行分解。

$$A = U\Sigma V^T$$

当给定一个大小为\(mn\)的矩阵\(A\),虽然矩阵\(A\)不一定是方阵,但大小为的\(mm\)的\(AA^T\)和\(n*n\)的\(A^TA\)却是对称矩阵。
然后对$$AA^T,A^TA$$做特征值分解。
$$AA^T=U\Sigma V^TV\Sigma^TU^T=U\Sigma \Sigma^TU^T$$
$$A^TA=V\Sigma^TU^TU\Sigma V^T=V\Sigma^T\Sigma V^T$$

\(\Sigma \Sigma^T,\Sigma^T \Sigma\)对角线上分别为\(AA^T,A^TA\)的特征值

其中U为矩阵A的左奇异向量(left singular vector),V为矩阵A的右奇异向量(right singular vector),\(\Sigma \Sigma^T ,\Sigma^T \Sigma\)两个矩阵对角线上的非零元素相同,位于对角线上的元素被称为奇异值(singular value)。设两个矩阵对角线上非零的特征值为\(\lambda_1,\lambda_2,\lambda_3,…,\lambda_n\),则奇异值为特征值的开方,即:\(\sigma=\sqrt{\lambda}\)

举例 图片压缩

Python, numpy, matplotlib

import matplotlib
import matplotlib.pyplot as plt
import numpy as np
  • 获取图片大小
img=matplotlib.image.imread('geed.jpg')
print(img.shape)
(386, 576, 3)
  • 奇异值分解
img_temp = img.reshape(386, 576 * 3)
U,Sigma,VT = np.linalg.svd(img_temp)
  • 取部分奇异值用于压缩图片
sval_nums = 50
img_restruct1 = (U[:,0:sval_nums]).dot(np.diag(Sigma[0:sval_nums])).dot(VT[0:sval_nums,:])
img_restruct1 = img_restruct1.reshape(img.shape)

sval_nums = 120
img_restruct2 = (U[:,0:sval_nums]).dot(np.diag(Sigma[0:sval_nums])).dot(VT[0:sval_nums,:])
img_restruct2 = img_restruct2.reshape(img.shape)

sval_nums = 386
img_restruct3 = (U[:,0:sval_nums]).dot(np.diag(Sigma[0:sval_nums])).dot(VT[0:sval_nums,:])
img_restruct3 = img_restruct3.reshape(img.shape)
fig,axs=plt.subplots(2,2,figsize = (12,8))
axs[0][0].imshow(img)
axs[0][1].imshow(img_restruct1.astype(np.uint8))
axs[1][0].imshow(img_restruct2.astype(np.uint8))
axs[1][1].imshow(img_restruct3.astype(np.uint8))
<matplotlib.image.AxesImage at 0x1e0fbd896c8>

Categories: MathmaticsPython

0 Comments

Leave a Reply

Your email address will not be published.