30奇异值分解

在讲SVD之前，我们先来看看计算是如何存储一个灰度图的。计算机用矩形，这个矩形由很多小块组成，这个在图像中是一个像素点，因为表示的是灰度图，所以一共有256种状态，不同数值表示不同的灰度程度。如果一个图像时纯白的，那么其所有像素点数值为255。

如果我们要拷贝一个 $m\times n$ 像素图像时，那一共需要多少次位的操作呢？答：
$m\times n\times 8$，一个典型的电视一般有 $m=1080$ $n=1920$，对于每一秒都会有24帧这样的像素图，更不用考虑彩色图像了，这个数据量对于传输设备来说是非常昂贵的，那么应该如何使得其更有效率传输？

对于一个视频而言，相邻不大的帧像素之间的变化时不大的，这使得我们只需要传输那些变化的数据，而不是所有的都进行覆写。所有的视频格式都是按照一定的线性代数规则将其变换存储下来的。

一、低秩图像（Low Rank Image）

2.1 例子1

压缩一个全黑或者全白的图像是非常容易的：
A=[111111111111111111111111111111111111]A=\\begin{bmatrix} 1&1&1&1&1&1\\\\ 1&1&1&1&1&1\\\\ 1&1&1&1&1&1\\\\ 1&1&1&1&1&1\\\\ 1&1&1&1&1&1\\\\ 1&1&1&1&1&1\\\\ \\end{bmatrix} A=​111111​111111​111111​111111​111111​111111​​
传输这样一个数据是非常低效的，我们可以将其分解以降低其数据量：
A=[111111][111111]A=\\begin{bmatrix} 1\\\\1\\\\1\\\\1\\\\1\\\\1 \\end{bmatrix}\\begin{bmatrix} 1&1&1&1&1&1 \\end{bmatrix} A=​111111​​[1​1​1​1​1​1​]
传输的数据量从原来的 $64$ 变成了 $12$。当然这样的例子是非常极端的，这样的全一矩阵，在处理起来是非常快速的。预设基还是动态调整基（也就是本例）是存在争议的，SVD的方法有时候并不是最高效的。

2.2 例子2

A=[aacceeaacceeaacceeaacceeaacceeaaccee]A=\\begin{bmatrix} a&a&c&c&e&e\\\\ a&a&c&c&e&e\\\\ a&a&c&c&e&e\\\\ a&a&c&c&e&e\\\\ a&a&c&c&e&e\\\\ a&a&c&c&e&e\\\\ \\end{bmatrix} A=​aaaaaa​aaaaaa​cccccc​cccccc​eeeeee​eeeeee​​
改成传输
A=[111111][aaccee]A=\\begin{bmatrix} 1\\\\1\\\\1\\\\1\\\\1\\\\1 \\end{bmatrix}\\begin{bmatrix} a&a&c&c&e&e \\end{bmatrix} A=​111111​​[a​a​c​c​e​e​]

例子1和例子2的共同之处都是矩阵的秩都为1，且都能写成一列乘以一行

1.3 例子3

A=[1011]A=\\begin{bmatrix}1&0\\\\1&1\\end{bmatrix} A=[11​01​]
这样的矩阵的秩是2，其中一种分解方法是：
A=[11][11]−[10][01]A=\\begin{bmatrix}1\\\\1\\end{bmatrix}\\begin{bmatrix}1&1\\end{bmatrix}-\\begin{bmatrix}1\\\\0\\end{bmatrix}\\begin{bmatrix}0 &1\\end{bmatrix} A=[11​][1​1​]−[10​][0​1​]
这样的分解不是根据SVD规则选取的，因为列向量和列向量不是正交的，行向量和行向量也不是正交的。如果是按照SVD规则选取的，第二项可能具更小的权重。如何选取出SVD所需要的向量呢？接下来就会对这个进行说明。

二、找出SVD需要的特征向量

大多数图像矩阵对应的特征向量都不是正交的，我们想要找出的是多项“列向量乘以行向量”的和形式，实现对矩阵的分解。SVD是这样完成特征向量的寻找的：

从 AATAA^TAAT 中获取特征向量 $u$ ，从 ATAA^TAATA 获取特征向量 $v$

AATAA^TAAT 和 AATAA^TAAT 是自动对称的，左边的新矩阵获取列向量 $u$，右边的新矩阵获取行向量，更进一步，我们将这些向量进行单位化，也就是 ∣∣ui∣∣=1||u_i||=1∣∣ui​∣∣=1 ， ∣∣∣vi∣∣=1|||v_i||=1∣∣∣vi​∣∣=1 。单位化不改变原来向量方向，同时为了保持不变，还会多乘以一个系数，我们将其记为 σi\\sigma_iσi​。这么一来秩2矩阵 $A$，就可以写成：
A=σ1u1v1T+σ2u2v2TA=\\sigma_1u_1v_1^T+\\sigma_2u_2v_2^T A=σ1​u1​v1T​+σ2​u2​v2T​
其中，单位化的系数 σ1\\sigma_1σ1​、σ2\\sigma_2σ2​表示了这个分量的权重，我们将保留更大的 $\sigma$项，忽略那些相对较小的 $\sigma$。

我们从以下等式中选取特征向量：
AATui=σi2uiATAvi=σi2viAvi=σiuiAA^Tu_i=\\sigma_i^2u_i\\quad A^TAv_i=\\sigma_i^2v_i\\quad Av_i=\\sigma_iu_i AATui​=σi2​ui​ATAvi​=σi2​vi​Avi​=σi​ui​

例子3：还是前面的矩阵
A=[1011]A=\\begin{bmatrix}1&0\\\\1&1\\end{bmatrix} A=[11​01​]
分别写出 AATAA^TAAT 和 ATAA^TAATA 矩阵的结果:
AAT=[1011][1101]=[1112]AA^T=\\begin{bmatrix}1&0\\\\1&1\\end{bmatrix}\\begin{bmatrix}1&1\\\\0&1\\end{bmatrix}=\\begin{bmatrix}1&1\\\\1&2\\end{bmatrix} AAT=[11​01​][10​11​]=[11​12​]
同理有:
ATA=[2111]A^TA=\\begin{bmatrix}2&1\\\\1&1\\end{bmatrix} ATA=[21​11​]
可以计算对应的特征值为:
λ1=3+52λ2=3−52\\lambda_1=\\frac{3+\\sqrt{5}}{2}\\quad\\lambda_2=\\frac{3-\\sqrt{5}}{2} λ1​=23+5​​λ2​=23−5​​
再对两个特征值进行开根号得到 $\sigma$：
σ1=5+12σ2=5−12\\sigma_1=\\frac{\\sqrt{5}+1}{2}\\quad\\sigma_2=\\frac{\\sqrt{5}-1}{2} σ1​=25​+1​σ2​=25​−1​
AATAA^TAAT和 ATAA^TAATA对应的特征向量为：
u1=[1σ1]u2=[σ1−1]v1=[σ11]v2=[1−σ1]u_1=\\begin{bmatrix}1\\\\\\sigma_1\\end{bmatrix}\\quad u_2=\\begin{bmatrix}\\sigma_1\\\\-1\\end{bmatrix}\\quad v_1=\\begin{bmatrix}\\sigma_1\\\\1\\end{bmatrix}\\quad v_2=\\begin{bmatrix}1\\\\-\\sigma_1\\end{bmatrix} u1​=[1σ1​​]u2​=[σ1​−1​]v1​=[σ1​1​]v2​=[1−σ1​​]
在对其进行单位化，也就是除以1+σ12\\sqrt{1+\\sigma_1^2}1+σ12​​.

OK！有了特征向量和权重,那么我们就可以用式子还原这个矩阵 $A$:
A=σ1u1v1T+σ2u2v2TA=\\sigma_1u_1v_1^T+\\sigma_2u_2v_2^T A=σ1​u1​v1T​+σ2​u2​v2T​111111111111111111111+
写成矩阵形式:
A=[u1u2][σ1σ2][v1Tv2T]A=\\begin{bmatrix}&\\\\u_1&u_2\\\\&\\end{bmatrix}\\begin{bmatrix}\\sigma_1&\\\\&\\sigma_2\\end{bmatrix}\\begin{bmatrix}v_1^T\\\\v_2^T\\end{bmatrix} A=​u1​​u2​​​[σ1​​σ2​​][v1T​v2T​​]
在处理实际图像时，大多数都是满秩的，使得SVD有意义的原因是我们可以近似替代。

二、SVD中的基和矩阵

SVD在线性代数中非常重要，因为解决了一个矩阵对角化的缺点：

• 对角化矩阵必须是一个方阵；
• 必须有矩阵维度的特征向量；
• 特征向量不一定是正交的；

这节课我们要学的分解就解决了这样一个问题，代价是我们需要两组特征向量 $u$ $v$，其中 $u$ 属于原矩阵的维数为行个数的空间，$v$属于原矩阵维数为列数的空间。事实上，这些基都涵盖在待分解矩阵 $A$的四个基本子空间中：

• u1,⋯,uru_1,\\cdots,u_ru1​,⋯,ur​ 是一组列空间上的正交基；
• ur+1,⋯,umu_{r+1},\\cdots,u_mur+1​,⋯,um​ 是一组左零空间上的正交基；
• v1,⋯,vrv_1,\\cdots,v_rv1​,⋯,vr​ 是一组行空间上的正交基；
• vr+1,⋯,vnv_{r+1},\\cdots,v_nvr+1​,⋯,vn​ 是一组零空间的正交基；

让人感到“巧合”的不光是这些基的正交性，更重要是它可将原矩阵对角化：
Av1=σ1u1Av2=σ2u2⋯Avr=σrur(1)Av_1=\\sigma_1 u_1\\quad Av_2=\\sigma_2 u_2\\quad\\cdots\\quad Av_r=\\sigma_ru_r \\tag{1} Av1​=σ1​u1​Av2​=σ2​u2​⋯Avr​=σr​ur​(1)
σ1,⋯,σr\\sigma_1,\\cdots,\\sigma_rσ1​,⋯,σr​ 是一组正数，它被称为奇异值。你可以把它理解为 AviAv_iAvi​的长度，这些奇异值可以写成对角矩阵形式，记为 $\Sigma$。
[σ1⋅⋅σr]\\begin{bmatrix} \\sigma_1&\\\\ & \\cdot&\\\\ &&\\cdot&\\\\ &&&\\sigma_r \\end{bmatrix} ​σ1​​⋅​⋅​σr​​​
这种将相同矩阵对角化的等式(1)可以写成：
AVr=UrΣrAV_r=U_r\\Sigma_r AVr​=Ur​Σr​
也就是：
A[v1⋯vr]=[u1⋯ur][σ1⋅⋅σr](2)A\\begin{bmatrix}v_1&\\cdots& v_r\\end{bmatrix}=\\begin{bmatrix}u_1&\\cdots& u_r\\end{bmatrix} \\begin{bmatrix} \\sigma_1&\\\\ & \\cdot&\\\\ &&\\cdot&\\\\ &&&\\sigma_r \\end{bmatrix}\\tag{2} A[v1​​⋯​vr​​]=[u1​​⋯​ur​​]​σ1​​⋅​⋅​σr​​​(2)
观察一下矩阵的维数情况：

• $A$ 是$m\times n$的矩阵
• $V$ 是$m\times m$的矩阵
• $U$ 是$n\times n$的矩阵
• $\Sigma$ 是$m\times n$的矩阵

接下来，我们考虑更加全面一些：
A[v1⋯vr⋯vn]=[u1⋯ur⋯un][σ1⋅⋅σr](3)A\\begin{bmatrix}v_1&\\cdots& v_r&\\cdots&v_n\\end{bmatrix}=\\begin{bmatrix}u_1&\\cdots& u_r&\\cdots&u_n\\end{bmatrix} \\begin{bmatrix} \\sigma_1&\\\\ & \\cdot&\\\\ &&\\cdot&\\\\ &&&\\sigma_r \\end{bmatrix}\\tag{3} A[v1​​⋯​vr​​⋯​vn​​]=[u1​​⋯​ur​​⋯​un​​]​σ1​​⋅​⋅​σr​​​(3)
这就是我们需要的奇异值分解：
a=UΣVT=u1σ1v1T+⋯+urσrvrTa=U\\Sigma V^T=u_1\\sigma_1v_1^T+\\cdots+u_r\\sigma_rv_r^T a=UΣVT=u1​σ1​v1T​+⋯+ur​σr​vrT​
证明略。