本次的講解主要内容如下：
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>