SVD的数学计算步骤

涉及到矩阵论相关的东西,这里查资料需要把他彻底搞个明白,幸好找到了参考中的pdf文档,写的很详细很入门,于是就拜读了一下。对于知道的人不要笑话,不知道的赶紧补课吧!

一、线性代数相关基础

  • 点乘/内积: $(\vec{x},\vec{y}) = \vec{x}\cdot\vec{y} = \sum_{i=1}^nx_i+y_i$
    要求点乘的两个向量的维度相同
  • 正交:$\vec{x}\cdot\vec{y} = 0$
    两个向量的点乘为0
  • 标准向量:|$\vec{x}| = \sqrt{\sum_{i=1}^nx_i^2} = 1$
    向量的长度为1
  • Gram-Schmidt正交化:
    用于产生一个矩阵的标准正交基,定义为每个列向量的长度为1,不同列向量相互正交,计算过程为:
    (1)对于第一列,对向量的模长进行标准化;
    (2)后面的每一列,依次按照公式$\vec{w}_k = \vec{v}k - \sum{i=1}^{k-1}\vec{u}_i\cdot\vec{v}_k*\vec{u}_i$进行计算,然后将计算结果$\vec{w}_k$进行标准化。
    如果标准正交基是方阵,那么叫做正交矩阵,且$\vec{A}\vec{A}^T=\vec{I}$。
  • 矩阵的乘法:
    如果$\vec{A}$和$\vec{B}$分别是维度为(m,n)和(n,s)的矩阵,那么$\vec{A}\vec{B}$结果的维度就是(m,s)。
  • 对角矩阵:
    对角线上的元素全不为零,其余元素全部为零的方阵。
  • 单位矩阵:
    除了对角线上的元素为1,其他元素都为0的方阵,且$\vec{A}\vec{I}=\vec{A}$。
  • 行列式:
    将一个方阵映射而成的数值,根据其方阵的维度不同,计算如下:
    (1)$\vec{A} = \begin{bmatrix}a\end{bmatrix}$,$det(\vec{A})=a$;
    (2)$\vec{A} =\begin{bmatrix}a&b\c&d\end{bmatrix}$,$det(\vec{A})=ad-bc$;
    (3)对于更高维度的,按照第一行展开成低纬度的子方阵计算,展开过程中交替改变符号。
    这里给出一个例子,计算检验看看对不对($det(\vec{A})=-36$)。
    $$\vec{A}=\begin{bmatrix}1&2&3&4\ -1&-2&-7&-4\2&3&4&5\ -2&-3&5&4\end{bmatrix}$$
  • 特征值和特征向量:
    对于方阵$\vec{A}$满足$\vec{A}\vec{v}=\lambda\vec{v}$,那么非0向量$\vec{v}$为特征向量,$\lambda$为特征值。其实可以上面看作是个方程组的解的问题,将$\vec{A}$看成方程组的系数,那么特征向量为方程组的解,比如
    $\vec{A} =\begin{bmatrix}2&1\1&2\end{bmatrix}$,那么
    $$\vec{A}\vec{v}=\lambda\vec{v}=\begin{bmatrix}2&1\1&2\end{bmatrix}\begin{bmatrix}x_1\x_2\end{bmatrix}=\lambda\begin{bmatrix}x_1\x_2\end{bmatrix}$$
    其整理后就为
    $$\begin{bmatrix}(2-\lambda)&1\11&(2-\lambda)2\end{bmatrix}=0$$
    解得特征值为$\lambda_1=3,\lambda_2=1$,对应的特征向量为$\begin{bmatrix}1,1\end{bmatrix}$和$\begin{bmatrix}1,-1\end{bmatrix}$。

二、进行SVD奇异值分解

SVD的目的,就是将一组相关的变量投射到某个超平面,形成相互无关的变量,用以更好的显示变量之间的差异性,同时还可以根据相关性进行排序,找出哪些属性的差异最明显,可选择的保留差异性大的属性,从而实现了数据的降维。其寻找的超平面具有以下目的:

  • 最近重构性:样本点到这个超平面的距离都足够近;
  • 最大可分性:样本在这个超平面上的投影都尽可能的分开;
    SVD的最简洁表达公式如下
    $$\vec{A}{mn}=\vec{U}{mm}\vec{S}{mn}\vec{V}{nn}^T$$
    其中,$\vec{A}{mn}$为原始信号,$\vec{U}{mm}$和 $\vec{V}{nn}$都是两个正交矩阵,$\vec{V}{nn}^T$为 $\vec{V}{nn}$的转置,$\vec{S}$为对角矩阵,那么$\vec{A}{mn}$就可以用右边的三个公式表示出来。

2.1 SVD分解

下面介绍SVD分解的计算过程:

  • 给定原始信号$\vec{A}$,计算 $\vec{A}{mn}\vec{V}{nm}^T$,得到(m,m)方阵;
  • 计算方阵的特征值和特征向量;
  • 按照特征值从大到小的顺序,依次取其特征向量作为列,组成矩阵$\vec{U}’$;
  • 对$\vec{U}’$进行Gram-Schmidt正交化形成正交矩阵$\vec{U}_{mm}$;
  • 依照上面类似的过程,采用$\vec{A}{nm}^T\vec{V}{mn}$进行计算,最终得到正交矩阵$\vec{V}{nn}$,再行转秩得到$\vec{V}{nn}^T$;
  • 对于$\vec{S}$,是使用上面的非0特征值按照从大到校的顺序开放形成对角矩阵,对于矩阵维度不满足,右端依次添加0列即可;
  • 用$\vec{U}{mm}\vec{S}{mn}\vec{V}{nn}^T$就可以重构$\vec{A{mn}}$了。

2.2 SVD用于降维的额外操作

上面是SVD分解,所以最终得到的三个变量是能够完全重构原来的输入信号的。在上面计算的特征值的时候,如果按照从大到小的顺序,实际就是按照属性差异从大到小进行的排列,一般来说可以事先固定设定$\lambda$的个数,或者取总$\lambda$和前95%部分的$\lambda$来决定降维的程度。
比如对原始的信号属性从n维降低到r维度,只需要用原始信号乘以前r列的特征向量就可以了。
$$\vec{A}{mn}\vec{U}{n,1:r}\approx\hat{A}_{mr}$$
就可以了。

其实,本质上PCA跟SVD就是一个东西~~
本文完!

参考