SVD 数学证明与理解

• 命题
• 证明
• 理解

命题

只讨论实矩阵.

任意矩阵 $A_{m,n}$Am,n​ 可以分解为:

​ $A_{m,n} = U\Sigma V^T$Am,n​=UΣVT

其中 $U_{m,m}$Um,m​ 和 $V_{n, n}$Vn,n​ 为由 $\R^m$Rm 和 $\R^n$Rn 下的标准正交基组成, $\Sigma$Σ 为对角矩阵

证明

$A^TA$ATA 为半正定矩阵, 特征值都为非负数, 记其特征值为 $\sigma (A^TA) = \{\sigma_1^2...\sigma_n^2\}$σ(ATA)={σ12​...σn2​}, 并按照从大到小顺序排列

记 $A^T A$ATA 的秩为 $r$r, 则 $\sigma_1 \ge ... \ge \sigma_r \ge 0 = \sigma_{r+1} = ... = \sigma_n$σ1​≥...≥σr​≥0=σr+1​=...=σn​

令 $\Sigma = diag(\sigma_1...\sigma_n), V=[v_1 ... v_n]$Σ=diag(σ1​...σn​),V=[v1​...vn​] 为其特征值平方根矩阵和对应的标准正交特征向量组

其中

$\Sigma_1 = diag(\sigma_1 ... \sigma_r) , V_1 = [v_1 ... v_r]$Σ1​=diag(σ1​...σr​),V1​=[v1​...vr​]

$\Sigma_2 = diag(\sigma_{r+1} ... \sigma_n) = \bold 0, V_2 = [v_{r+1} ... v_n]$Σ2​=diag(σr+1​...σn​)=0,V2​=[vr+1​...vn​]

于是有

$A^TAV_1 = V_1\Sigma_1^2$ATAV1​=V1​Σ12​

变形得

$\Sigma_1^{-1}V_1^TA^TAV_1\Sigma_1^{-1} = I$Σ1−1​V1T​ATAV1​Σ1−1​=I (公式 I )

又有

$A^T A V_2 = V_2 \bold0 $

变形得

$V_2^TA^TAV_2 = (AV_2)^T (AV_2)= \bold 0$V2T​ATAV2​=(AV2​)T(AV2​)=0

因此

$AV_2 = \bold 0$AV2​=0

令 $U_1 = AV_1\Sigma_1^{-1}$U1​=AV1​Σ1−1​

由公式 I, 有 $U_1^TU_1 = I$U1T​U1​=I

选择任意 $U_2$U2​ 使得 $U = [U_1, U_2]$U=[U1​,U2​] 为正交矩阵

于是有

$U^TAV = [U_1, U_2]^TA[V_1, V_2] = \begin{bmatrix}U_1AV_1&U_1AV_2\\U_2AV_1&U_2AV_2\end{bmatrix} = \begin{bmatrix}\Sigma _1&\bold 0\\U_2^TU_1\Sigma _1 & \bold 0\end{bmatrix} = \begin{bmatrix}\Sigma_1 & \bold 0 \\ \bold 0 & \bold 0\end{bmatrix} =\Sigma$UTAV=[U1​,U2​]TA[V1​,V2​]=[U1​AV1​U2​AV1​​U1​AV2​U2​AV2​​]=[Σ1​U2T​U1​Σ1​​00​]=[Σ1​0​00​]=Σ

所以

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

理解

在我看来, SVD 的功劳是, 它实现了对任意矩阵的特征值分解.

特征值分解的好处是, 它将一个矩阵分解为有限个同阶子矩阵的代权和, 从而实现了有损压缩.

对于本身即可对角化的方阵来说, SVD的速度比常规手段更快

因此, 在PCA中, SVD的角色是实现快速的特征值分解, 因为协方差矩阵本身就可对角化.