[人工智能]SVD分解

SVD分解

先来一道题开开胃
$W=\left[\begin{array}{lll}4& 0& 5\\ 0& 0& 5\end{array}\right]$ Find $W=U\Sigma V^T=\sqrt{{\lambda }_1}{u}_1{\left(v_1\right)}^T+\sqrt{{\lambda }_2}{u}_2{\left(v_2\right)}^T$

$C=W^{T}W=VD{V}^T=V{\Sigma }^T\Sigma V^T=\left(V{\Sigma }^T{U}^T\right)\left(U\Sigma V^T\right)$

$B=W{W}^T=UD{U}^T=U{\Sigma }^T\Sigma U^T=\left(U{\Sigma }^T{V}^T\right)\left(V\Sigma U^T\right)$

$B=\left[\begin{array}{lll}4& 0& 5\\ 0& 0& 5\end{array}\right]?\begin{array}{ll}4& 0\\ 0& 0\\ 5& 5\end{array}?=\left[\begin{array}{ll}41& 25\\ 25& 25\end{array}\right]=\left[\begin{array}{cc}0.81& ?0.59\\ 0.59& 0.81\end{array}\right]\left[\begin{array}{cc}59.2& 0\\ 0& 6.75\end{array}\right]\left[\begin{array}{cc}0.81& 0.59\\ ?0.59& 0.81\end{array}\right]$

求出特征值及特征向量

$\left[\begin{array}{lll}4& 0& 5\\ 0& 0& 5\end{array}\right]=\left[\begin{array}{cc}0.81& ?0.59\\ 0.59& 0.81\end{array}\right]\left[\begin{array}{ccc}7.70& 0& 0\\ 0& 2.60& 0\end{array}\right]?\begin{array}{ccc}0.42& 0& 0.91\\ ?0.91& 0& 0.42\\ 0& 1& 0\end{array}?$

$=7.70\left[\begin{array}{l}0.81\\ 0.59\end{array}\right]\left[\begin{array}{lll}0.42& 0& 0.91\end{array}\right]+2.6\left[\begin{array}{l}0.59\\ 0.81\end{array}\right]\left[\begin{array}{lll}?0.91& 0& 0.42\end{array}\right]$

$=\left[\begin{array}{lll}2.62& 0& 5.68\\ 1.91& 0& 4.12\end{array}\right]+\left[\begin{array}{ccc}1.38& 0& ?0.64\\ ?1.91& 0& 0.88\end{array}\right]$

奇异值分解(Singular Value Decomposition，以下简称SVD)是在机器学习领域广泛应用的算法，它不光可以用于降维算法中的特征分解，还可以用于推荐系统，以及自然语言处理等领域。是很多机器学习算法的基石。

1.回顾特征值和特征向量

首先回顾下特征值和特征向量的定义如下：

$Ax=\lambda x$

其中 $A$ 是一个 $n\times n$ 矩阵， $x$ 是一个 $n$ 维向量，则 $\lambda$ 是矩阵 $A$ 的一个特征值，而 $x$ 是矩阵 $A$ 的特征值 $\lambda$ 所对应的特征向量。

求出特征值和特征向量有什么好处呢？ 就是我们可以将矩阵 $A$ 特征分解。如果我们求出了矩阵 $A$ 的n个特征值 ${\lambda }_1\le {\lambda }_2\le \dots \le {\lambda }_n$，以及这 $n$ 个特征值所对应的特征向量 $w_1,w_2,\dots ,w_n$ ，

那么矩阵A就可以用下式的特征分解表示：
$A=W\Sigma W^{?1}$

其中 $W$ 是这 $n$ 个特征向量所张成的$n\times n$维矩阵，而 $\Sigma$ 为这$n$个特征值为主对角线的$n\times n$维矩阵。

一般我们会把$W$的这$n$个特征向量标准化，即满足${\Vert w_i\Vert }_2=1$ ，或者 $w_i^T{w}_i=1$，此时 $W$ 的 $n$ 特征向量为标准正交基，满足 $W^{T}W=I$ ，即 $W^T=W^{?1}$，也就是说 $W$ 为酉矩阵。

这样我们的特征分解表达式可以写成

$A=W\Sigma W^T$

注意到要进行特征分解，矩阵A必须为方阵。
那么如果A不是方阵，即行和列不相同时，我们还可以对矩阵进行分解吗？答案是可以，此时我们的SVD登场了。

2. SVD定义

SVD也是对矩阵进行分解，但是和特征分解不同，SVD并不要求要分解的矩阵为方阵。假设我们的矩阵A是一个m×n的矩阵，那么我们定义矩阵A的SVD为：

$A=U\Sigma V^T$

其中 $U$ 是一个 $m\times m$ 的矩阵， $\Sigma$ 是一个 $m\times n$ 的矩阵，除了主对角线上的元素以外全为$0$，主对角线上的每个元素都称为奇异值， $V$ 是一个 $n\times n$ 的矩阵。$U$和 $V$ 都是酉矩阵，即满足。

下图可以很形象的看出上面SVD的定义：

$U^{T}U=I,V^{T}V=I$

那么我们如何求出SVD分解后的$U,\Sigma ,V$这三个矩阵呢？

如果我们将$A$的转置和$A$做矩阵乘法，那么会得到$n\times n$的一个方阵 $A^{T}A$ 。既然$A^{T}A$是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：

$\left(A^{T}A\right)v_i={\lambda }_i{v}_i$

这样我们就可以得到矩阵 $A^{T}A$ 的$n$个特征值和对应的$n$个特征向量$v$了。将 $A^{T}A$ 的所有特征向量张成一个$n\times n$的矩阵$V$，就是我们SVD公式里面的$V$矩阵了。一般我们将$V$中的每个特征向量叫做$A$的右奇异向量。

如果我们将$A$和$A$的转置做矩阵乘法，那么会得到$m\times m$的一个方阵$A{A}^T$。既然 $A{A}^T$ 是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：
$\left(A{A}^T\right)u_i={\lambda }_i{u}_i$

这样我们就可以得到矩阵 $A{A}^T$ 的$m$个特征值和对应的$m$个特征向量$u$了。将 $A{A}^T$ 的所有特征向量张成一个$m\times m$的矩阵$U$，就是我们SVD公式里面的$U$矩阵了。一般我们将$U$中的每个特征向量叫做$A$的左奇异向量。

$U$和$V$我们都求出来了，现在就剩下奇异值矩阵$\Sigma$没有求出了.

由于$\Sigma$除了对角线上是奇异值其他位置都是0，那我们只需要求出每个奇异值$\sigma$就可以了。

我们注意到:

$A=U\Sigma V^T?AV=U\Sigma V^{T}V?AV=U\Sigma ?A{v}_i={\sigma }_i{u}_i?{\sigma }_i=A{v}_i/u_i$

这样我们可以求出我们的每个奇异值，进而求出奇异值矩阵$\Sigma$。

上面还有一个问题没有讲，就是我们说 $A^{T}A$ 的特征向量组成的就是我们SVD中的$V$矩阵，而$A{A}^T$的特征向量组成的就是我们SVD中的$U$矩阵，这有什么根据吗？这个其实很容易证明，我们以$V$矩阵的证明为例。

$A=U\Sigma V^T?A^T=V\Sigma U^T?A^{T}A=V\Sigma U^{T}U\Sigma V^T=V{\Sigma }^2{V}^T$

类似的方法可以得到$A{A}^T$的特征向量组成的就是我们SVD中的 $U$ 矩阵。

进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方，也就是说特征值和奇异值满足如下关系：
${\sigma }_i=\sqrt{{\lambda }_i}$

这样也就是说，我们可以用 ${\sigma }_i=\frac{A{v}_i}{u_i}$ 来计算奇异值，也可以通过求出 $A^{T}A$ 的特征值取平方根来求奇异值。

https://zhuanlan.zhihu.com/p/29846048