奇异值分解（SVD）推导证明与应用

lankuohsing
75 阅读3分钟

本文已参与「新人创作礼」活动，一起开启掘金创作之路。

0. 线性代数与矩阵基础知识回顾

本文讨论的范围实数空间，不涉及复数空间，因此各种术语和定理都以实空间下的名称为准，当然也可以推广到复数空间，只需进行一些名词的变换（对称矩阵-Hermitian举矩阵，正交矩阵-酉矩阵）。

0.1. 正交向量组

对于向量x1,x2,⋯ ,xk∈Rnx_1,x_2,\cdots,x_k\in R^n，若xiTxj=0,∀(i,j)∈{(i,j)∣1≤i<j≤k}x_i^Tx_j=0,\forall (i,j)\in \{(i,j)\lvert 1\leq i<j\leq k\}，则称x1,x2,⋯ ,xkx_1,x_2,\cdots,x_k是一组正交向量组，简称正交组。如果正交组里面的向量还是归一化的，即xiTxi=1,i=1,2,⋯ ,kx_i^Tx_i=1,i=1,2,\cdots,k，则称该正交组为标准正交组。

0.2. 正交矩阵

一个实的正方矩阵Q∈Rn×nQ\in R^{n\times n}称为正交矩阵，若：

QQT=QTQ=I(0,2)QQ^T=Q^TQ=I\\ \tag{0,2}

由上述定义可以推出如下几个等价的叙述：

  1. QQ是正交矩阵
  2. QTQ^T是正交矩阵
  3. QQ是非奇异的，并且QT=Q−1Q^T=Q^{-1}
  4. QQT=QTQ=IQQ^T=Q^TQ=I
  5. Q=[q1,q2,⋯ ,qn]Q=[q_1,q_2,\cdots,q_n]的列组成标准正交组
  6. QQ的行组成标准正交组
  7. ∀x∈Rn,y=Qx\forall x\in R^n, y=Qx的Euclidean长度与xx的Euclidean长度相等，也即有yTy=xTxy^Ty=x^Tx。

0.3. 正定矩阵

一个对称矩阵AA称为

  • 正定矩阵(A>0A>0)：若二次型xTAx>0,∀x≠0x^TAx>0,\forall x\neq 0;
  • 半正定矩阵(A≥0A\geq 0)：若二次型xTAx≥0,∀x≠0x^TAx\geq 0,\forall x\neq 0;
  • 负定矩阵：如果−A-A是正定的
  • 半负定矩阵：如果−A-A是半正定的

正定矩阵的等价条件：

  • 存在可逆矩阵CC使CTCC^TC等于该矩阵
  • 正定矩阵<=><=>所有特征值取正实数，半正定矩阵<=><=>所有特征值取非负实数

0.4. 特征值

  • 对于n阶对称矩阵AA的特征值都是实数。
  • 对于n阶对称矩阵AA，总存在正交阵QQ，使得Q−1AQQ^{-1}AQ是对角阵，且对角线元素就是AA的特征值按从大到小排列。即Q−1AQ=diag(λ1,λ2,⋯ ,λn),λ1>λ2>⋯>λnQ^{-1}AQ=diag(\lambda_1,\lambda_2,\cdots,\lambda_n),\lambda_1>\lambda_2>\cdots>\lambda_n。

1. 奇异值分解（Singular Value Decomposition）

1.1. svd的数学描述

svd告诉我们，对任意m×nm\times n的矩阵AA，都可以表示为下面这种形式：

A=UΣVT(1,1)A=U\Sigma V^T\\ \tag{1,1}

其中UU是m×mm \times m的正交阵，VV是n×nn\times n的正交阵，Σ\Sigma是m×nm\times n的对角阵，

Σ=[Σ1000](1,2)\Sigma=\begin{bmatrix} \Sigma_1 &0\\ 0 &0 \\ \end{bmatrix} \\ \tag{1,2}

Σ1=diag(σ1,σ2,⋯ ,σr),r=rank(A)\Sigma_1=diag(\sigma_1,\sigma_2,\cdots,\sigma_r),r=rank(A)，其对角元素按照从大到小排列

1.2. svd的证明

在开始证明前，先给出几个引理：

  • 引理1：ATAA^TA可对角化，且具有实的非负特征值（这是因为ATAA^TA是半正定矩阵）
  • 引理2：rank(A)=rank(ATA)=rank(AAT)rank(A)=rank(A^TA)=rank(AA^T)
  • 引理3：A=0 ⇔ ATA=0A=0\ \Leftrightarrow\ A^TA=0

下面开始证明： 设rank(A)=rrank(A)=r，根据引理1和引理2，存在n×nn\times n的正交矩阵VV，使得

VT(ATA)V=diag(λ1,λ2,⋯ ,λn)(1,3)V^T(A^TA)V=diag(\lambda_1,\lambda_2,\cdots,\lambda_n)\\ \tag{1,3}

其中λ1>λ2>⋯>λr>0=λr+1=⋯=λn\lambda_1>\lambda_2>\cdots>\lambda_r>0=\lambda_{r+1}=\cdots=\lambda_n为ATAA^TA的n个非负特征根。 令Σ1=diag(σ1,σ2,⋯ ,σr)=diag(σ1,σ2,⋯ ,σr)\Sigma_1=diag(\sigma_1,\sigma_2,\cdots,\sigma_r)=diag(\sqrt\sigma_1,\sqrt\sigma_2,\cdots,\sqrt\sigma_r)，V1=[v1,v2,⋯ ,vr]，V2=[vr+1,vr+2,⋯ ,vn]V_1=[v_1,v_2,\cdots,v_r]，V_2=[v_{r+1},v_{r+2},\cdots,v_{n}]，并且有V=[V1,V2]V=[V_1,V_2]。 从而有ATAV1=V1Σ12A^TAV_1=V_1\Sigma_1^2，进一步得到：

Σ1−1V1TATAV1Σ1−1=I(1,4)\Sigma_1^{-1}V_1^TA^TAV_1\Sigma_1^{-1}=I\\ \tag{1,4}

令U1=AV1Σ1−1U_1=AV_1\Sigma_1^{-1}，则有U1TU1=IU_1^TU_1=I。此时，我们可以选择m−rm-r组标准正交向量与U1U_1的列向量组成一组标准正交基，也即U=[U1,U2]U=[U_1,U_2]是一个m阶正交阵，且U1TU2=0U_1^TU_2=0。 另一方面，容易得到：

ATAV2=V20 ⇒ V2TATAV2=0(1,5)A^TAV_2=V_20\ \Rightarrow\ V_2^TA^TAV_2=0\\ \tag{1,5}

根据引理3可得AV2=0AV_2=0

综上可得：

UTAV=[U1TAV1U1TAV2U2TAV1U2TAV2]=[Σ10U2TU1Σ10]=[Σ1000]=Σ(1,6)\begin{aligned} U^TAV&=\begin{bmatrix} U_1^TAV_1 &U_1^TAV_2\\ U_2^TAV_1 &U_2^TAV_2 \\ \end{bmatrix} \\ &=\begin{bmatrix} \Sigma_1 &0\\ U_2^TU_1\Sigma_1 &0 \\ \end{bmatrix} \\ &=\begin{bmatrix} \Sigma_1 &0\\ 0 &0 \\ \end{bmatrix} \\ &=\Sigma\\ \tag{1,6} \end{aligned}

也即A=UΣVTA=U\Sigma V^T，到此奇异值分解定理得证。

2. SVD的应用

2.1. 矩阵压缩

矩阵压缩的具体场景有很多，例如图像就是一个矩阵，神经网络里面的某一层的权重也是一个矩阵。 由(1,1)(1,1)可知

A=σ1u1v1T+σ2u2v2T+⋯σrurvrT(2,1)A=\sigma_1 u_1v_1^T+\sigma_2 u_2v_2^T+\cdots \sigma_ru_r v_r^T\tag{2,1}

注意上式用到了Kronecker积 将奇异值从大到小排序，选择前k个最大的奇异值对应的乘积项，可以在尽可能保留矩阵信息的情况下压缩存储空间