> For the complete documentation index, see [llms.txt](https://json007.gitbook.io/svm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://json007.gitbook.io/svm/math-linear_algebra/svd.md).

# 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简述——字典学习，稀疏编码](http://blog.csdn.net/abcjennifer/article/details/8693342)\
[病态矩阵与条件数](http://www.cnblogs.com/daniel-D/p/3219802.html)

[Sparse SVDs in Python](https://jakevdp.github.io/blog/2012/12/19/sparse-svds-in-python/)

[http://www.benfrederickson.com/fast-implicit-matrix-factorization/](http://www.benfrederickson.com/fast-implicit-matrix-factorization/?spm=5176.100239.blogcont66794.20.Lrc87I)