Singular Value Decomposition

SVD，全称为奇异值分解（Singular Value Decomposition），是一种在数值线性代数中广泛使用的矩阵分解技术。SVD 将一个矩阵分解成三个特定的矩阵的乘积，可以用于许多应用领域，包括信号处理、统计分析、图像处理和推荐系统等。

Review: Eigendecomposition

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

$$A x=\lambda x$$

其中 $\mathrm{A}$ 是一个 $n \times n$ 的实对称矩阵, $x$ 是一个 $n$ 维向量, 则我们说 $\lambda$ 是矩阵 $\mathrm{A}$ 的一个特征值, 而 $x$ 是矩阵 $\mathrm{A}$ 的特征值 $\lambda$ 所对应的特征向量。

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

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

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

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

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

$$A=W \Sigma W^T$$

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

SVD: Definition

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

$$A=\mathrm{U} \Sigma \mathrm{V}^{-1}$$

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

求解矩阵 $\mathrm{V}$

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

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

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

求解矩阵 $\mathrm{U}$

同理，对 $(AA^T)$ 如此操作，可以得到 $m \times m$ 的矩阵 $\mathrm{U}$。一般我们将 $\mathrm{U}$ 中的每个特征向量叫做 $\mathrm{A}$ 的左奇异向量。

求解 $\Sigma$

$$
A=U\Sigma V^T \Rightarrow AV=U\Sigma V^TV \Rightarrow AV=U\Sigma \Rightarrow Av_i = \sigma_i u_i \Rightarrow \sigma_i = Av_i / u_i
$$

解法的证明

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

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

可以看出 $(A^TA)$的特征向量组成的就是我们 SVD 中的 $\mathrm{V}$ 矩阵。同理，$(AA^T)$的特征向量组成的就是我们 SVD 中的 $\mathrm{U}$ 矩阵。

进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方，也就是说特征值和奇异值满足如下关系：

$$
\sigma_i = \sqrt{\lambda_i}
$$

性质

对于奇异值,它跟我们特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列，而且奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说，我们也可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说：

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

其中k要比n小很多。由于这个重要的性质，SVD可以用于PCA降维，来做数据压缩和去噪。

在 PCA 中的应用

PCA和白化（Whitening）是一种预处理形式。在这种处理中，先对数据进行零中心化处理，然后计算协方差矩阵，它展示了数据中的相关性结构。

# 假设输入数据矩阵X的尺寸为[N x D]
X -= np.mean(X, axis = 0) # 对数据进行零中心化(重要)
cov = np.dot(X.T, X) / X.shape[0] # 得到数据的协方差矩阵

数据协方差矩阵的第(i, j)个元素是数据第i个和第j个维度的协方差。具体来说，该矩阵的对角线上的元素是方差。还有，协方差矩阵是对称和半正定的。我们可以对数据协方差矩阵进行SVD（奇异值分解）运算。

U,S,V = np.linalg.svd(cov)

U的列是特征向量，S是装有奇异值的1维数组（S中元素是特征值的算术平方根）。为了去除数据相关性，将已经零中心化处理过的原始数据投影到特征基准上：

Xrot = np.dot(X,U) # 对数据去相关性

注意U的列是标准正交向量的集合（范式为1，列之间标准正交），所以可以把它们看做标准正交基向量。因此，投影对应x中的数据的一个旋转，旋转产生的结果就是新的特征向量。如果计算Xrot的协方差矩阵，将会看到它是对角对称的。np.linalg.svd的一个良好性质是在它的返回值U中，特征向量是按照特征值的大小排列的。我们可以利用这个性质来对数据降维，只要使用前面的小部分特征向量，丢弃掉那些包含的数据没有方差的维度。 这个操作也被称为主成分分析（ Principal Component Analysis 简称PCA）降维：

Xrot_reduced = np.dot(X, U[:,:100]) # Xrot_reduced 变成 [N x 100]

经过上面的操作，将原始的数据集的大小由[N x D]降到了[N x 100]，留下了数据中包含最大方差的100个维度。通常使用PCA降维过的数据训练线性分类器和神经网络会达到非常好的性能效果，同时还能节省时间和存储器空间。

最后一个在实践中会看见的变换是白化（whitening）。白化操作的输入是特征基准上的数据，然后对每个维度除以其特征值来对数值范围进行归一化。该变换的几何解释是：如果数据服从多变量的高斯分布，那么经过白化后，数据的分布将会是一个均值为零，且协方差相等的矩阵。该操作的代码如下：

# 对数据进行白化操作:
# 除以特征值 
Xwhite = Xrot / np.sqrt(S + 1e-5)

References

• 奇异值分解(SVD)原理与在降维中的应用 – 刘建平Pinard