奇异值分解

机器学习

---

奇异值分解 (Singular Value Decomposition, SVD) 不光可以用于降维算法中的特征分解，还可以用于推荐系统，以及自然语言处理等领域。

---

1. 特征值和特征向量

特征值和特征向量的定义如下：

$$Ax=\lambda x$$

其中$A$是一个$n×n$的矩阵，$x$是一个$n$维向量，则我们说$λ$是矩阵$A$的一个特征值，而$x$是矩阵$A$的特征值$λ$所对应的特征向量。

求出特征值和特征向量有什么好处呢？就是我们可以将矩阵A特征分解。如果我们求出了矩阵A的$n$个特征值$\lambda_1 \leq \lambda_2 \leq ... \leq \lambda_n$，以及这$n$个特征值所对应的特征向量$\{w_1,w_2,...w_n\}$那么矩阵A就可以用下式的特征分解表示：

$$A=W\Sigma W^{-1}$$

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

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

注意到要进行特征分解，矩阵$A$必须为方阵。那么如果$A$不是方阵，矩阵分解需用到SVD。

---

2. SVD的定义

奇异值的定义：对于一个矩阵$A$，有：

$$(A^TA) \nu = \lambda \nu$$

那么向量$x$就是$A$的右奇异向量。并且：
奇异值：$\sigma_i = \sqrt{\lambda_i}$
左奇异向量：$\mu_i = \frac{1}{\sigma_i}A \nu_i$

SVD并不要求要分解的矩阵为方阵。假设矩阵$A$是一个$m×n$的矩阵，那么定义矩阵$A$的SVD为：

$$A = U\Sigma V^T$$

其中$U$是一个$m×m$的矩阵；$\Sigma$是一个$m×n$的矩阵，除了主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值，通常按从大到小排列；$V$是一个$n×n$的矩阵。$U$和$V$都是酉矩阵，即满足$U^TU=I$，$V^TV=I$。

---

3. 求解

$$A=U\Sigma V^T \Rightarrow A^T=V\Sigma U^T \Rightarrow A^TA = V\Sigma U^TU\Sigma V^T = V\Sigma^2V^T$$

可以看出$A^TA$的特征向量组成的是SVD中的$V$矩阵。类似的方法可以得到$AA^T$的特征向量组成的就是SVD中的$U$矩阵。还可以看出特征值矩阵等于奇异值矩阵的平方，可以通过求出$A^TA$的特征值取平方根来求奇异值。

V：将方阵$A^TA$进行特征分解，得到的特征值和特征向量满足下式：

$$(A^TA)v_i = \lambda_i v_i$$

可以得到矩阵$A^TA$的$n$个特征值和对应的$n$个特征向量$v$了。将$A^TA$的所有特征向量张成一个$n×n$的矩阵$V$，即SVD公式里面的$V$矩阵了。一般我们将$V$中的每个特征向量叫做$A$的右奇异向量。

U：将方阵$AA^T$进行特征分解，得到的特征值和特征向量满足下式：

$$(AA^T)u_i = \lambda_i u_i$$

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

Σ：由于$\Sigma$除了对角线上是奇异值其他位置都是0，那我们只需要求出每个奇异值$\sigma$。通过求出$A^TA$的特征值取平方根来求奇异值。

---

4. 应用

在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上。也就是说，我们也可以用最大的$r$个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说：

$$A_{m \times n} = U_{m \times m}\Sigma_{m \times n} V^T_{n \times n} \approx U_{m \times r}\Sigma_{r \times r} V^T_{r \times n}$$

• 降维：原矩阵$A$的特征有$n$维，经过SVD分解之后，完全可以用前$r$个非零奇异值对应的奇异向量表示矩阵$A$的主要特征。
• 压缩：经过SVD分解以后，要表示原来的大矩阵$A$，我们只需要存储$U$，$\Sigma$，$V$三个较小的矩阵即可。