Matrix Factorization

2024-02-27 23:44:45

概述

在机器学习领域通常会用到矩阵分解技术，目的就是维度规约或压缩存储，本文做一个简单的总结与概述。

特征值分解(Eigenvalue Decomposition)，假设对于一个 $n{\times}n$ n×n的方阵 $A$ A，有如下等式成立：

$A\vec{v}=\lambda\vec{v}$ Av=λv

其中 $\lambda$ λ为常数， $\vec{v}$ v为列向量。那么满足上式的 $\lambda$ λ为矩阵 $A$ A的特征值，对应的 $\vec{v}$ v为特征向量，方阵的特征向量是相互正交的。写成矩阵形式有：

$A=Q{\Sigma}Q^{-1}$ A=QΣQ−1

其中 $\Sigma$ Σ为特征值由大到小排列构成的对角矩阵， $Q$ Q为特征向量构成的方阵。选取前 $k$ k大的特征值，那么降维后的 $A$ A可以表示成：

$A_{reduc}=A_{n{\times}n}(Q^{-1})_{n{\times}k}$ Areduc=An×n(Q−1)n×k

EVD即是PCA的原理。

奇异值分解(Singular Value Decomposition)，假设对一个 $n{\times}m$ n×m的矩阵 $A$ A，SVD的目标是把 $A$ A分解成如下形式：

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

其中 $\Sigma$ Σ是与 $A$ A同形状的奇异值矩阵。由矩阵乘法的性质可得，矩阵 $U$ U的形状为 $n{\times}n$ n×n， $V^{T}$ VT的形状为 $m{\times}m$ m×m。同样类似的， $U$ U与 $V$ V都是正交方阵。

SVD可以通过EVD来实现，注意到：

$AA^{T}=U\Sigma\Sigma^{T}U^{T} \\ A^{T}A=V\Sigma^{T}{\Sigma}V^{T} \\$ AAT=UΣΣTUTATA=VΣTΣVT

不难发现可以分别通过对 $AA^{T}$ AAT和 $A^{T}A$ ATA做EVD可以得到 $U$ U和 $V$ V，而 $\Sigma$ Σ则是特征值的开方。选取前 $k$ k大的奇异值，那么 $A$ A可以近似压缩存储成：

$A_{comp}=U_{n{\times}k}\Sigma_{k{\times}k}(V^{T})_{k{\times}m}$ Acomp=Un×kΣk×k(VT)k×m

对于降维，有：

$A_{reduc}=A_{n{\times}m}(V^{T})_{m{\times}k}$ Areduc=An×m(VT)m×k