矩阵的奇异值分解(singular value decomposition,简称SVD)是线性代数中很重要的内容,并且奇异值分解过程也是线性代数中相似对角化分解(也被称为特征值分解,eigenvalue decomposition,简称EVD)的延伸。因此,以下将从线性代数中最基础的矩阵分解开始讲起,引出奇异值分解的定义,并最终给出奇异值分解的低秩逼近问题相关的证明过程。 1 线性代数中的矩阵分解我们在学习线性代数时,就已经接触了线性代数中的两个重要定理,即对角化定理和相似对角化定理,在这里,我们先简单地回顾一下这两个定理。另外,在接下来的篇幅里,我们所提到的矩阵都是指由实数构成的矩阵,即实矩阵。 给定一个大小为 的矩阵 (是方阵),其对角化分解可以写成 ![A=U\Lambda U^{-1}]()
其中, 的每一列都是特征向量, 对角线上的元素是从大到小排列的特征值,若将 记作 ,则 ![AU=A\left(\vec{u}_1,\vec{u}_2,...,\vec{u}_m\right)=\left(\lambda_1 \vec{u}_1,\lambda_2 \vec{u}_2,...,\lambda_m \vec{u}_m\right)]()
![=\left(\vec{u}_1,\vec{u}_2,...,\vec{u}_m\right) \left[ \begin{array}{ccc} \lambda_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \lambda_m \\ \end{array} \right]]()
![\Rightarrow AU=U\Lambda \Rightarrow A=U\Lambda U^{-1}]()
更为特殊的是,当矩阵 是一个对称矩阵时,则存在一个对称对角化分解,即 ![A=Q\Lambda Q^T]()
其中, 的每一列都是相互正交的特征向量,且是单位向量, 对角线上的元素是从大到小排列的特征值。 当然,将矩阵 记作 ,则矩阵 也可以写成如下形式: ![A=\lambda_1 \vec{q}_1\vec{q}_1^T+\lambda_2 \vec{q}_2\vec{q}_2^T+...+\lambda_m \vec{q}_m\vec{q}_m^T]()
举一个简单的例子,如给定一个大小为 的矩阵 ,根据 求得特征值为 , ,相应地, , ,则 .这样,我们就很容易地得到了矩阵 的对称对角化分解。 2 奇异值分解的定义在上面,对于对称的方阵而言,我们能够进行对称对角化分解,试想:对称对角化分解与奇异值分解有什么本质关系呢? 当给定一个大小为 的矩阵 ,虽然矩阵 不一定是方阵,但大小为 的 和 的 却是对称矩阵,若 , ,则矩阵 的奇异值分解为 ![A=P\Sigma Q^T]()
其中,矩阵 的大小为 ,列向量 是 的特征向量,也被称为矩阵 的左奇异向量(left singular vector);矩阵 的大小为 ,列向量 是 的特征向量,也被称为矩阵 的右奇异向量(right singular vector);矩阵 大小为 ,矩阵 大小为 ,两个矩阵对角线上的非零元素相同(即矩阵 和矩阵 的非零特征值相同,推导过程见附录1);矩阵 的大小为 ,位于对角线上的元素被称为奇异值(singular value)。 接下来,我们来看看矩阵 与矩阵 和矩阵 的关系。令常数 是矩阵 的秩,则 ,当 时,很明显,矩阵 和矩阵 的大小不同,但矩阵 和矩阵 对角线上的非零元素却是相同的,若将矩阵 (或矩阵 )对角线上的非零元素分别为 ,其中,这些特征值也都是非负的,再令矩阵 对角线上的非零元素分别为 ,则 ![\sigma_1=\sqrt{\lambda_1},\sigma_2=\sqrt{\lambda_2},...,\sigma_k=\sqrt{\lambda_k}]()
即非零奇异值的平方对应着矩阵 (或矩阵 )的非零特征值,到这里,我们就不难看出奇异值分解与对称对角化分解的关系了,即我们可以由对称对角化分解得到我们想要的奇异值分解。 为了便于理解,在这里,给定一个大小为 的矩阵 ,虽然这个矩阵是方阵,但却不是对称矩阵,我们来看看它的奇异值分解是怎样的。 由 进行对称对角化分解,得到特征值为 , ,相应地,特征向量为 , ;由 进行对称对角化分解,得到特征值为 , ,相应地,特征向量为 , 。取 ,则矩阵 的奇异值分解为 ![A=P\Sigma Q^T=\left(\vec{p}_1,\vec{p}_2\right)\Sigma \left(\vec{q}_1,\vec{q}_2\right)^T]()
.
若矩阵 不再是一个方阵,而是一个大小为 的 ,由 得到特征值为 , ,特征向量为 , , ;由 得到特征值为 , ,特征向量为 , ,令 (注意:矩阵 大小为 ),此时,矩阵 的奇异值分解为 ![A=P\Sigma Q^T=\left(\vec{p}_1,\vec{p}_2\right)\Sigma \left(\vec{q}_1,\vec{q}_2\right)^T]()
.
比较有趣的是,假设给定一个对称矩阵 ,它是对称矩阵,则其奇异值分解是怎么样的呢? 分别计算 和 ,我们会发现, ,左奇异向量和右奇异向量构成的矩阵也是相等的,即 ,更为神奇的是,该矩阵的奇异值分解和对称对角化分解相同,都是 。这是由于对于正定对称矩阵而言,奇异值分解和对称对角化分解结果相同。 3 奇异值分解的低秩逼近在对称对角化分解中,若给定一个大小为 的矩阵 ,很显然,矩阵 的秩为 ,特征值为 , , ,对应的特征向量分别为 , , ,考虑任意一个向量 ,则 ![A\vec{v}=A\left(2\vec{q}_1+4\vec{q}_2+6\vec{q}_3\right)]()
![=2\lambda_1\vec{q}_1+4\lambda_2\vec{q}_2+6\lambda_3\vec{q}_3=60\vec{q}_1+80\vec{q}_2+6\vec{q}_3]()
在这里,我们会发现,即使 是一个任意向量,用矩阵 去乘以 的效果取决于 较大的特征值及其特征向量,类似地,在奇异值分解中,较大的奇异值会决定原矩阵的“主要特征”,下面我们来看看奇异值分解的低秩逼近(有时也被称为截断奇异值分解)。需要说明的是,接下来的部分是从文献《A Singularly Valuable Decomposition: The SVD of a Matrix》整理而来的。 给定一个大小为 的矩阵 ,由于 可以写成 ![A=\sum_{i=1}^{k}{\sigma_i\vec{p}_i\vec{q}_i^T}=\sigma_1\vec{p}_1\vec{q}_1^T+\sigma_2\vec{p}_2\vec{q}_2^T+...+\sigma_k\vec{p}_k\vec{q}_k^T]()
其中,向量 之间相互正交,向量 之间也相互正交,由内积 (有兴趣的读者可以自行推算)得到矩阵 的F-范数的平方为 ![=\sigma_1^2+\sigma_2^2+...+\sigma_k^2=\sum_{i=1}^{r}{\sigma_i^2}]()
知道了矩阵 的F-范数的平方等于其所有奇异值的平方和之后,假设 是矩阵 的一个秩一逼近(rank one approximation),那么,它所带来的误差则是 ( 是矩阵 的秩),不过如何证明 是最好的秩一逼近呢? 由于 (证明过程见附录2),令 ,其中, 是一个正常数,向量 和 分别是大小为 和 的单位向量,则 ![=||\Sigma||_F^2+\alpha^2-2\alpha \left\Sigma, \vec x\vec y^T\right]()
单独看大小为 的矩阵 和 的内积 ,我们会发现, ![\left\Sigma, \vec x\vec y^T\right=\sum_{i=1}^{k}{\sigma_i x_i y_i}\leq \sum_{i=1}^{k}{\sigma_i\left| x_i\right|\left| y_i\right|}]()
![\leq \sigma_1||\vec x^*||\cdot ||\vec y^*||\leq \sigma_1||\vec x||\cdot ||\vec y||=\sigma_1]()
其中,需要注意的是, 分别是向量 和 的第 个元素;向量 的大小为 ,向量 的大小也为 ,另外,以 为例, 是向量的模,则 (残差矩阵的平方和)为 ![=||\Sigma||_F^2+\left(\alpha-\sigma_1\right)^2-\sigma_1^2]()
当且仅当 时, 取得最小值 ,此时,矩阵 的秩一逼近恰好是 . 当然,我们也可以证明 是矩阵 的最佳秩一逼近,以此类推, 是矩阵 的最佳秩一逼近。由于矩阵 的秩为 ,这样,我们可以得到矩阵 的最佳秩 逼近(rank- approximation),即 .
这里得到的矩阵 的大小为 ,矩阵 的大小为 ,矩阵 的大小为 ,矩阵 可以用 来做近似。 用低秩逼近去近似矩阵 有什么价值呢?给定一个很大的矩阵,大小为 ,我们需要存储的元素数量是 个,当矩阵 的秩 远小于 和 ,我们只需要存储 个元素就能得到原矩阵 ,即 个奇异值、 个左奇异向量的元素和 个右奇异向量的元素;若采用一个秩 矩阵 去逼近,我们则只需要存储更少的 个元素。因此,奇异值分解是一种重要的数据压缩方法。 另外,关于奇异值分解的应用将在该系列后续文章中进行详述。 --------------------------------------------------------------- 附录1:相关链接:Largest eigenvalues of AA;#x27; equals to A;#x27;A,截图如下: ![]() 附录2:求证: ,其中, , . 证明:![||P\Sigma Q^T-A_1||_F^2]() ![=trace \left(\left(P\Sigma Q^T-A_1\right)\left(P\Sigma Q^T-A_1\right)^T\right)]()
![=trace \left(\left(P\Sigma Q^T-A_1\right)QQ^T\left(P\Sigma Q^T-A_1\right)^T\right)]()
![=trace \left(\left(P\Sigma -A_1Q\right)\left(\Sigma^T P^T-Q^TA_1^T\right)\right)]()
![=trace \left(\left(\Sigma^T P^T-Q^TA_1^T\right)\left(P\Sigma -A_1Q\right)\right)]()
![=trace \left(\left(\Sigma^T P^T-Q^TA_1^T\right)PP^T\left(P\Sigma -A_1Q\right)\right)]()
![=trace \left(\left(\Sigma^T -Q^TA_1^TP\right)\left(\Sigma -P^TA_1Q\right)\right)]()
. 好书推荐一、《矩阵计算》被誉为数值计算领域的“圣经”,该书以线性代数为基础,系统地介绍了矩阵计算的基本理论和方法,并附有大量算法、习题和参考文献,据谷歌学术 (Google Scholar) 引用数据显示,该书已被引用超过7.5万次,是一本不可多得的好书。目前,人民邮电出版社已获得授权在国内出版,并发行了中文版与英文版。 二、机器学习领域经典中文著作《机器学习》,南京大学周志华教授西瓜书。
|