线性代数之——SVD 分解

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

1. SVD 分解

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

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

 

\[AA^T=U\Sigma^2U^T \quad A^TA =V\Sigma^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 \to ||Av_i||=\sigma_i \]

 

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

 

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

 

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

 

线性代数之——SVD 分解

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

 

\[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} \]

 

 

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

 

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

线性代数之——SVD 分解

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

 

\[A=U\Sigma V^T \]

 

线性代数之——SVD 分解

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

线性代数之——SVD 分解

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 的矩阵开始,

线性代数之——SVD 分解

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

线性代数之——SVD 分解

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

 

\[A^TA=(U\Sigma V^T)^T(U\Sigma V^T)=V\Sigma ^T\Sigma V^T \]

 

线性代数之——SVD 分解

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

 

\[AA^T=(U\Sigma V^T)(U\Sigma V^T)^T=U\Sigma \Sigma ^TU^T \]

 

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

线性代数之——SVD 分解

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

线性代数之——SVD 分解

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

线性代数之——SVD 分解


线性代数之——SVD 分解

   
上一篇:SVD


下一篇:【图像隐藏】基于DWT与SVD算法的数字水印图像隐藏matlab源码