奇异值分解我写过一个简短的理解,记录于 https://www.jianshu.com/p/8c7dac32620f ,
这次又写一遍完全是因为《统计学习方法》的奇异值分解讲得太详细了,占了25页的篇幅,且大致翻看后面章节后发现奇异值分解的应用很多,因此决定对奇异值分解再重新学习一遍。
任意一个 矩阵,都可以表示为三个矩阵的乘积(因子分解)形式:
其中 是 阶正交矩阵、 是由降序排列的非负的对角线元素组成的 矩形对角阵、 是 阶正交矩阵。即这三个矩阵满足:
称为矩阵 的奇异值分解(singular value decomposition,SVD)。
奇异值分解基本定理 :若 为一个 实矩阵, ,则 的奇异值分解存在。
证明:
证明是构造性的,对给定矩阵,不妨设 。
(1)确定 和 。
矩阵 是 实矩阵,则 是 阶实对称矩阵,因而 的特征值都是实数,且存在一 阶正交实矩阵 实现 的对角化,使得 ,其中 是 阶对角矩阵,其对角线元素由 的特征值组成,且 的特征值都是非负的。事实上,令 是 的一个特征值, 是对应的特征向量,则:
于是:
假设正交矩阵 的列的排列使得对应特征值形成降序排列:
计算特征值平方根(实际就是矩阵 的奇异值):
设矩阵 的秩为 ,则矩阵 的秩也为 (通过证明 和 同解即可证明)。由于 是对称矩阵,它的秩等于正的特征值的个数(因为 和与其相似的对角矩阵 秩相等,而 对角元素是 的特征值)。所以:
从而:
令:
其中 为正特征值对应的特征向量组成的矩阵, 则为0特征值对应的特征向量组成的矩阵。从而 可以写成:
这就是矩阵 的奇异值分解中的正交矩阵 。
令:
于是 矩阵对角矩阵 可以表示为:
这就是矩阵 奇异值分解中的 。
(2)确定
令:
则有:
的列向量构成了一组标准正交基,因为:
因为 时, 和 正交。故有:
所以 的列向量构成了一组标准正交基。
若将 看成从 到 的线性变换,则 的列空间和 的值域 相同。因此 也是 的一组标准正交基。因为 (即 的零空间和 的正交补相同),故 的维数为 。
令 为 的一组标准正交基,并令:
则 构成了 的一组标准正交基。因此 就是 的奇异值分解中的 阶正交矩阵。
(3)证明
至此证明了矩阵 存在奇异值分解。
上述定理给出的奇异值分解 称为矩阵的 完全奇异值分解 。实际常用的是奇异值分解的紧凑形式和截断形式。 紧奇异值分解是与原始矩阵等秩的奇异值分解,截断奇异值分解是比原始矩阵低秩的奇异值分解。
紧奇异值分解定义 :
设有 实矩阵 ,其秩为 ,则称 为 的紧奇异值分解:
是 矩阵,由完全奇异值分解中 的前 列得到, 是 矩阵,由完全奇异值分解中 的前 列得到, 是 阶对角矩阵,由完全奇异值分解中 的前 个对角线元素得到。
截断奇异值分解定义:
设有 实矩阵 ,其秩为 ,且 ,则称 为 的截断奇异值分解:
是 矩阵,由完全奇异值分解中 的前 列得到, 是 矩阵,由完全奇异值分解中 的前 列得到, 是 阶对角矩阵,由完全奇异值分解中 的前 个对角线元素得到。
注意,紧奇异值分解完全还原原矩阵,截断奇异值分解近似还原原矩阵。因此在对矩阵数据进行压缩时,紧奇异值分解对应无损压缩,截断奇异值分解对应有损压缩。
从线性变换的角度理解奇异值分解, 矩阵表示从 维空间 到 维空间 的一个线性变换:
, , 和 分别是各自空间的向量。 线性变换可以分解为三个简单的变换:一个坐标系的旋转或反射变换、一个坐标轴的缩放变换、另一个坐标系的旋转或反射变换。 这就是奇异值分解的几何解释。
上图来自《统计学习方法》。我们可以很直观地看到奇异值分解的几何意义。
其实奇异值分解的计算过程已经蕴含在奇异值分解基本定理中了,对给定 矩阵 ,计算过程如下:
(1)计算 的特征值 和对应的特征值向量。
(2)将特征向量单位化,得到单位特征向量 构成 阶正交矩阵 :
(3)计算 的奇异值:
构造 矩阵 ,主对角线元素为奇异值,其余元素为 。
(4)对 前 个正奇异值,令:
得到:
求 零空间的一组标准正交基 ,令:
则:
这部分内容是我没有接触过的,我以前只知道SVD和PCA类似,都可以做降维(其实PCA是SVD的特殊情形),但并没有从矩阵近似和压缩的角度看待过SVD。这一部分内容证明了一个结论: 奇异值分解是在平方损失意义下对矩阵的最优近似。
首先定义 矩阵的平方损失函数 (也称为弗罗贝尼乌斯范数):
设矩阵 , ,定义矩阵 的平方损失函数为:
下面证明一个结论:
证明:
一般地,若 是 阶正交矩阵,则:
这是因为:
同理,若 是 阶正交矩阵,则:
因此:
即:
有了上述结论,我们接下来证明 奇异值分解是在平方损失意义下对矩阵的最优近似。
定理1 设矩阵 , ,设 为 中所有秩不超过 的矩阵集合, ,则存在一个秩为 的矩阵 ,使得:
称矩阵 为矩阵 在平方误差下的最优近似。
定理2 设矩阵 , ,有奇异值分解 ,并设 为 中所有秩不超过 的矩阵的集合, ,若秩为 的矩阵 满足:
则:
特别地,若 ,其中:
则:
定理2的具体证明过程见《统计学习方法》。