线性代数之——SVD 分解

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

1. SVD 分解

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

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

[AA^T=USigma^2U^T quad A^TA =VSigma^2V^T ]

证明：

让我们从 (A^TAv_i=sigma_i^2v_i) 开始，两边同乘以 (v_i^T)，有：

[v_i^TA^TAv_i=sigma_i^2v_i^Tv_i=sigma_i^2 o ||Av_i||=sigma_i ]

这说明向量 (Av_i) 的长度为 (sigma_i)。然后两边同乘以 (A)，有：

[AA^T(Av_i)=sigma_i^2(Av_i) o u_i = Av_i / sigma_i ]

这说明 (Av_i) 是 (AA^T) 的特征向量，除以其长度 (sigma_i) 我们便可以得到单位向量 (u_i)。这些 (oldsymbol{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 ]

奇异向量 (oldsymbol{v}) 位于 (A) 的行空间，而结果 (oldsymbol{u}) 位于 (A) 的列空间，奇异值都是正数。然后 (Av_i=sigma_iu_i) 一列一列告诉我们 (AV=USigma)，

[A egin{bmatrix} &&&\ v_1&v_2&cdots&v_r\&&& end{bmatrix} = egin{bmatrix} &&&\ u_1&u_2&cdots&u_r\&&& end{bmatrix} egin{bmatrix} sigma_1&&&\ &sigma_2&&\&&cdots&sigma_r end{bmatrix} ]

[(m×n)(n×r)=(m×r)(r×r) ]

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

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

[A=USigma V^T ]

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

2. 图像压缩

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

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

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

为什么会牵涉到 SVD 呢？矩阵 (A) 最好的秩 1 近似为 (sigma_1u_1v_1^T)，使用了最大的奇异值 (sigma_1)。最好的秩 5 近似为 (sigma_1u_1v_1^T+sigma_2u_2v_2^T+cdots+sigma_5u_5v_5^T)，SVD 按照降序放置矩阵 A 的小片。

3. 基和 SVD

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

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

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

[A^TA=(USigma V^T)^T(USigma V^T)=VSigma ^TSigma V^T ]

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

[AA^T=(USigma V^T)(USigma V^T)^T=USigma Sigma ^TU^T ]

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

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

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

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