Singular value decomposition(SVD)详解

SVD,全称Singular Value Decomposition,奇异值分解。线性代数里重要的一种矩阵分解形式,可以看作特征值分解在 $m\times n $ 矩阵下的推广,其矩阵的特殊含义可以用来做处理线性相关。可用于矩阵降维,也可以利用性质解线性方程组。图像处理中,SVD可以用数据压缩,去噪,推荐系统。这里总结一下奇异值分解与特征值分解,还有SVD在线性最小二乘问题上的应用。

参考1:SVD与其意义

SVD的介绍与原理 - lanyizheng blog - CSDN博客:定义

奇异值分解 SVD 的数学解释 - Alan Lee - CSDN博客:求解过程与求解思路!

奇异值的物理意义是什么? - 知乎:郑宁这篇文章用图片的奇异值分解的例子阐述了奇异值的物理工程意义,很详细说明了对于SVD降维作用,值的一看。

AMS :: Feature Column from the AMS:fcarc-svd:美国数学协会的文章,在郑宁的文章中提到。非常全面的阐述,从特征值到奇异值,单看这一个基本足够了

人们是如何想到奇异值分解的? - 知乎:还是郑宁的文章,矩阵分解的动机有两个:(1)解线性方程组;(2)研究双线性形式。奇异值分解的动机为第二种

机器学习系列-SVD篇 - 知乎:开头有个实例,讲了一下NLP的文章分类中,词与文章的相关性矩阵的SVD分解三个矩阵的具体意义

参考2:SVD与最小二乘解

SVD分解及线性最小二乘问题 - 侯凯 - 博客园

SVD

定义

SVD是线代中对于实数矩阵和复数矩阵的分解,可以看作特征值分解从半正定矩阵推广到任意mxn矩阵

  • 正交矩阵:若一个方阵其行与列皆为正交的单位向量,则该矩阵为正交矩阵,且该矩阵的转置和其逆相等。两个向量正交的意思是两个向量的内积为 0
  • 正定矩阵:如果对于所有的非零实系数向量 $z$,都有 $z^TAz>0$,则称矩阵 $A$ 是正定的。正定矩阵的行列式必然$>0$, 所有特征值也必然$>0$ 。相对应的,半正定矩阵的行列式必然 $\ge$ 0。

SVD将一个矩阵M分解成三个矩阵的乘积。

$U,V$为正交矩阵(酉矩阵)。$\Sigma$ 称为奇异值矩阵,$\Sigma$只有主对角元素,其他元素为0,且对角元素从大到小排列且大于0,这些对角元素称为奇异值。即

图示:

image-20190220151651407

$U$ 和 $V$的列分别叫做 $A$ 的 左奇异向量(left-singular vectors)和 右奇异向量(right-singular vectors),$\Sigma$ 的对角线上的元素叫做 $A$ 的奇异值(singular values)。

求解

对一个矩阵进行SVD。假设矩阵$A$,满足 $A = U\Sigma V^T$ ,则有(1)式如下

注:$U,V$ 为酉矩阵,转置等于逆,$U^TU=V^TV=I$。

$\Sigma \Sigma ^T$ 与$\Sigma ^T \Sigma$,是方阵,对角线前 $r$ 个元素是奇异值的平方${\sigma_i}^2$,其余元素为0。

显然(1)式中矩阵$AA^T ,A^TA$可以看作为特征值分解

则:

  • $U$ 的列由 $AA^T$ 的单位化过的特征向量构成
  • $V$ 的列由 $A^TA$ 的单位化过的特征向量构成
  • $\Sigma $ 的对角元素来源于 $AA^T$ 或 $A^TA$的特征值的平方根,按从大到小的顺序排列

即求解方法为:

  1. 求 $AA^T​$ 的特征值和特征向量,用单位化的特征向量构成 $U​$
  2. 求 $A^TA$ 的特征值和特征向量,用单位化的特征向量构成 $V$
  3. 将 $AA^T$ 或者 $A^TA$ 的特征值的平方根,构成$ \Sigma$

几何含义与物理意义

参考文献讲的很详细,总结一下:

物理意义

奇异值往往对应着矩阵中隐含的重要信息,且重要性和奇异值大小正相关。每个矩阵 $A$ 都可以表示为一系列秩(rank)为1的“小矩阵”之和,奇异值则衡量了这些小矩阵对于$A$ 的权重。

SVD也可以写为(2),如下

其中,$u_i,v_i$分别是$m\times1,n\times1$的矩阵,$\sigma_i$是奇异值。

实例1:图像压缩

对于一张图像 $A$ 进行SVD,取前k<r项生成新的图像,则会得到一张较为模糊,但是可识别的图像$A_k$。

对于原图像,所需空间为$m\times n$;对于$A_k$,有k个$u_i,v_i$,则所需空间为$(m+n)\times k$。令m=450,n=333,k=50,此时所需空间仅为原图的26%。

即$A_k$为在损失精度的情况下对于图像 $A$ 进行了压缩。

实例2:图像去噪

如果一幅图像包含噪声,我们有理由相信那些较小的奇异值由噪声引起。

对图像进行SVD,在(2)中,令所有较小的奇异值$\sigma_i=0$,就可以达到去噪的效果。

实例3:NLP文章分类

用一个矩阵A来描述m篇文章和n个词的关联性(Co-occurrence Matrix)。

SVD分解三个矩阵的物理含义:

  • 第一个矩阵$U$中的每一行表示意思相关的一类词,其中的每个非零元素表示这类词中每个词的重要性(或者说相关性),数值越大越相关。
  • 第三个矩阵$V^T$中的每一列表示同一主题一类文章,其中每个元素表示这类文章中每篇文章的相关性。

  • 第二个矩阵$\Sigma$则表示类词和文章之间的相关性。因此,我们只要对关联矩阵A进行一次奇异值分解,我们就可以同时完成了近义词分类和文章的分类。(同时得到每类文章和每类词的相关性)。

image-20190220171853350

几何意义

说到SVD的几何意义,有必要回顾一下特征值的意义

特征值与特征向量

特征分解_百度百科

我们知道

n维非零向量$\vec v$是矩阵 $A\in \mathbb R^{n\times n}$ 的特征向量,当且仅当

其中 $\lambda$ 是一标量,称为特征向量$\vec v$ 对应的特征值

由上述式子可定义特征多项式$p(\lambda)$

上式亦称为矩阵的特征方程。特征多项式是关于未知数 $\lambda$ 的 n 次多项式。由代数基本定理,特征方程有 n 个解。这些解的解集也就是特征值的集合,有时也称为(Spectrum)。

矩阵的特征分解

注意:只有可对角化矩阵才可以作特征分解,即满秩方阵$A\in\mathbb R^{n\times n}$。

特殊矩阵的特征分解

  • 对称矩阵:对称矩阵的特征向量都可以正交单位化而得到一组正交且模为 1 的向量

解释

来自参考[AMS]

含义是:将$A$ 看作一个线性变换矩阵,特征向量被施以线性变换$A$, 只会使向量伸长或缩短而其方向不被改变。

例如:

对于一个对角矩阵

image-20190221101544954

对应的线性变换是

image-20190221101637021

这种变换的效果如下所示:平面水平拉伸3倍,而没有垂直变化。

image-20190221101715177

现在我们看一个对称矩阵

image-20190221101756745

这种变换的效果如下所示:

image-20190221101815032

将坐标旋转45度

image-20190221102232645

此时这组新的坐标基,使线性变换在这组基下仅有拉伸变换而没有旋转变换。对于对称矩阵而言,可以证明在域中旋转网格,来使得矩阵对应的线性变换在这组基下为一个仅在基方向上的拉伸变换

数学化来说,就是对于一个n维对称矩阵$M$,存在一组正交向量 $V = \{v_1,v_2,\dots,v_n\}$,使得$Mv_i$是$v_i$的标量倍数

这也就是特征值的定义,其中 $\lambda_i$ 是一标量,称为特征向量 $v_i$ 对应的特征值

容易验证的一个重要事实是:对应于不同特征值的对称矩阵的特征向量是正交的

If we use the eigenvectors of a symmetric matrix to align the grid, the matrix stretches and reflects the grid in the same way that it does the eigenvectors.

再考虑一般非对称矩阵

image-20190221102757525

变换如下

image-20190221104416306

此时找不到一组正交网格是的矩阵作用在该正交网格上后只有拉伸变换(本质上是一般非对称矩阵无法在实数域上对角化),但是如果允许旋转变换,还是可以的

image-20190221105136499

image-20190221105147750

这也是特征值的几何意义。

特征值分解是特殊的奇异值分解。上述可以看作 2 $\times$ 2 矩阵的奇异值分解。for any 2$\times $2 matrix, we may find an orthogonal grid that is transformed into another orthogonal grid.

奇异值的几何意义

奇异值分解的几何含义是:对于任何一个矩阵,要找到一组正交的单位向量族,使得矩阵作用在族上后得到的新的向量族保持正交。

奇异值的含义:变换后新的向量族的长度。

我们将使用向量表达这一事实:当矩阵 $M$ 作用在正交单位向量 $v_1$ 和 $v_2$ 上,向量 $Mv_1$ 和 $Mv_2$ 是正交的。

image-20190221105725399

令$u_1,u_2$ 分别是$Mv_1,Mv_2$ 方向上的单位向量,$\sigma_1,\sigma_2$ 分别是$Mv_1,Mv_2$ 的长度(标量),即

image-20190221112855358

整理得:由$v_1,v_2$正交

也可写作

这就是矩阵 $M$ 的 奇异值分解

其中 $U$ 是矩阵,其列是矢量 $u_1$ 和 $u_2$ ,$\Sigma$ 是对角矩阵,其对角线上元素是$\sigma_1,\sigma_2$,$V$ 是列是 $v_1,v_2$ 的矩阵。 矩阵$V$ 上的上标 $T$ 表示 $V$ 的矩阵转置。

奇异值$\sigma_1,\sigma_2$ 分别是$Mv_1,Mv_2$ 的长度

This shows how to decompose the matrix $M$ into the product of three matrices: $V$ describes an orthonormal basis in the domain, and $U$ describes an orthonormal basis in the co-domain, and $ \Sigma $ describes how much the vectors in $V$ are stretched to give the vectors in $U$. [AMS]

【这显示了如何将矩阵M分解为三个矩阵的乘积:V描述了域中的标准正交基,U描述了co-domain中的标准正交基,Σ描述了V中的向量被拉伸到多少以给出 在U的矢量】

另一种直观的几何解释

image-20190221120949755

推广到多维一般情况:一般矩阵 $A$ 将单位球 $||x||_2=1$ 变换为超椭球面

那么 $A$ 的每个奇异值恰好式超椭球面的每条半轴的长度

image-20190221120934686

总结

SVD的几何意义实质上就是:对于一个线性变换A,寻找一组空间下的基V,使得变换后的基也是正交的,奇异值$\Sigma$ 就是变换后的基的长度,U是单位化后的变化后的基。

实际上这就是特征值求解的推广

要注意的是:奇异值分解 U,V是不同空间维度的

奇异值代表的是变化后的基的长度,这也就很容易理解为什么奇异值能够用来做压缩与去噪。通过保留重要的分量部分(奇异值大的向量),舍去奇异值小的部分,从而达到目的。这也是PCA可以用SVD来实现的原因。

补充:SVD与最小二乘解

它们之间的联系的本质就是一组空间基在另外一个不同维度的投影。

最小二乘法

最小二乘法是机器学习的基本方法。这里先简单回顾一下。

$m$ 个方程求解 $n$ 个未知数,存在三种情况:

  1. $m=n$且 $A$ 非奇异,则存在唯一解,$x=A^{-1}b$。
  2. $m>n$ 且 $\text{rank}(A)=n$ ,约束条件数量大于未知数个数(超定问题)。
  3. $m<n$ ,负定问题。

对于超定问题,此时解不存在,从而转化为最小二乘问题,几何上可以看作曲线拟合问题:求曲线参数,使曲线与样本点的残差最小。

线性最小二乘问题,数学表示如下:

这是一个线性优化问题

$L(x)$ 是凸函数,令其导数=0,得到正规方程

一般解:(注意会存在 $A^TA$ 不可逆的情况)

这个解说明了:向量 $x$ 相当于m维向量$b$ 在 n维空间下的投影,$(A^TA)^{-1}A^T$ 则是那个投影变换。这也就是最小二乘法的几何意义。

SVD解最小二乘问题

对于矩阵A进行奇异值分解

令 $U_n$ 为 $U$ 的前n列矩阵,即 $U = [U_n,\bar U]$,则:

要取得最小值 $||\bar U^Tb||$ 当且仅当:

即求出未知数的最小二乘解$x^*$