数学知识—线代

为了论述矩阵的奇异值分解，需要下面的结论：

1.设$A \in {{C_r^{m*n}}}$A∈Crm∗n​ (r>0)，则$A^HA$AHA是Hermite矩阵，且其特征值均是非负实数；

2.$rank（A^HA）= rankA$rank（AHA）=rankA

3.设$A \in {{C_r^{m*n}}}$A∈Crm∗n​，则$A=O$A=O的充要条件是$A^HA=O$AHA=O

定义：设$A \in {{C_r^{m*n}}}(r>0)$A∈Crm∗n​(r>0) ，则$A^HA$AHA的特征值为：

${{\lambda_1}}\geq{{\lambda_2}}\geq....\geq{{\lambda_r}}\geq{{\lambda_{r+1}}}=.......={{\lambda_n}}=0$λ1​≥λ2​≥....≥λr​≥λr+1​=.......=λn​=0

则称 ${{\sigma_1}}=\sqrt{{{\lambda_i}}}(i=1,2,3,...,n)$σ1​=λi​​(i=1,2,3,...,n)为A的奇异值;当A为零矩阵时，它的奇异值都是0.

定理：设$A \in {{C_r^{m*n}}}$A∈Crm∗n​ (r>0)，则存在m阶酉矩阵U和n阶酉矩阵V，使得

$U^HAV= \left[ \begin{matrix} \Sigma & O \\ O & O \end{matrix} \right] \tag{1.1}$UHAV=[ΣO​OO​](1.1)``

其中$\Sigma$Σ=diag( ${{\sigma_1}},{{\sigma_2}},...,{{\sigma_r}}$σ1​,σ2​,...,σr​),${{\sigma_i}}(i=1,2,....,r)$σi​(i=1,2,....,r)为矩阵A的全部非零奇异值.

---

证   记Hermite矩阵$A^HA$AHA的特征值为：

${{\lambda_1}}\geq{{\lambda_2}}\geq....\geq{{\lambda_r}}\geq{{\lambda_{r+1}}}=.......={{\lambda_n}}=0$λ1​≥λ2​≥....≥λr​≥λr+1​=.......=λn​=0

根据$P^TP=\Lambda$PTP=Λ，存在n阶酉矩阵V使得

$U^H（A^HA）V= \left[ \begin{matrix} {{\lambda_1}} & & && & & \\ & {{\lambda_2}}& & & & & & \\ & &{{\lambda_3}} & & & & & \\ & &&. & & & & \\ & &&&.& & & \\ & &&& & .& & \\ & &&& & & .& \\ & &&& & & &{{\lambda_n}} \end{matrix} \right] = \left[ \begin{matrix} {{\Sigma^2}} & O \\ O & O \end{matrix} \right] \tag{1.2}$UH（AHA）V=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​λ1​​λ2​​λ3​​.​.​.​.​λn​​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​=[Σ2O​OO​](1.2)``

将$V$V分块为$V=$V=$[{{V_1}}| {V_2}]$[V1​∣V2​]，${{V_1}} \in {{C_r^{n*r}}},{{V_2}} \in {{C_{n-r}^{m*(n-r)}}}$V1​∈Crn∗r​,V2​∈Cn−rm∗(n−r)​

并改写式$（1.2）$（1.2）为

$A^HAV = V \left[ \begin{matrix} {{\Sigma^2}} & O \\ O & O \end{matrix} \right] \tag{1.3}$AHAV=V[Σ2O​OO​](1.3)``

则有 $A^HA{{V_1}}={{V_1}}{{\Sigma^2}}，A^HA{{V_2}}=O \tag{1.4}$AHAV1​=V1​Σ2，AHAV2​=O(1.4)

由式$（1.4）$（1.4）的第一式可得 $A^HA={{\Sigma^2}}或者(A{{V_1}}{{\Sigma^{-1}}})^H(A{{V_1}}{{\Sigma^{-1}}})={{I_r}}$AHA=Σ2或者(AV1​Σ−1)H(AV1​Σ−1)=Ir​

由式$（1.4）$（1.4）的第二式可得$(A{{V_1}})^H(A{{V_2}})=O或A{{V_2}}=O$(AV1​)H(AV2​)=O或AV2​=O

令${U_1}=A{V_1}{{\Sigma^{-1}}}$U1​=AV1​Σ−1，则${U_1}^H{U_1}={I_r}$U1​HU1​=Ir​,即${U_1}$U1​的$r$r个列是两两正交的单位向量，记作${U_1}=({u_1},{u_2},{u_3},...{u_r})$U1​=(u1​,u2​,u3​,...ur​),并将${u_1},{u_2},{u_3},...{u_r}$u1​,u2​,u3​,...ur​扩充为$C^m$Cm的标准正交基，记增添为${u_{r+1}}，...，{u_m}$ur+1​，...，um​，并构造${U_2}=({u_{r+1}},...{u_m})$U2​=(ur+1​,...um​),则$U=[{{U_1}}| {U_2}]=({u_1},{u_2},{u_3},...{u_r}，...，{u_m})$U=[U1​∣U2​]=(u1​,u2​,u3​,...ur​，...，um​)是m阶酉矩阵，且有 ${{U_1^H}}{U_1}={I_r},{{U_2^H}}{U_1}=O$U1H​U1​=Ir​,U2H​U1​=O

于是可得

$U^HAV=U^H[{A{V_1}}|A {V_2}]= \left[ \begin{matrix} {U_1}^H \\ {U_2}^H \end{matrix} \right] \left[ \begin{matrix} {U_1} {{\Sigma}} & O \end{matrix} \right]= \left[ \begin{matrix} {U_1}^H{U_1}{{\Sigma}} & O \\ {U_2}^H{U_2}{{\Sigma}} & O \end{matrix} \right] =\left[ \begin{matrix} \Sigma & O \\ O & O \end{matrix} \right] 证毕$UHAV=UH[AV1​∣AV2​]=[U1​HU2​H​][U1​Σ​O​]=[U1​HU1​ΣU2​HU2​Σ​OO​]=[ΣO​OO​]证毕``

改写式$(1.1)$(1.1)为

$A=U \left[ \begin{matrix} \Sigma & O \\ O & O \end{matrix} \right] V^H\tag{1.5}$A=U[ΣO​OO​]VH(1.5)``

SVD分解的应用—图像压缩

    奇异值分解（Singular Value Decomposition，SVD）作为一种常用的矩阵分解和数据降维方法，在机器学习中也得到了广泛的应用，比如自然语言处理中的SVD词向量和潜在语义索引，推荐系统中的特征分解，SVD用于PCA降维以及图像去噪与压缩等。作为一个基础算法，我们有必要将其单独拎出来在机器学习系列中进行详述。

SVD图像压缩

    通过尝试将SVD用于图像的压缩算法，其原理就是保存像素矩阵的前k个奇异值，并在此基础上做图像恢复。由SVD的原理我们可以知道，在SVD分解中越靠前的奇异值越重要，代表的信息含量越大。 下面我们尝试对一个图像进行SVD分解，并分别取前1~50个奇异值来恢复该图像。需要恢复的图像如下：

实现：Python中numpy和scipy两个科学计算库都直接提供了SVD的实现方式，所以我们这里就不再基于numpy手写SVD的实现过程了。下面基于numpy.linalg线性代数模块下的svd函数来看一个计算实例。

Python代码实现：

import numpy as np
from PIL import Image
from tqdm import tqdm


# 定义恢复函数，由分解后的矩阵恢复到原矩阵
def restore(u, s, v, K):  # u:左奇异值矩阵 v:右奇异值矩阵 s:奇异值矩阵 K:奇异值个数
    m, n = len(u), len(v[0])
    a = np.zeros((m, n))
    for k in range(K):
        uk = u[:, k].reshape(m, 1)
        vk = v[k].reshape(1, n)
        # 前k个奇异值的加总
        a += s[k] * np.dot(uk, vk)
        a = a.clip(0, 255)
    return np.rint(a).astype('uint8')


A = np.array(Image.open("C:/Users/Administrator/Desktop/image/headpic01.jpg", 'r')) #所要压缩图片的路径
# 对RGB图像进行奇异值分解
u_r, s_r, v_r = np.linalg.svd(A[:, :, 0])
u_g, s_g, v_g = np.linalg.svd(A[:, :, 1])
u_b, s_b, v_b = np.linalg.svd(A[:, :, 2])
# 使用前50个奇异值
K = 50
output_path = r'C:Users/Administrator/Desktop/image/svd_pic' #所得的压缩图像吃存放路径
# 恢复图像
for k in tqdm(range(1, K + 1)): # tqdm模拟进度条效果
    R = restore(u_r, s_r, v_r, k)
    G = restore(u_g, s_g, v_g, k)
    B = restore(u_b, s_b, v_b, k)
    I = np.stack((R, G, B), axis=2)
    Image.fromarray(I).save('%s\\svd_%d.jpg' % (output_path, k)) 输出图片

当K=1时，被压缩后的图像模糊一团，除了颜色线条啥也看不出：

当K=25时，恢复后的压缩图像，就像打了马赛克一样：

当K=50时，所得到的压缩图像已经相对清晰许多了：

输出所得图像的渐进效果如下：

总体而言就是图像清晰度随着奇异值数量增多而变好。当奇异值k不断增大时，恢复后的图像就会无限逼近于真实图像。这便是基于SVD的图像压缩原理。