SVD

特征值分解

$A = Q \Sigma Q^T$

$\Sigma$是对角阵，每个元素都是特征值。Q是对应的特征向量组成的矩阵。 一个矩阵就是一个线性变换，矩阵作用于一个向量后得到一个向量，就相当于先做基变换，然后乘上对角阵，再各个基方向上拉伸，然后再基变换一次。

$Ax = Q \Sigma Q^Tx$

奇异值分解

$M = U \Sigma V^T$

V是原始空间正交基，U是新空间正交基，Σ是V中向量变成U中向量拉伸的倍数。 M是$m \times n$阶复矩阵，则U为m阶酉阵，V为n阶酉阵，Σ为$m \times n$ 。 总结：任何变换都可以理解为先转一下，再各维度扯一扯，再转一下。扯的时候可以直接把几个维度拍扁，所以最后一步可能在低维度上进行，没了。

计算过程如下：

• 计算$M^T$ 和$M^T M$,$M^T M=VΣ^T U^T UΣV^T= VΣ^T ΣV^T= VΣ^2 V^T$。 因为U是正交阵，所以$U^T = U^(-1)$ 。 $\Sigma$是对角阵,$\Sigma^T \Sigma= \Sigma^2$。

• 计算$M^T M$ 的特征值，将特征值按照递减的顺序排列, 求均方根，得到M的奇异值

• 由奇异值可以构建出对角线矩阵$\Sigma$， 同时求出 $\Sigma^{-1}$，以备后面的计算

• 有上述排好序的特征值可以求出对应的特征向量，以特征向量为列得到矩阵 V， 转置后得到$V^T$

• 求出$MV\Sigma^{-1}=U\Sigma V^T V\Sigma^{-1}= U\Sigma\Sigma^{-1}=U$，完毕。

酉矩阵（Unitary Matrix）： n阶复方阵U的n个列向量是U空间的一个标准正交基，则U是酉矩阵。是正交矩阵往复数域的推广。是标准正交基到标准正交基的特殊基变换。 故n阶的复数矩阵U满足：

$$U^H U=U^H U=E \ U^H=U^{-1} \ U^H \text{为U的共轭转置}$$

性质：

• 若A是酉矩阵，则A的逆矩阵也是酉矩阵；

• 若A，B是酉矩阵，则A∙B 也是酉矩阵；

• 若A是酉矩阵，则|det⁡(A) |=1；

• A是酉矩阵的充分必要条件是，它的n个列向量是两两正交的单位向量。

Incremental SVD

《Incremental Singular Value Decomposition Algorithms for Highly Scalable Recommender Systems》

待扩展

sparse SVD， sparse SVD regression， T-SVD

参考佳文

K-SVD简述——字典学习，稀疏编码 病态矩阵与条件数

Sparse SVDs in Python

http://www.benfrederickson.com/fast-implicit-matrix-factorization/