数字水印 | 奇异值分解 SVD 的定义、原理及性质
数字水印 | 奇异值分解 SVD 的定义、原理及性质
奇异值分解（SVD）是线性代数中的重要概念，在机器学习、数据科学和图像处理等领域有着广泛的应用。本文将从为什么使用SVD开始，逐步深入讲解SVD的定义、求解过程和性质，帮助读者全面理解这一重要概念。
1. 为什么使用 SVD？
实际采集的数据常常充斥着大量的噪声和冗余信息，因此必须筛选出这些不必要的内容，仅保留下那些蕴含主要信息的数据特征。奇异值分解（SVD）技术可以用于简化数据，提取出数据的重要特征，同时剔除数据中的噪声和冗余。SVD 的应用范围广泛，例如在推荐系统中，它能够增强算法的准确性和效率；在图像处理领域，SVD 则被用来实现图像压缩，从而减少存储空间的需求。
2. SVD 的定义是什么？
线性代数警告⚠️
个人感觉，奇异值分解是特征值分解的一般情况，因此几乎所有 SVD 博客都会先讲特征值分解。
2.1 特征值分解
特征值和特征向量的定义如下：
[Ax = \lambda x]
其中，A 是一个n × n阶矩阵，x 是一个n阶向量。如果上式成立，那么我们称λ 是矩阵A的一个特征值，而x 是特征值λ所对应的特征向量。
说明：本文使用大写字母代表矩阵，小写字母代表向量或者标量。一个矩阵A可以有若干个特征值λ，而和特征值λ一起使等式成立的向量x被称为特征向量。
令矩阵A的所有特征值分别为：
[{\lambda_1,\lambda_2,...,\lambda_n}\ (\lambda_1\le \lambda_2\le ...\le \lambda_n)]
这n个特征值所对应的特征向量为({w_1,w_2,...,w_n})。如果同时满足这n个特征向量线性无关，那么矩阵A可以用下式的特征分解表示：
[A = W\Sigma W^{-1}]
其中，W 是这n个特征向量拼成的n × n阶矩阵，而Σ 是以这n个特征值为对角线的n × n阶矩阵。
注意：Σ 是一个名为 Sigma 的矩阵，而不是一个求和符号。
通常情况下，我们会把这n个特征向量标准化，即使其满足(\left | w_i \right |_2=1)，从而有：
[w_i^Tw_i=1]
此时W满足(W^TW = I)，从而有(W^T = W^{-1})。这样特征分解表达式可以写成：
[A = W\Sigma W^{T}]
注意：特征分解仅适用于方阵，即行数与列数相等的矩阵。如果遇到非方阵，即行数与列数不相等的矩阵，那么就需要采用奇异值分解 SVD 来处理了。
2.2 奇异值分解
假设A是一个m × n阶矩阵，其中的元素全部属于实数域或复数域，则存在一个分解使得：
[A = U\Sigma V^T]
其中，U 是m × m阶酋矩阵，Σ 是半正定的m × n阶对角矩阵，而(V^T)是V的共轭转置，是n × n阶酋矩阵。我们称这样的分解为矩阵A的奇异值分解，其中矩阵Σ主对角线上的元素σi即为A的奇异值。
注意：Σ是对角矩阵，但不一定是方阵。此外，假设V是一个复数矩阵，对V中的每个元素取共轭，再对V求转置，那么得到的就是V的共轭矩阵(V^\dagger)。虽然标准的符号是(V^\dagger)，但本文一直用的是(V^T)。
一般Σ的形式如下：
[\Sigma= \begin{bmatrix} \sigma_1 & 0 & 0 & 0 & 0\ 0 & \sigma_2 & 0 & 0 & 0\ 0 & 0 & ... & 0 & 0\ 0 & 0 & 0 & ... & 0 \end{bmatrix}_{m\times n}]
矩阵Σ只有对角元素，其他元素均为0。另一个惯例是，Σ的对角元素是按从大到小的顺序排列的。这些对角元素被称为奇异值。
在科学和工程领域，一个广为人知的观点是：当超过某个奇异值数目（r个）之后，其余的奇异值都会变得很小，以至于可以忽略不计。这表明数据中只有r个特征是重要的，而其他的特征都可以视为噪声或冗余信息。
原文的意思貌似是，由于可以忽略不计，因此可以直接置为零。
补充：酋矩阵的定义
如果n × n阶的复数矩阵U满足：
[U^\dagger U = UU^\dagger = I]
那么U是酋矩阵。其中，I是n阶单位矩阵，(U^\dagger)是U的共轭转置。换句话说，矩阵U为酋矩阵，当且仅当其共轭转置(U^\dagger)为其逆矩阵(U^{-1}=U^\dagger)时成立。
3. 如何求解奇异值 SV？
⚠️注意：有现成的库函数，不必非得看原理。
下图形象地展示了 SVD 的定义：
那么我们如何求解U, Σ, V这三个矩阵呢？
3.1 求解过程
求解 V 矩阵
如果用(A^T)和A做矩阵乘法，那么会得到一个n × n阶的方阵(A^TA)。既然(A^TA)是方阵，那么就可以做特征分解了。特征值和特征向量满足下式：
[(A^TA)v_i=\lambda_i v_i]
从而得到(A^TA)的n个特征值λi及其对应的n个特征向量vi。将所有特征向量vi拼成一个n × n阶矩阵V，即为 SVD 公式中的V矩阵。一般我们将V中的每个特征向量称为A的右奇异向量。
求解 U 矩阵
如果用A和(A^T)做矩阵乘法，那么会得到一个m × m阶的方阵(AA^T)。 既然(AA^T)是方阵，那么就可以做特征分解了。特征值和特征向量满足下式：
[(AA^T)u_i=\lambda_i u_i]
从而得到(AA^T)的n个特征值λi及其对应的n个特征向量ui。将所有特征向量ui拼成一个n × n阶矩阵U，即为 SVD 公式中的U矩阵。一般我们将U中的每个特征向量称为A的左奇异向量。
求解 Σ 矩阵
由于Σ除对角线上的奇异值外，其余的位置都是0，因此我们只需求出每个奇异值σi即可。
我们注意到：
[\begin{alignat}{2}
A &= U\Sigma V^T \
AV &= U\Sigma V^TV \
AV &= U\Sigma \
Av_i &= \sigma_i u_i \
\sigma_i &= Av_i/u_i
\end{alignat}]
如此一来，我们就可以求出每个奇异值σi，进而求出奇异值矩阵Σ。
3.2 证明过程
我们说(A^TA)的特征向量组成了 SVD 中的V矩阵，(AA^T)的特征向量组成了 SVD 中的U矩阵，这有什么依据吗？这个其实很容易证明，我们以V矩阵的证明为例：
[\begin{alignat}{2}
A = U\Sigma V^T &\Rightarrow A^T = V\Sigma^T U^T \
A^TA &= V\Sigma^T U^TU\Sigma V^T \
&= V\Sigma^T \Sigma V^T \
&= V\Sigma^2 V^T \
\end{alignat}]
上式证明使用了：(U^TU = I)和(\Sigma^T\Sigma = \Sigma^2)。可以看出(A^TA)的特征向量矩阵的确是 SVD 中的V矩阵。同理可以证明(AA^T)的特征向量矩阵的确是 SVD 中的U矩阵。
说明：对比(A^TA=V\Sigma^2 V^T)和特征值分解公式(A=W\Sigma W^{T})可知，V矩阵是(A^TA)的特征向量矩阵。
进一步我们还可以看出，特征值矩阵是奇异值矩阵的平方(\Sigma^2)，因此特征值λi和奇异值σi满足如下关系：
[\sigma_i = \sqrt{\lambda_i}]
由此可见，我们可以不使用上面推导出的(\sigma_i = Av_i/u_i)来计算奇异值，而是通过求(A^TA)的特征值λi并对其开平方根来得到奇异值。
补充：通过(A^TA)或(AA^T)的特征值开平方根求解奇异值的注意点
如前所述，我们可以利用如下性质求解奇异值：
[\begin{alignat}{2}
A^TA &= V\Sigma U^TU\Sigma V^T = V\Sigma^T \Sigma V^T \
AA^T &= U\Sigma V^TV\Sigma U^T = U\Sigma \Sigma^TU^T
\end{alignat}]
需要注意的是，上述(\Sigma^T\Sigma)和(\Sigma\Sigma^T)在矩阵的角度上来讲是不同的，因为它们的维度不同(\Sigma^T\Sigma \in \mathbb{R}^{n\times n},\Sigma \Sigma^T \in \mathbb{R}^{m\times m})。但是它们主对角线上的奇异值是相等的，即有：
[\Sigma^T \Sigma= \begin{bmatrix} \sigma_1^2 & 0 & 0 & 0\ 0 & \sigma_2^2 & 0 & 0\ 0 & 0 & ... & 0\ 0 & 0 & 0 & ... \end{bmatrix}{n\times n}\ \Sigma \Sigma^T= \begin{bmatrix} \sigma_1^2 & 0 & 0 & 0\ 0 & \sigma_2^2 & 0 & 0\ 0 & 0 & ... & 0\ 0 & 0 & 0 & ... \end{bmatrix}{m\times m}]
因此，对(\Sigma^T\Sigma)或(\Sigma\Sigma^T)的特征值开方，都可以得到所有奇异值。
个人理解：虽然(\Sigma^T\Sigma)和(\Sigma\Sigma^T)的维度不同，但是它们的对角元素个数相同且数值相等，并且等于奇异值的平方。
4. 什么是 SVD 的性质？
上面我们对 SVD 的定义和计算做了详细的介绍，下面对 SVD 的性质进行分析。
奇异值分解中的奇异值，与特征分解中的特征值类似，在奇异值矩阵(\Sigma_{m\times n})中也是按照从大到小的顺序排列的。而且奇异值减小的特别快，在很多情况下，前10%甚至1%的奇异值的和就占了全部奇异值之和的99%以上。
这意味着我们可以用前r个奇异值以及相应的左右奇异向量来近似描述矩阵。也就是说，由于r要比n小很多，因此一个大的矩阵A可以用几个小的矩阵来近似表示。如下图所示：
说明：不难看出，上图中的(U_r,\Sigma_r,V^T_r)分别是原来的U,Σ,VT裁剪得到的矩阵，因此说大矩阵A可以由几个小矩阵来近似表示。此外，个人认为蓝色块只是为了标出左奇异向量、奇异值、右奇异向量分别是什么，并不是说只需要矩阵的这一部分。
取其前r个非零奇异值，可以还原原来的矩阵A，即前r个非零奇异值对应的奇异向量代表了矩阵A的主要特征。可以表示为：
[A_{m\times n} \approx U_{m\times r} \Sigma_{r\times r} V^T_{r\times n}]
综上所述：SVD 的一个显著特性是其奇异值衰减速度非常快，这意味着数据集中的大部分信息都可以由前几个大的奇异值表征，而后续的奇异值则迅速减小至可以忽略不计的程度。这一特性使得 SVD 在数据压缩和去噪领域大放异彩，因为它能够有效地捕捉并保留数据的关键特征，同时剔除噪声和次要信息。