09 奇异值分解(SVD)

对称矩阵的谱分解

我们知道实对称矩阵是可对角化的，有

其中$Q$是标准正交矩阵，$\Lambda$是由特征值构成的对角矩阵。设$Q=\begin{bmatrix}v_1 & \cdots & v_n\end{bmatrix}$，就有$S=\left[\begin{array}{lll} \boldsymbol{v}_{1} & \ldots & \boldsymbol{v}_{n} \end{array}\right]\left[\begin{array}{cccc} \lambda_{1} & 0 & \cdots & 0 \\ 0 & \lambda_{2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_{n} \end{array}\right]\left[\begin{array}{c} \boldsymbol{v}_{1}^{\top} \\ \vdots \\ \boldsymbol{v}_{n}^{\top} \end{array}\right]$，把每个$v$看作整体运用分块矩阵的乘法，就得到

这就是对称矩阵的谱分解，本质上就是对角化的另外一种表示方式。

而由于$Q$是可逆的，$\text{rank}(\Lambda)=\text{rank}(S)$。而$\text{rank}(\Lambda)$就是非零特征值的个数。在谱分解的表达式中，我们可以直接抹掉特征值为0的项，如果$\text{rank}(S)$很小，那么谱分解表达式的复杂度就很小。更精确地，用矩阵表示$S$需要$n^2$个数字，而用谱分解来表示$S$只需要$(n+1) \cdot \text{rank}(S)$个数字。在$\text{rank}(S)$远小于$n$的时候复杂度减小了一个数量级。这使得谱分解在图像压缩等领域有广泛的应用

一般矩阵的奇异值分解(SVD)

对于非对称的矩阵，也有一种类似地分解方式。此时的“对角化”不用特征值而变成了“奇异值”。对于矩阵$A_{m \times n}$，假如$\text{rank}(A)=r$，那么我们我们可以找到标准正交的矩阵$U_{m \times m},V^\top _{n \times n}$，以及矩阵$\Sigma_{n \times n}=\begin{bmatrix}D_{r \times r} & 0 \\ 0 & 0\end{bmatrix}$（其中$D=\left[\begin{array}{cccc} \sigma_{1} & 0 & \cdots & 0 \\ 0 & \sigma_{2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \sigma_{r} \end{array}\right]$，$\sigma_i$就是奇异值），使得能够成立

用类似的方法展开有

可以发现，复杂度从$nm$降为了$(n+m+1) \cdot \text{rank}(A)$

事实上我们注意到，奇异值分解是谱分解（即一般的对角化）的一种推广。因此奇异值与特征值有很密切的关系。当$A$退化为对称方阵的时候，奇异值就是特征值。

我们可以证明，$A$的奇异值恰好是矩阵$A^\top A$的特征值的算术平方根！

$A^\top A$是个对称矩阵。我们知道，一个矩阵是否是正定的，即它的特征值是否恒为正，与这个矩阵的二次型是否恒为正是充分必要的。我们很容易验证$A^\top A$的二次型始终是正的，因为$x^\top A^\top Ax=(Ax)^\top (Ax)=(Ax)^2 \geq 0$。唯一需要注意的是，由于$A$不一定列满秩，等于0的等号是可能取到的。因此我们或许不能说$A^\top A$是正定的，只能说它是“半正定”的。用完全类似的方法，我们可以验证$A^\top A$的所有特征值都是非负的。$A^\top A$的非零特征值就是它的全部正特征值，而由于非零特征值个数就等于矩阵的秩，因此$A^\top A$恰好有$\text{rank}(A^\top A)$个正的特征值。

我们在讨论投影矩阵的时候证明过$\text{rank}(A)=\text{rank}(A^\top A)$。由于$\text{rank}(A)=\text{rank}(A^\top A)$，那么如果做代换$A \to A^\top$，就会得到$\text{rank}(A^\top) = \text{rank}((A^\top) ^\top A^\top)$。而由于行秩等于列秩，这告诉我们$\text{rank}(A)=\text{rank}(AA^\top)$。所以，$\text{rank}(A)=\text{rank}(A^\top A)=\text{rank}(AA^\top)$。

现在我们知道，$A^\top A$恰好有$\text{rank}(A)$个正的特征值。我们很容易验证，$AA^\top$也是“半正定阵”，它也恰好有$\text{rank}(A)$个正的特征值。

我们设$A^\top A$有$r$个特征值$\lambda_1,\cdots \lambda_r$，并且实对称矩阵的代数重数等于几何重数，对应地我们可以找到$r$个线性独立的特征向量。更进一步，这$r$个向量可以是两两正交的单位向量（因为不同特征值对应的特征向量一定是正交的，而同一个特征值的特征子空间里一定能够选出正交基），设为$v_1,\cdots,v_r$。

我们可以验证：$\dfrac{1}{\sqrt{\lambda_{1}}} A \boldsymbol{v}_{1}, \ldots, \dfrac{1}{\sqrt{\lambda_{r}}} A \boldsymbol{v}_{r}$是互相标准正交的：首先，$\left(\dfrac{1}{\sqrt{\lambda_{i}}} A \boldsymbol{v}_{i}\right)^2=\dfrac{v_i^\top A^\top A v_i}{\lambda_i}$，由于$A^\top Av_i=\lambda_iv_i$，因此$\dfrac{v_i^\top (A^\top A v_i)}{\lambda_i}=\dfrac{v_i^\top \lambda_i v_i}{\lambda_i}$ $=(v_i)^2=1$。同时，$\left(\dfrac{1}{\sqrt{\lambda_{i}}} A \boldsymbol{v}_{i}\right)\left(\dfrac{1}{\sqrt{\lambda_{j}}} A \boldsymbol{v}_{j}\right)=\dfrac{v_i^\top A^\top A v_j}{\sqrt{\lambda_i\lambda_j}}=\dfrac{v_i^\top \lambda_j v_j}{\sqrt{\lambda_i\lambda_j}}=0$。此时我们发现，$\dfrac{1}{\sqrt{\lambda_{i}}} A \boldsymbol{v}_{i}=\dfrac{1}{\sqrt{\lambda_i}}A\left(\dfrac{A^\top Av_i}{\lambda_i}\right)=AA^\top\left(\dfrac{1}{\lambda_{i}\sqrt{\lambda_{i}}} A \boldsymbol{v}_{i}\right)$，整理得到

这意味着，$\dfrac{1}{\sqrt{\lambda_{i}}} A \boldsymbol{v}_{i}$恰好是矩阵$AA^\top$（注意不是$A^\top A$）的特征向量，而每个$A^\top A$的特征值$\lambda_i$恰好也是$AA^\top$的特征值！直觉上我们已经感受到，$A^\top A$和$AA^\top$有完全相同的特征值，但我们还需要小心的验证这个断言。我们已经知道这两个矩阵拥有“相同种类”的特征值，但还不知道每个数值的特征值个数是否相同。其实这也是容易验证的，因为我们已经知道$v_i$是线性独立的，$\dfrac{1}{\sqrt{\lambda_{i}}} A \boldsymbol{v}_{i}$也是线性独立的。每个$v_i$占了一维来对应$\lambda_i$，而每个$\dfrac{1}{\sqrt{\lambda_{i}}} A \boldsymbol{v}_{i}$也占了一维来对应$\lambda_i$。因此每个$\lambda_i$在$A^\top A$和$AA^\top$中的维数（即代数重数和几何重数，它们是相等的）是相等的。综上，$A^\top A$和$AA^\top$有完全相同的特征值。

$v_1,\cdots,v_r$可以扩展为$\R^n$的一组基$v_1,\cdots,v_n$，同时依然保证它们是标准正交的特征向量，对于每个$i$都有$A^\top A v_i=\lambda_iv_i$。同时，我们令$u_i=\dfrac{1}{\sqrt{\lambda_{i}}} A \boldsymbol{v}_{i}$，同时把$u_1,\cdots,u_r$也扩展为$\R^m$的一组基$u_1,\cdots,u_m$，同时保证它们是两两正交的单位向量。于是我们令$V = \begin{bmatrix}v_1 & \cdots & v_n\end{bmatrix},U=\begin{bmatrix}u_1 & \cdots & u_m\end{bmatrix}$，令$\sigma_i=\sqrt{\lambda_i}$，就有：

这是容易验证的，因为只需验证$Av_i=\sqrt{\lambda_i}u_i$。对于$i \leq r$，$\sqrt{\lambda_i}u_i=Av_i$，对于$i>r$，$Av_i=\lambda_i v_i=0$。这样我们就证明了$(1)$式！

SVD中的矩阵与基

由于$A=\sigma_{1} \boldsymbol{u}_{1} \boldsymbol{v}_{1}^{\top}+\sigma_{2} \boldsymbol{u}_{2} \boldsymbol{v}_{2}^{\top}+\cdots+\sigma_{r} \boldsymbol{u}_{r} \boldsymbol{v}_{r}^{\top}$，我们容易发现$A$的每个列向量都是$u_1,\cdots,u_r$的线性组合，因此有$C(A) \subseteq \text{span}\{u_1,\cdots,u_r\}$，而因为$\dim(C(A))=r$，因此就有$C(A)=\text{span}\{u_1,\cdots,u_r\}$。因此$\{u_1,\cdots,u_r\}$就是$C(A)$的一组基！

对于$v_{r+1 ..n}$，任意一个乘在奇异值分解式上就会得到$Av_i=\sigma_{1} \boldsymbol{u}_{1} \boldsymbol{v}_{1}^{\top}v_i+\sigma_{2} \boldsymbol{u}_{2} \boldsymbol{v}_{2}^{\top}v_i+\cdots+\sigma_{r} \boldsymbol{u}_{r} \boldsymbol{v}_{r}^{\top}v_i$，而$v_j ^\top v_i=0$对于$j \in [r]$是恒成立的，因此$Av_i=0$对于$i > r$是恒成立的，因此$v_i \in N(A)$。而$\dim(N(A))=n-r$，因此$\{v_{r+1} ,\cdots,v_n\}$就是$N(A)$的一组基！

如果对$A=U\Sigma V^\top$取转置，那么$A^\top = V \Sigma U^\top$，套用相同的结论就会得到$\{v_1,\cdots,v_r\}$是$C(A^\top)$的一组基，$\{u_{r+1} ,\cdots,u_m\}$是$N(A^\top )$的一组基。

由此可见，我们在SVD过程中就已经得到了$C(A),N(A),C(A^\top),N(A^\top)$的标准正交基。

拟合

直线拟合

给出$\R^n$中的$m$个点$a_1,\cdots,a_m$（点和向量是等价的），要想找到一条直线（用单位向量$w$表示），使得所有点到直线的距离平方和最小，这就是直线的拟合问题。

考虑$a_i$在$w$上的投影$p_i$，那么我们要最小化$\sum\limits_{i \in [n]}d_i^2=\sum\limits_{i \in [n]}a_i^2-\sum\limits_{i \in [n]}p_i^2$就等价于最大化$\sum\limits_{i \in [n]}p_i^2$。而$p_i^2=(w \cdot a_i)^2$。如果我们构造矩阵$A=\begin{bmatrix}a_1^\top \\ \vdots \\ a_m^\top \end{bmatrix}$，那么我们只需最大化$(Aw)^2$，即最大化$\|Aw\|$。

神奇的是，$\|Aw\|$的最大值恰好是$A$的最大的奇异值$\sigma_1$。我们知道$\sigma_1=\sqrt{\lambda_1}$，如果我们把$v_1$乘在奇异值分解的表达式上就会得到$Av_1=\sigma_{1} \boldsymbol{u}_{1} \boldsymbol{v}_{1}^{\top}v_1+\sigma_{2} \boldsymbol{u}_{2} \boldsymbol{v}_{2}^{\top}v_1+\cdots+\sigma_{r} \boldsymbol{u}_{r} \boldsymbol{v}_{r}^{\top}v_1=\sigma_{1} \boldsymbol{u}_{1}$，因此$(Av_1)^2=\sigma_1^2u_1^2=\sigma_1^2$，即取$w=v_1$时刚好取到最大值。那么下面我们只需证明对于任意的$w$都有$(Aw)^2 \leq \sigma_1^2$

我们考虑这样一个事实：假如$q_i$是一组标准正交基，那么对于任意的向量$v$我们可以写出$v=c_1q_1+\cdots+c_nq_n$，把它乘开一定得到$v^2=\sum\limits_{i \in [n]}c_i^2$，即标准正交基下向量的长度和其坐标向量的长度是相等的。

我们取出奇异值分解式中的$v_1, \cdots,v_n$，那么有$w=c_1v_1+\cdots+c_nv_n$。由于$v_i$是标准正交基，因此$\sum\limits_{i \in [n]}c_i^2=\|w\|^2=1$。我们把$w$乘在奇异值分解式上，得到