主成分分析是一种矩阵的压缩算法,在减少矩阵维数的同时尽可能的保留原矩阵的信息,简单来说就是将 $n×m$的矩阵转换成$n×k$的矩阵,仅保留矩阵中所存在的主要特性,从而可以大大节省空间和数据量。最近课上学到这个知识,感觉很有意思,就在网上找一些博客进行学习,发现网上关于这方面的介绍很多,但是感觉都不太全面,单靠某一个介绍还是无法理解,当然这可能也跟个人基础有关。所以我在这里根据自己的理解写一个总结性的帖子,与大家分享同时也方便自己复习。对于主成分分析,可以参照以下几篇博客:
百万富翁问题
Count Sketch
Bloom Filter
Count-Min Sketch
马尔可夫与切比雪夫不等式
主成分分析原理与实现
Euclid Algorithm and Extended Euclid Algorithm.
欧几里得算法
原理
欧几里得算法是一种快速计算最大公约数的算法,对于任意的两个数$(a,b)$,其最大公约数表示为$gcd(a,b)$,根据欧几里得算法,$gcd(a,b)=gcd(b,a\mod b)$ 。证明如下: