SVD性质

矩阵的奇异值分解一定存在，但不唯一；
奇异值唯一，但矩阵$U$ $V$ 不唯一；
矩阵$A$ $\sum$ 秩相等，等于正奇异值数量（包含重复的奇异值）；

SVD具体介绍

特征值、特征向量、特征值分解

特征值分解和奇异值分解(Singular Value Decomposition)在机器学习中都是很常见的矩阵分解算法。两者有着很紧密的关系，特征值分解和奇异值分解的目的都是一样，就是提取出一个矩阵最重要的特征。

特征值、特征向量

如果一个向量$v$ 矩阵$A$ 特征向量，将一定可以表示成下面的形式：$Av=\lambda v$ 中，$\lambda$ 特征向量$v$ 应的特征值，一个矩阵的一组特征向量是一组正交向量。

思考：为什么一个向量和一个数相乘的效果与一个矩阵和一个向量相乘的效果是一样的呢？

答案：矩阵$A$ 向量$v$ 乘，本质上是对向量$v$ 行了一次线性变换（旋转或拉伸），而该变换的效果为常数$\lambda$ 以向量$v$。当我们求特征值与特征向量的时候，就是为了求矩阵A能使哪些向量（特征向量）只发生伸缩变换，而变换的程度可以用特征值$\lambda$ 示。

特征值与特征向量的几何意义

一个矩阵其实就是一个线性变换，因为一个矩阵乘以一个向量后得到的向量，其实就相当于将这个向量进行了线性变换。比如说下面的这个矩阵：
$$
M=
\begin{bmatrix}
3 & 0\
0 & 1
\end{bmatrix}
$$
它其实对应的线性变换如下图所示：

因为这个矩阵M乘以一个向量$(x,y)$ 结果是：

$$
\begin{bmatrix}
3 & 0\
0 & 1
\end{bmatrix}
\begin{bmatrix}
x\
y
\end{bmatrix}

\begin{bmatrix}
3x\
y
\end{bmatrix}
$$

上面的矩阵是对称的，所以这个变换是一个对x、y轴的方向一个拉伸变换（每一个对角线上的元素将会对一个维度进行拉伸变换，当值大于1时是拉伸，当值小于1时是缩短），如图2所示。当矩阵不是对称的时候，假如说矩阵是下面的样子：

$$
M=
\begin{bmatrix}
1 & 1\
0 & 1
\end{bmatrix}
$$

它所描述的变换是下面的样子：

这其实是在平面上对一个轴进行的拉伸变换，如图3蓝色的箭头所示，蓝色的箭头是一个最主要的变换方向（变换的方向可能不止一个）。如果想要描述好一个变换，那我们就需要描述好这个变换主要的变化方向。

特征值分解

对于矩阵$A$，有一组特征向量$v$，将这组向量进行正交化单位化，就能得到一组正交单位向量。特征值分解，就是将矩阵$A$ 解为如下式：
$$
A=Q\sum Q^{-1}
$$
其中，$Q$ 矩阵$A$ 特征向量组成的矩阵，$\sum$ 是一个对角阵，对角线上的元素就是特征值。

我们来分析一下特征值分解的式子，分解得到的$\sum$ 阵是一个对角矩阵，里面的特征值是由大到小排列的，这些特征值所对应的特征向量就是描述这个矩阵变换方向（从主要的变化到次要的变化排列）。

当矩阵是高维的情况下，那么这个矩阵就是高维空间下的一个线性变换，这个线性变换可能没法通过图片来表示，但是可以想象，这个变换也同样有很多的变化方向，我们通过特征值分解得到的前$N$ 特征向量，就对应了这个矩阵最主要的$N$ 变化方向。我们利用这前$N$ 变化方向，就可以近似这个矩阵变换。也就是之前说的**：提取这个矩阵最重要的特征。**

总结：特征值分解可以得到特征值与特征向量，特征值表示的是这个特征到底有多么重要，而特征向量表示这个特征是什么，可以将每一个特征向量理解为一个线性的子空间，我们可以利用这些线性的子空间干很多事情。不过，特征值分解也有很多的局限，比如说变换的矩阵必须是方阵。

特征值分解的例子

这里我们用一个简单的方阵来说明特征值分解的步骤。我们的方阵$A$ 义为：
$$
A=
\begin{bmatrix}
-1 & 1 & 0\
-4 & 3 & 0\
1 & 0 & 2
\end{bmatrix}
$$
首先，由方阵A的特征方程，求出特征值。
$$
\begin{vmatrix}
A-\lambda E
\end{vmatrix}

\begin{vmatrix}
-1-\lambda & 1 & 0\
-4 & 3-\lambda & 0\
1 & 0 & 2-\lambda
\end{vmatrix}
=(2-\lambda)
\begin{vmatrix}
-1-\lambda & 1 \
-4 & 3-\lambda \
\end{vmatrix}
=(2-\lambda)(\lambda - 1)^2=0
$$
特征值为$\lambda = 2,1$（重数是2)。

然后，把每个特征值$\lambda$ 入线性方程组$(A-\lambda E)x = 0$，求出特征向量。

当$\lambda = 2$ ，解线性方程组$(A-2E)x = 0$。
$$
(A-2E)=
\begin{pmatrix}
-3 & 1 & 0\
-4 & 1 & 0\
1 & 0 &0
\end{pmatrix}
\to
\begin{pmatrix}
1 & 0 & 0\
0 & 1 & 0\
0 & 0 &0
\end{pmatrix}
$$
解得$x_1 = 0, x_2 = 0$ 征向量为：$p_1 = \begin{pmatrix} 0 \0 \1\end{pmatrix}$

当$\lambda$=1时，解线性方程组$(A-E)x = 0$
$$
(A-E)=
\begin{pmatrix}
-2 & 1 & 0\
-4 & 2 & 0\
1 & 0 &1
\end{pmatrix}
\to
\begin{pmatrix}
1 & 0 & 1\
0 & 1 & 2\
0 & 0 &0
\end{pmatrix}
$$
$x_1 + x_2 = 0, x_2 + 2x_3 = 0$。特征向量为：$p_1 = \begin{pmatrix} -1 \-2 \1\end{pmatrix}$.

最后，方阵$A$ 特征值分解为：
$$
A=Q\sum Q^{-1}
\begin{pmatrix}
0 & -1 & -1\
0 & -2 & -2\
1 & 1 & 1
\end{pmatrix}
\begin{pmatrix}
2 & 0 & 0\
0 & 1 & 0\
0 & 0 &1
\end{pmatrix}
\begin{pmatrix}
0 & -1 & -1\
0 & -2 & -2\
1 & 1 &1
\end{pmatrix}^{-1}
$$

SVD分解

特征值分解矩阵的缺点

我们前面讲了很多特征值、特征向量和特征值分解，而且基于我们以前学习的线性代数知识，利用特征值分解提取特征矩阵是一个容易理解且便于实现的方法。但是为什么还存在奇异值分解呢？特征值分解最大的问题是只能针对方阵，即$n*n$ 矩阵。而在实际的应用中，我们分解的大部分都不是方阵。

奇异值分解

奇异值分解是一个能适用于任意矩阵的一种分解的方法，对于任意矩阵$A$ 是存在一个奇异值分解：$A=U\sum V^T$

假设 $A$ 是一个 $mn$ 的矩阵，那么得到的$U$ 一个$mm$ 方阵，$U$ 面的正交向量被称为左奇异向量。$\sum$ 一个$mn$ 矩阵，$\sum$ 了对角线其它元素都为0，对角线上的元素称为奇异值。$V^T$ $V$ 转置矩阵，是一个$nn$ 矩阵，它里面的正交向量被称为右奇异值向量。而且一般来讲，我们会将 $\sum$ 上的值按从大到小的顺序排列。

思考：虽说上面奇异值分解等式成立，但是如何求得左奇异向量、右奇异向量和奇异值呢？

答案：由上面的奇异值分解等式，我们是不知道如何拆分矩阵$A$ 。我们可以把奇异值和特征值联系起来。

首先，我们用矩阵$A$ 转置乘以$A$，得到一个方阵，用这样的方阵进行特征分解，得到的特征值和特征向量满足下面的等式：$(A^TA)v_i = \lambda_iv_i$。这里的$v_i$ 是我们要求的右奇异向量。

其次，我们将$A$ $A$ 转置做矩阵的乘法，得到一个方阵，用这样的方阵进行特征分解，得到的特征和特征向量满足下面的等式：$(AA^T)u_i = \lambda_iu_i$。这里的$u_i$ 是左奇异向量。

思考：上面我们说$A^TA$ 的特征向量组成的矩阵就是我们SVD中的$V$ 阵，而$AA^T$ 特征向量组成的就是我们SVD中的$U$ 阵，这有什么根据么?我们来证明一下，以$V$ 阵的证明为例。
$$
A^TA=(U\sum V^T)^T(U\sum V^T)=V(\sum) ^TU^TU\sum V^T=V(\sum) ^2V^T=V(\sum) ^2V^{-1}
$$
因为$V$ 标准正交基，所以$V^T = V^{-1}$，进而推得$A^TA = V(\sum) ^2V^{-1}$。上式证明中使用了$U^TU = I, \sum^T\sum = (\sum)^2$。而又有$A^TA$ 一个对称的半正定矩阵,它可以通过特征值分解为（ $\Lambda$ 对角化特征值， $Q$ 特征向量）：
$$
A^TA=Q\Lambda Q^{-1}
$$
可以看到上下两个形式保持了一致，当限定了特征值的顺序后，这样的组合是唯一的，所以 $V$ $A^TA$ 特征向量，奇异值和特征值是平方关系
$$
V = Q\
\Lambda = (\sum)^2
$$
补充定义：
$$
U\in M_n(R)满足U^TU = I(单位矩阵),则U是实正交矩阵。
$$
此外，我们还可以得到奇异值，奇异值求法有两种：

a) 第一种：
$$
A = U \sum V^T \to AV = U\sum V^TV \to AV = U\sum \to Av_i = \sigma _i u_i \to\sigma_i = \frac{Av_i}{u_i}
$$
b)第二种：

通过上面证明，我们还可以看出，特征值矩阵等于奇异值矩阵的平方，也就是说特征值和奇异值满足如下关系：
$$
\sigma_i = \sqrt{\lambda_i}
$$
这里的$\sigma_i$ 是奇异值，奇异值$\sigma_i$ 特征值类似，在矩阵$\sum$ 也是从大到小排列。

思考：我们已经知道如何用奇异值分解任何矩阵了，那么问题又来了，一个$mn$ 矩阵$A$，你把它分解成$mm$ 矩阵$U$、$mn$ 矩阵$\sum$ $nn$ 矩阵$V^T$。这三个矩阵中任何一个的维度似乎一点也不比$A$ 维度小，而且还要做两次矩阵的乘法，并且我们知道矩阵乘法的时间复杂度为$O(n^3)$。那奇异值分解到底要怎么做呢？

答案：在奇异值分解矩阵中 $\sum$ 里面的奇异值按从大到小的顺序排列，奇异值$\sigma_i$ 大到小的顺序减小的特别快。在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上。也就是说，剩下的90%甚至99%的奇异值几乎没有什么作用。因此，我们可以用前面$r$ 大的奇异值来近似描述矩阵，于是奇异值分解公式可以写成如下：
$$
A_{mn}\approx U_{mr}(\sum) {r*r}V{r*n}^T
$$
其中$r$ 一个远远小于$m$ $n$ 数，右边的三个矩阵相乘的结果将会是一个接近$A$ 矩阵。如果$r$ 接近于$n$，则相乘的结果越接近于$A$。如果$r$ 取值远远小于$n$，从计算机内存的角度来说，右边三个矩阵的存储内存要远远小于矩阵$A$ 。所以在奇异值分解中 $r$ 的取值很重要，就是在计算精度和时间空间之间做选择。

SVD计算举例

这里我们用一个简单的矩阵来说明奇异值分解的步骤。我们的矩阵A定义为：
$$
A=
\begin{pmatrix}
0 & 1 \
1 & 1\
1 & 0
\end{pmatrix}
$$
首先，我们先求出$A^TA$ $AA^T$
$$
A^TA=
\begin{pmatrix}
0 & 1 & 1\
1 & 1 & 0\
\end{pmatrix}
\begin{pmatrix}
0 & 1\
1 & 1\
1 & 0
\end{pmatrix}

\begin{pmatrix}
2 & 1\
1 & 2\
\end{pmatrix}\

AA^T=
\begin{pmatrix}
0 & 1\
1 & 1\
1 & 0
\end{pmatrix}
\begin{pmatrix}
0 & 1 & 1\
1 & 1 & 0\
\end{pmatrix}

\begin{pmatrix}
1 & 1 & 0\
1 & 2 & 1\
0 & 1 & 1
\end{pmatrix}
$$

然后，求出 $A^{T} A$ 和 $A A^{T}$ 的特征值和特征向量： $A^{T} A$ 的特征值和特征向量：

$$
\lambda_{1}=3 ; \quad v_{1}=\binom{\frac{1}{\sqrt{2}}}{\frac{1}{\sqrt{2}}} ; \quad \lambda_{2}=1 ; \quad v_{2}=\binom{\frac{-1}{\sqrt{2}}}{\frac{1}{\sqrt{2}}} ;
$$

$A A^{T}$ 的特征值和特征向量：
$$
\lambda_{1}=3 ; \quad u_{1}=\left(\begin{array}{c}\frac{1}{\sqrt{6}} \\frac{2}{\sqrt{6}} \\frac{1}{\sqrt{6}}\end{array}\right) ; \quad \lambda_{2}=1 ; \quad u_{2}=\left(\begin{array}{c}\frac{1}{\sqrt{2}} \0 \\frac{-1}{\sqrt{2}}\end{array}\right) ; \quad \lambda_{3}=0 ; \quad u_{3}=\left(\begin{array}{c}\frac{1}{\sqrt{3}} \\frac{-1}{\sqrt{3}} \\frac{1}{\sqrt{3}}\end{array}\right) ;
$$

其次，我们利用 $A v_{i}=\sigma_{i} u_{i}, i=1,2$ 求奇异值：
$$
\begin{array}{l}\left(\begin{array}{ll}0 & 1 \1 & 1 \1 & 0\end{array}\right)\binom{\frac{1}{\sqrt{2}}}{\frac{1}{\sqrt{2}}}=\sigma_{1}\left(\begin{array}{c}\frac{1}{\sqrt{6}} \\frac{2}{\sqrt{6}} \\frac{1}{\sqrt{6}}\end{array}\right) \Rightarrow \sigma_{1}=\sqrt{3} \\left(\begin{array}{ll}0 & 1 \1 & 1 \1 & 0\end{array}\right)\binom{\frac{-1}{\sqrt{2}}}{\frac{1}{\sqrt{2}}}=\sigma_{2}\left(\begin{array}{c}\frac{1}{\sqrt{2}} \0 \\frac{-1}{\sqrt{2}}\end{array}\right) \Rightarrow \sigma_{2}=1\end{array}
$$
当然，这一步也可以用 $\sigma_{i}=\sqrt{\lambda_{i}}$ 直接求出奇异值为 $\sqrt{3}$ 和1。
最后，我们得到 $A$ 的奇异值分解为:

$$
A=U \Sigma V^{T}=\left(\begin{array}{ccc}\frac{1}{\sqrt{6}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{3}} \\frac{2}{\sqrt{6}} & 0 & \frac{-1}{\sqrt{3}} \\frac{1}{\sqrt{6}} & \frac{-1}{\sqrt{2}} & \frac{1}{\sqrt{3}}\end{array}\right)\left(\begin{array}{cc}\sqrt{3} & 0 \0 & 1 \0 & 0\end{array}\right)\left(\begin{array}{cc}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\frac{-1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\end{array}\right)
$$

SVD分解的应用

异值分解的应用有很多，比如：用SVD解PCA、潜在语言索引也依赖于SVD算法。可以说，SVD是矩阵分解、降维、压缩、特征学习的一个基础的工具，所以SVD在机器学习领域相当的重要。

降维

通过奇异值分解的公式，我们可以很容易看出来，原来矩阵A的特征有n维。经过SVD分解后，可以用前r个非零奇异值对应的奇异向量表示矩阵A的主要特征，这样就把矩阵A进行了降维。

压缩

通过奇异值分解的公式，我们可以看出来，矩阵A经过SVD分解后，要表示原来的大矩阵A，我们只需要存储$U$、$\sum$、$V$ 个较小的矩阵即可。而这三个较小规模的矩阵占用内存上也是远远小于原有矩阵$A$ ，这样SVD分解就起到了压缩的作用。

紧奇异值分解与截断奇异值分解

紧奇异值分解：与原始矩阵等秩的奇异值分解；

截断奇异值分解：比原始矩阵低秩的奇异值分解；