线性代数之——SVD 分解

SVD 分解是线性代数的一大亮点。

1. SVD 分解

$A$A 是任意的 $m×n$m×n 矩阵，它的秩为 $r$r，我们要对其进行对角化，但不是通过 $S^{-1}A S$S−1AS。$S$S 中的特征向量有三个大问题：它们通常不是正交的；并不总是有足够的特征向量；$Ax=\lambda x$Ax=λx 需要 $A$A 是一个方阵。$A$A 的奇异向量很好地解决了上述所有问题。

代价是我们需要两组奇异向量，一组是 $\boldsymbol{u}$u， 一组是 $\boldsymbol{v}$v。$\boldsymbol{u}$u 是 $AA^T$AAT 的特征向量，$\boldsymbol{v}$v 是 $A^TA$ATA 的特征向量，因为这两个矩阵都是对称矩阵，我们可以选出一组标准正交的特征向量。即：

$AA^T=U\Sigma^2U^T \quad A^TA =V\Sigma^2V^T$AAT=UΣ2UTATA=VΣ2VT

证明：

让我们从 $A^TAv_i=\sigma_i^2v_i$ATAvi​=σi2​vi​ 开始，两边同乘以 $v_i^T$viT​，有：

$v_i^TA^TAv_i=\sigma_i^2v_i^Tv_i=\sigma_i^2 \to ||Av_i||=\sigma_i$viT​ATAvi​=σi2​viT​vi​=σi2​→∣∣Avi​∣∣=σi​

这说明向量 $Av_i$Avi​ 的长度为 $\sigma_i$σi​。然后两边同乘以 $A$A，有：

$AA^T(Av_i)=\sigma_i^2(Av_i) \to u_i = Av_i / \sigma_i$AAT(Avi​)=σi2​(Avi​)→ui​=Avi​/σi​

这说明 $Av_i$Avi​ 是 $AA^T$AAT 的特征向量，除以其长度 $\sigma_i$σi​ 我们便可以得到单位向量 $u_i$ui​。这些 $\boldsymbol{u}$u 还是正交的，因为：

$(Av_i)^TAv_j = v_i^T(A^TAv_j) = v_i^T(\sigma_j^2v_j) =\sigma_j^2v_i^Tv_j=0$(Avi​)TAvj​=viT​(ATAvj​)=viT​(σj2​vj​)=σj2​viT​vj​=0

奇异向量 $\boldsymbol{v}$v 位于 $A$A 的行空间，而结果 $\boldsymbol{u}$u 位于 $A$A 的列空间，奇异值都是正数。然后 $Av_i=\sigma_iu_i$Avi​=σi​ui​ 一列一列告诉我们 $AV=U\Sigma$AV=UΣ，

$A \begin{bmatrix} &&&\\ v_1&v_2&\cdots&v_r\\&&& \end{bmatrix} = \begin{bmatrix} &&&\\ u_1&u_2&\cdots&u_r\\&&& \end{bmatrix} \begin{bmatrix} \sigma_1&&&\\ &\sigma_2&&\\&&\cdots&\sigma_r \end{bmatrix}$A⎣⎡​v1​​v2​​⋯​vr​​⎦⎤​=⎣⎡​u1​​u2​​⋯​ur​​⎦⎤​⎣⎡​σ1​​σ2​​⋯​σr​​⎦⎤​

$(m×n)(n×r)=(m×r)(r×r)$(m×n)(n×r)=(m×r)(r×r)

这是 SVD 的核心，但不仅仅到此为止，这些 $\boldsymbol{v}$v 和 $\boldsymbol{u}$u 只负责矩阵 $A$A 的行空间和列空间，我们需要 $n-r$n−r 个额外的 $\boldsymbol{v}$v 和 $m-r$m−r 个额外的 $\boldsymbol{u}$u，分别来自零空间 $N(A)$N(A) 和左零空间 $N(A^T)$N(AT)。它们可以是这两个空间的标准正交基，当然它们也自动正交于前 $r$r 个 $\boldsymbol{v}$v 和 $\boldsymbol{u}$u。将这些新的向量包含进 $V$V 和 $U$U，我们依然有 $AV=U\Sigma $：

新的 $\Sigma$Σ 是 $m×n$m×n 的，由之前的 $r×r$r×r 矩阵 $\Sigma_r$Σr​ 和 $m-r$m−r 行零和 $n-r$n−r 列零组成。此时，$V$V 和 $U$U 分别是大小为 $n,m$n,m 的方阵，有 $V^{-1}=V^T$V−1=VT，则 $AV=U\Sigma$AV=UΣ 就变成了

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

这也就是 SVD 分解。当我们将奇异值降序排列时，上述的方程按照重要性给出了矩阵 $A$A 的 $r$r个秩为 1 的小片。

2. 图像压缩

这是一个数据的时代，并且数据经常存储在一个矩阵中。数字图像就是一个存储像素值的矩阵，比如一个大小为 256×512 的图像总共有 $2^8*2^9=2^{17}$28∗29=217 个元素。单独存储这一个图像对计算机来说是没问题的，但在 CT 和 MR 扫描过程中会产生大量的数据，又或者它们是电影中的帧图片，那么需要存储的数据量将会非常大。高清晰度的数字电视特别需要压缩，否则设备无法实时跟踪。

什么是压缩呢？我们想要用更少的数字代替这 $2^{17}$217 个元素，但同时不损失图像质量。一个简单的办法就是用一组中四个元素的均值来替换它们，这就是 4:1 压缩。但是如果我们想进一步压缩，比如 16:1，那么我们的图像就会有一些块效应，我们想要用一个人的视觉系统注意不到的方式进行压缩。

很多方法被提出来解决这个问题，比如用在 jpeg 中的傅里叶变换以及用在 JPEG2000 中的小波变换。这里我们尝试一个 SVD 的方法：用一个秩为 1 的矩阵，一列乘以一行，来替换原始的 256×512 矩阵。这样奏效的话，压缩比将会是 (256*512)/(256+512) 超过 170:1。实际上，我们会用 5 个秩为 1 的矩阵，这时候压缩比仍然有 34:1，而更重要的问题是图像质量。

为什么会牵涉到 SVD 呢？矩阵 $A$A 最好的秩 1 近似为 $\sigma_1u_1v_1^T$σ1​u1​v1T​，使用了最大的奇异值 $\sigma_1$σ1​。最好的秩 5 近似为 $\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_5u_5v_5^T$σ1​u1​v1T​+σ2​u2​v2T​+⋯+σ5​u5​v5T​，SVD 按照降序放置矩阵 A 的小片。

3. 基和 SVD

让我们以一个 2×2 的矩阵开始，

它的秩为 2，是可逆的。我们想要 $v_1,v_2$v1​,v2​ 是正交的单位向量，同时使得 $Av_1,Av_2$Av1​,Av2​ 正交。没有一个正交矩阵 $Q$Q 可以让 $Q^{-1}AQ$Q−1AQ 对角化，我们需要 $U^{-1}AV$U−1AV。

有一个简单的办法可以移除 $U$U 而只留下 $V$V，

$A^TA=(U\Sigma V^T)^T(U\Sigma V^T)=V\Sigma ^T\Sigma V^T$ATA=(UΣVT)T(UΣVT)=VΣTΣVT

这就和 $A=Q\Lambda Q^T$A=QΛQT 一样，只不过这里的对称矩阵不是 $A$A 本身，而是 $A^TA$ATA ，$V$V 的列是 $A^TA$ATA 的特征向量。然后我们可以利用 $u=Av/\sigma$u=Av/σ 来得到 $U$U，也可以直接得到，

$AA^T=(U\Sigma V^T)(U\Sigma V^T)^T=U\Sigma \Sigma ^TU^T$AAT=(UΣVT)(UΣVT)T=UΣΣTUT

矩阵 $U$U 和 $V$V 包含了四个子空间的标准正交基：

以下的例子很好地展示了矩阵的四个字空间和 SVD 的关系。

4. 特殊矩阵的特征值和特征向量

获取更多精彩，请关注「seniusen」!