一些公式/定理积累

积累一些可能会用的数学公式，有时可以作为简化计算、提升效率的小技巧。

1. Woodbury Formula

不想敲代码，直接截个wiki的图过来：

上面已经提到了这个公式的几种特殊情形，这里我们关注更简单的一种。当A是n阶单位阵，C是k阶单位阵时，有：

然后呢，有什么用嘛？且看，如果n>>k，那我们原本要求的式子左边，是对一个n阶方阵求逆—-复杂度为O(n3)，现在哩，式子右边只用对一个k阶方阵求逆—-复杂度为O(k3)，然后再加上矩阵乘法约为O(nk2)的复杂度，对n而言，计算复杂度瞬间从立方下降为线性有木有！

2. Nystrom Method

可以用来计算特征向量，可以看到，Nystrom把对n阶矩阵的特征分解问题，转化为对l阶矩阵的特征分解问题，大大降低了计算复杂度。实际上，谱聚类的一种大规模扩展方式，就是利用Nystrom方法。

3. 一个不等式

当z>0时，有z≥1+logz成立，且在z=1时取等号。

4. 闵可夫斯基不等式

5. Holder不等式

6. Ky Fan Theorem

[ref]: Fan K. On a Theorem of Weyl Concerning Eigenvalues of Linear Transformations [J]. Proc Natl Acad Sci USA, 1949, 35(11):652-655.

7. Eckart-Young-Mirsky theorem

n阶矩阵A（rank>p）的rank-p近似为：

这里，λi是第i大的特征值，fi是对应的特征向量。

[ref]: Eckart C, Young G. The approximation of one matrix by another of lower rank[J]. Psychometrika, 1936, 1(3):211-218.

8. Von-Neumann successive projection lemma

For finding the closest intersection of sub-spaces…
Actually, the Von-Neumann lemma applies only to linear subspaces. The extension to convex subspaces involves a “deflection” component described by Dykstra [2].

[ref]: [1] Von Neumann J. Functional Operators. II. The Geometry of Orthogonal Spaces.[J]. Princeton University Press Princeton N J, 1950.
[2] Richard L. Dykstra. An Algorithm for Restricted Least Squares Regression[J]. Journal of the American Statistical Association, 1983, 78(384):837-842.