本次的讲解主要内容如下：
1.什么是奇异值分解？为什么任意实矩阵都存在奇异值分解？
2.怎么用C语言代码实现SVD分解？
3.实际应用：
基于SVD的图像压缩
基于SVD的协同过滤推荐系统
一、SVD奇异值分解概念
在多数情况下，数据中的一小段携带了数据集中的大部分信息，其他信息要么是噪声，要么就是毫不相干的信息。在线性代数中有很多矩阵分解技术，通过它们可以将原始矩阵表示成新的易于处理的形式。不同的矩阵分解技术具有不同的性质，有各自特定的应用场景。
奇异值分解SVD作为矩阵分解的一种类型，可以使我们只用很小的数据集就能表达原始数据集，它可以从噪声数据中抽取特征值。SVD可以将任意维数的原始数据集矩阵Data分解成三个矩阵U、Σ、VT，如下公式所示：
上述分解中会构建出一个矩阵Σ，该矩阵只有对角元素，其他元素均为0.此外，Σ的对角元素是从大到小排列的，这些对角线元素称为原始数据集矩阵Data的“奇异值”singular value。它与PCA特征的联系：PCA得到的是矩阵的特征值，奇异值就是矩阵Data*DataT特征值的平方根。
设A∈Rrm*n，ATA的特征值为：
则称
（i=1,2,…,n)为矩阵A的奇异值。
当A为零矩阵时，它的所有奇异值均为零。一般的，矩阵A的奇异值个数等于A的列数，A的非零奇异值的个数等于A的秩。
接下来，首先用数学推导介绍SVD存在的必然性。
一些定义：
正交矩阵：
如果方正Q满足QTQ=QQT=I(或者等价的Q-1=QT)，则称Q为正交矩阵。
非奇异矩阵：
若n阶矩阵A的行列式不为零，即 |A|≠0，则称A为非奇异矩阵或满秩矩阵，否则称A为奇异矩阵或降秩矩阵。
正定矩阵：
设M是n阶方阵，如果对任何非零向量z，都有 zTMz > 0，就称M正定矩阵。
定理证明：
定理1 (实对称矩阵正交相似于对角矩阵)：
对任意n阶实对称矩阵A，都有n阶正交矩阵Q，使得
为了证明该定理，首先给出并证明两个引理：
. 实对称矩阵特征值为实数
若任意n阶矩阵的特征值为实数，则有正交矩阵Q，使得
引理1，证明：
设λ为A的一个特征值，x为对应的特征向量，则有Ax = λx，因此
所以特征值必为实数。
引理2，利用数学归纳法证明：
当n=1时，结论显然成立
设对n-1阶矩阵的结论也成立，现在证明对n阶矩阵结论依然成立
令λ1为A的一个实特征值，相应的特征向量为a1，不妨设a1已单位化。把a1扩充为Rn的标准正交基a1, a2,…, an，构造矩阵X=(a2,…, an)和P=(a1,X)，则P为正交矩阵且有：
于是，AP = (Aa1, AX)= (λ1a1, P(P-1AX)) = (λ1Pε1,P(P-1AX)) = P(λ1ε1, P-1AX)。设：
【个人理解：A->n*n，X->n*n-1，P->n*n，则P-1AX->n*n-1，正好这么拆，a’->1*n-1】
从而有：
根据归纳假设，对于A1有n-1阶正交矩阵T，使得T-1A1T = TTA1T= At为上三角矩阵，现取：
由于P和Q都是正交矩阵，而正交矩阵相乘结果R仍是正交矩阵，因此可以写作：
现在回到定理1的证明，因为A为实对称矩阵，则有引理1知，A的特征值均为实数。由引理2知，存在正交矩阵R，使得
C为上三角矩阵，而A=AT，则有C=CT，但C是上三角矩阵，CT为下三角矩阵，所以C必为对角矩阵。定理1得证。其中，C的对角线元素即为A的特征值构成。
定理2（奇异值分解）：
设A∈Rrm*n，则存在m阶正交矩阵U和n阶正交矩阵V，使得
其中，Σ = diag(σ1,σ2,…, σr)，即σ1, σ2,…,σr是A的非零奇异值，亦记作A=UDVT
证明：
记对称矩阵ATA的特征值为：
由对称矩阵的正交分解(定理1)，我们有：
由第一个公式可以得到，
由第二个公式可以得到，
故有
，证毕
若记U=(u1, u2,…,um)，V=(v1, v2,…,vn)，根据SVD的分解，A可以表示为：
上式就是A的奇异值分解过程。
【我恨死CSDN的公式编辑了！！每次都贴图，烦的要命】
二、SVD奇异值分解求解及实现
上面的一堆推导，只是为了说明对任意矩阵都存在奇异值分解，而没有讲述如何求解奇异值分解。以下内容来自《徐士良C常用算法程序集(第二版)》，一般实矩阵的奇异值分解：
用household变换和变形QR算法对一般实矩阵进行奇异值分解，得到左右奇异向量U、V及奇异值矩阵D。
[个人认为具体怎么求SVD，大家不要去记和理解了，要用的时候能找到源码，方便其他移植即可]
例：求下面两个矩阵A和B的奇异值分解，ε取0.000001
C语言代码：
徐士良老头写的，可读性很差
bmuav.c：
brmul.c：矩阵乘法
调用：
程序结果：
三、SVD应用实例
1. 基于SVD的图像压缩
这个例子比较简单，首先进行奇异值分解，得到奇异值矩阵，和左右奇异向量。然后由于只要很少的奇异值，就能包含绝大部分被分解的矩阵信息，因此我们挑选不同数量的奇异值，重构图像，比较差异。这边分别实现了灰度图、RGB三色图的SVD分解。【奇异值到底选多少，自己打印奇异值矩阵，从大到小排序的，小到什么程度就舍弃，实际情况实际操作。。。】
结果：
彩色图：
效果图：
注意：SVD压缩只是为了存储更少的数据来表达原始图像，在重构图像时，奇异值矩阵仍旧是要和原始图像大小一样的，只不过大部分地方用0填充罢了。
2 . 基于SVD的协同过滤推荐系统
这个例子比较有趣，推荐系统已存在很多年了。大家在网购时，商家总会根据大家的购买的历史记录给大家推荐新的商品及服务。实现方法有多种，这次只讲基于协同过滤的方法。所谓协同过滤，就是将用户和其他用户的数据进行对比来实现推荐的。前端输入的原始数据如下：【评分：0-5】
【后话：很严重的问题，就是当用户间没有交集，推荐系统就无法工作咯】
下面就构建一个餐饮网站的推荐系统。假设一个人在家决定外出吃饭，但是他并不知道该到哪去吃饭，该点什么菜。我们可以构建一个基本的推荐引擎，它能够帮助用户寻找没有尝过的菜肴，然后通过SVD来减少特征空间并提高反馈的速度。
a. 基本的推荐引擎
推荐系统的工作过程：给定一个用户，系统会为此用户返回N个最好的推荐，为了实现这一点我们需要做：
寻找用户没有评级的菜肴
在用户没有评级的物品中，对每个物品预计一个可能的评级分数。也就是说，我们的系统认为用户可能会对物品的打分
对这些物品的评分从高到低排序，返回前N个
之前说将用户和其他用户的数据进行对比来实现推荐，那么我们借助什么手段预测评分呢？有两种方案：
基于用户的相似度：行与行之间的比较
基于菜肴的相似度：列与列之间的比较
【距离公式可采用欧氏距离、余弦距离、皮尔逊距离等等】
那么到底使用哪一种相似度呢？这取决于菜肴和用户的数目。无论基于哪种相似度，它的计算时间都会随着用户/物品的数量的增加而增加。对于大部分产品导向的推荐引擎而言，用户的数量往往大于商品的数量。因此这里采用基于菜肴的相似度计算。
各种相似度计算代码：
【机器学习是用Python写的，操作矩阵很方便，这边C语言很笨重，所以没有做到代码重用，XXX2表示SVD推荐系统时用的距离函数，XXX是标准推荐系统】
预测评价的原理：假设要预测用户A的第k个未评价菜肴的评分，我们可以遍历整个数据矩阵寻找用户A和其他用户都评价过的其他菜肴j，计算用户A和其他用户针对菜肴j的评价的相似距离，若有多个这种共同的评价，则累加相似度。最后的计算公式：
第k个菜肴的评分 = sum(累加的相似度 * A对j的评分 ) / 累加相似度
下面先给出主函数吧，否则太乱了：
标准推荐系统：
对于data矩阵，用户2，对应第三行，预测结果：
b. 基于SVD的推荐引擎
在数据矩阵非常稀疏时，基于SVD的推荐引擎性能就会比标准的好很多。我们利用SVD将所有菜肴隐射到一个低维空间中，再利用和前面一样的相似度计算方法来进行推荐。
对于矩阵 data_2，用户2，对应第三行，预测结果：
c. 现实中的挑战
（1）如何对推荐引擎进行评价
我们既没有预测的目标值，也没有用户来调查对他们预测结果的满意度。我们这时可以将已知的评价结果去掉，然后对他们进行预测，最后计算预测值和真实值之间的差异。通常用于推荐引擎评价的指标是最小均方根误差，它 首先计算均方误差的平均值，然后取其平方根 【sqrt((sum((a-b)*(a-b)))/num)】
（2）真实的系统
这边代码为了保证可读性，没有效率：
a.我们不必在每次预测评分时都对数据矩阵进行SVD分解。在大规模数据集上，频繁进行SVD分解，只会拖慢效率。在真实系统中，SVD每天运行一次，并且还要离线运行。
b.规模扩展性的挑战：
数据矩阵很稀疏，我们有很多0，我们能否只存储非零元素来节省内存计算开销。
相似度计算也导致了计算资源浪费，每次需要一个推荐得分时，都要计算很多物品的相似度得分，这些相似度得分能否被其他用户重复使用？实际系统中，会进行离线计算，并保存相似度得分。
c.如何在缺乏数据时，给出好的推荐？
实际系统将推荐系统看成是搜索问题，我们可能要使用需要推荐物品的属性。在上述餐馆例子里，我们可以通过各种标签来标记菜肴，比如素食、美式烤肉、价格贵等。同时我们也可以将这些属性作为相似度计算所需要的数据。这个被称为基于内容的推荐。
所有代码下载地址：
<a target="_blank" href="http://download.csdn.net/detail/jinshengtao/8188243">http://download.csdn.net/detail/jinshengtao/8188243</a>