本文将分别介紹特征值分解、奇異值分解、及PCA的相關理論概念。
文章末尾将給出Householder矩陣變換、QR算法求解特征值、特征向量的代碼
其中，特征值分解、奇異值分解的相關内容，轉載自：
<a target="_blank" href="http://www.cnblogs.com/LeftNotEasy/archive/2011/01/19/svd-and-applications.html">http://www.cnblogs.com/LeftNotEasy/archive/2011/01/19/svd-and-applications.html</a>
考慮到本文50%以上的部分不是那個哥們的部落格原文，是以我搞成原創标題了。。。。
一、特征值與特征向量的幾何意義
1. 矩陣乘法
在介紹特征值與特征向量的幾何意義之前，先介紹矩陣乘法的幾何意義。
矩陣乘法對應了一個變換，是把任意一個向量變成另一個方向或長度的新向量。在這個變化過程中，原向量主要發生旋轉、伸縮的變化。如果矩陣對某些向量隻發生伸縮變換，不産生旋轉效果，那麼這些向量就稱為這個矩陣的特征向量，伸縮的比例就是特征值。
比如：
，它對應的線性變換是下面的形式形式：
因為，這個矩陣乘以一個向量(x,y)的結果是：
。由于矩陣M是對稱的，是以這個變換是一個對 x , y 軸的一個拉伸變換。【當M中元素值大于1時，是拉伸；當值小于1時，是縮短】
那麼如果矩陣M不是對稱的，比如：
，它所描述的變換如下圖所示：
這其實是在平面上對一個軸進行的拉伸變換【如藍色箭頭所示】，在圖中藍色箭頭是一個最主要的變化方向。變化方向可能有不止一個，但如果我們想要描述好一個變換，那我們就描述好這個變換主要的變化方向就好了。
2. 特征值分解與特征向量
如果說一個向量v是方陣A的特征向量，将一定可以表示成下面的形式：
λ為特征向量 v 對應的特征值。特征值分解是将一個矩陣分解為如下形式：
其中，Q是這個矩陣A的特征向量組成的矩陣，Σ是一個對角矩陣，每一個對角線元素就是一個特征值，裡面的特征值是由大到小排列的，這些特征值所對應的特征向量就是描述這個矩陣變化方向（從主要的變化到次要的變化排列）。也就是說矩陣A的資訊可以由其特征值和特征向量表示。
對于矩陣為高維的情況下，那麼這個矩陣就是高維空間下的一個線性變換。可以想象，這個變換也同樣有很多的變換方向，我們通過特征值分解得到的前N個特征向量，那麼就對應了這個矩陣最主要的N個變化方向。我們利用這前N個變化方向，就可以近似這個矩陣（變換）。
總結一下，特征值分解可以得到特征值與特征向量，特征值表示的是這個特征到底有多重要，而特征向量表示這個特征是什麼。不過，特征值分解也有很多的局限，比如說變換的矩陣必須是方陣。
二、奇異值分解
1. 奇異值
特征值分解是一個提取矩陣特征很不錯的方法，但是它隻是對方陣而言的，在現實的世界中，我們看到的大部分矩陣都不是方陣，比如說有N個學生，每個學生有M科成績，這樣形成的一個N * M的矩陣就不可能是方陣，我們怎樣才能描述這樣普通的矩陣呢的重要特征呢？奇異值分解可以用來幹這個事情，奇異值分解是一個能适用于任意的矩陣的一種分解的方法：
分解形式：
假設A是一個M * N的矩陣，那麼得到的U是一個M * M的方陣（稱為左奇異向量），Σ是一個M * N的矩陣（除了對角線的元素都是0，對角線上的元素稱為奇異值），VT(V的轉置)是一個N * N的矩陣（稱為右奇異向量）。
2. 奇異值與特征值
那麼奇異值和特征值是怎麼對應起來的呢？我們将一個矩陣A的轉置乘以 A，并對(AAT)求特征值，則有下面的形式：
這裡V就是上面的右奇異向量，另外還有：
這裡的σ就是奇異值，u就是上面說的左奇異向量。【證明那個哥們也沒給】
奇異值σ跟特征值類似，在矩陣Σ中也是從大到小排列，而且σ的減少特别的快，在很多情況下，前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上了。也就是說，我們也可以用前r（ r遠小于m、n ）個的奇異值來近似描述矩陣，即部分奇異值分解：
右邊的三個矩陣相乘的結果将會是一個接近于A的矩陣，在這兒，r越接近于n，則相乘的結果越接近于A。
三、PCA主成份分析
主成分分析(PrincipalComponents Analysis。即PCA，也稱為K-L變換)，是圖像壓縮中的一種最優正交變換。PCA用于統計特征提取構成了子空間法模式識别的基礎。它從圖像整體代數特征出發，基于圖像的總體資訊進行分類識别。PCA的核心思想是利用較少數量的特征對樣本進行描述以達到降低特征空間維數的目的。
1. PCA理論
給定一副N*N大小圖像，将它表示成一個N2*1維向量，向量中元素為像素點灰階，按行存儲，如下列公式分别表示第i張圖檔和n張圖檔平均值：
令N2*n矩陣X為：
注意，矩陣減去平均值相當于将坐标系原點移動到平均值位置。
設Q=XXT，則Q是一個N2* N2矩陣：
,Q是方陣
,Q是對稱矩陣。
,Q被成為協方差矩陣，
,Q的資料量非常龐大
那麼，X中的每個元素xj可以被如下表達：
其中,ei是Q中非零特征值對應的特征向量。由特征向量e1,e2,…,en組成的空間叫做張成特征空間。對于N*N圖像，e1,e2,…,en是N2*1維互相正交的向量。尺度gji是xj在空間中的坐标。
2. 實作PCA
為了降維，可以對特征值設定門檻值或按照其他準則，尋找協方差矩陣Q中前k個特征向量。這裡Q十分龐大，對于一副256*256的圖像，Q的大小為65536*65536！替代方案是，考慮矩陣
.P和Q都是對稱矩陣
.P≠QT
.Q的大小是N2*N2，而P大小為n*n
.n為訓練樣本圖像數量，通常n<<N
設e是矩陣P的特征值λ對應的特征向量，則有：
這裡，X*e也是矩陣Q的特征值λ對應的特征向量【這是用求特征值分解方法，下面介紹用SVD方法】
3. PCA與奇異值分解SVD
任何一個m*n矩陣都能進行奇異值分解，拆分為3個矩陣相乘的形式。由于SVD得出的奇異向量也是從奇異值由大到小排列的，按PCA的觀點來看，就是方差最大的坐标軸就是第一個奇異向量，方差次大的坐标軸就是第二個奇異向量…。我們可以對Q進行奇異值分解。
.U就是QQT的特征向量
.V就是QTQ的特征向量
.D中奇異值的平方就是QQT和QTQ的特征值
=======================================================================================================================
上面講了一大堆，就是為了下一篇PCA人臉識别做鋪墊的，給你一副圖像，要從圖像庫中得到比對的圖像，怎麼弄？如果是兩兩做像素點比較是不可能完成的任務，時間上廢掉了。如果用其他特征點代替也許可以，但容易漏檢吧，這邊不擴充。我們必須對圖像資料的協方差矩陣進行降維，是以用到了PCA。
而具體如何實作PCA呢？關鍵是特征值及相應特征向量的求取。matlab有個eig函數，opencv也有相應的函數。由于不想被别人牽制，我自己查了資料，發現QR算法可以用來求實對稱矩陣的全部特征值和特征向量。【雅可比算法也可以，就是速度太慢了；而上面介紹的SVD實作PCA還沒見過，文獻上說SVD和PCA是等價的】
以下内容，來自《C常用算法程式集第二版》，這絕對是搞科研的好書！
在用QR算法求解特征值和向量之前，必須将實對稱矩陣轉化為三對角矩陣。【由于我們的協方差矩陣是實對稱矩陣，是以不用轉化為Hessen berg矩陣，QR算法是一個疊代的過程，具體算法太長了，我不貼出來了，有需要的，自己去下載下傳這本書的PDF文檔或其他資料】
1.約化對稱矩陣為三對角矩陣的Householder變換法：
例：
【其他高維矩陣也行，大家可以把資料存在txt文本中，然後讀取進來】
代碼：
計算結果：
即上述計算結果傳回的三對角陣T為：
2.下面，我們将在三對角矩陣的基礎上使用QR算法計算全部特征值和特征向量
例，同樣對上面那個5階矩陣，先求三對角矩陣，再求其全部特征值和特征向量
最大疊代次數為60，誤差為0.000001
這裡，又把householder貼了一遍。。。
這裡，我們要注意：
數組q中第j列為數組b中第j個特征值對應的特征向量