线性代数 (三): SVD数学证明与理解

SVD 数学证明与理解

• 命题
• 证明
• 理解

命题

只讨论实矩阵.

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

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

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

证明

A T A A^TA ATA 为半正定矩阵 (证明见上篇博客), 所以特征值都为非负数, 记其特征值为 σ ( A T A ) = { σ 1 2 . . . σ n 2 } \sigma (A^TA) = \{\sigma_1^2...\sigma_n^2\} σ(ATA)={σ12​...σn2​}, 并按照从大到小顺序排列

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

令 Σ = d i a g ( σ 1 . . . σ n ) , V = [ v 1 . . . v n ] \Sigma = diag(\sigma_1...\sigma_n), V=[v_1 ... v_n] Σ=diag(σ1​...σn​),V=[v1​...vn​] 为其特征值的平方根的矩阵和其对应的标准正交特征向量组 (实对称矩阵的特征向量彼此正交, 证明见上上篇博客)

其中

Σ 1 = d i a g ( σ 1 . . . σ r ) , V 1 = [ v 1 . . . v r ] \Sigma_1 = diag(\sigma_1 ... \sigma_r) , V_1 = [v_1 ... v_r] Σ1​=diag(σ1​...σr​),V1​=[v1​...vr​]

Σ 2 = d i a g ( σ r + 1 . . . σ n ) = 0 , V 2 = [ v r + 1 . . . v n ] \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 T A V 1 = V 1 Σ 1 2 A^TAV_1 = V_1\Sigma_1^2 ATAV1​=V1​Σ12​

变形得

Σ 1 − 1 V 1 T A T A V 1 Σ 1 − 1 = I \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 0 A^T A V_2 = V_2 \bold0 ATAV2​=V2​0

变形得

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

因此

A V 2 = 0 AV_2 = \bold 0 AV2​=0

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

由公式 I, 有 U 1 T U 1 = I U_1^TU_1 = I U1T​U1​=I (即 U 1 U_1 U1​的向量组彼此正交)

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

于是有

U T A V = [ U 1 , U 2 ] T A [ V 1 , V 2 ] = [ U 1 A V 1 U 1 A V 2 U 2 A V 1 U 2 A V 2 ] = [ Σ 1 0 U 2 T U 1 Σ 1 0 ] = [ Σ 1 0 0 0 ] = Σ 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 Σ V T A = U\Sigma V^T A=UΣVT

理解

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

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

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

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