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

╰+哭是因爲堅強的太久メ 2022-02-22 21:03 439阅读 0赞

### 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 为半正定矩阵 (证明见[上篇博客][Link 1]), 所以特征值都为非负数, 记其特征值为  σ ( 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\] 为其**特征值的平方根**的矩阵和其对应的**标准正交**特征向量组 (实对称矩阵的特征向量彼此正交, 证明见[上上篇博客][Link 2])

其中

Σ 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−1V1TATAV1Σ1−1=I *(公式 I )*

又有

A T A V 2 = V 2 0 A^T A V\_2 = V\_2 \\bold0 ATAV2=V20

变形得

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 V2TATAV2=(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 U1TU1=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\]=\[U1AV1U2AV1U1AV2U2AV2\]=\[Σ1U2TU1Σ100\]=\[Σ1000\]=Σ

所以

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

# 理解 #

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

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

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

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

[Link 1]: https://blog.csdn.net/vinceee__/article/details/89033193
[Link 2]: https://blog.csdn.net/vinceee__/article/details/89033132