PCA之奇異值分解

05-17

PCA之奇異值分解

來自專欄我的ai之路

本文接上文講到特徵值分解後，繼續探究矩陣分解的另一種方法——奇異值分解。

其實在大學期間，我們的線性代數課程是沒有教授奇異值分解這個部分的，具體原因不得而知，但是在接觸了機器學習之後，發現奇異值分解在數據降維、隱語義分析、圖像等領域都有著廣泛的運用，因此是一個非常重要的知識點。本著掌握該知識點的目的，學習了一些相關教材和視頻，繼而做個總結。不過有一些前置的知識點我要在前面列出來，否則描述起來會比較困難。

向量之間互相正交。正交的含義體現在數值計算上，就是兩個向量之間的內積為0；體現在幾何意義上就是兩個向量的夾角為90度，即互相垂直。
實對稱矩陣指的是矩陣元素均為實數，且為n維的方陣，其中矩陣元素 $A_{ij}= A_{ji}$ ，實對稱矩陣有一些很有用的性質：實對稱矩陣的轉置還是自身 $A^T=A$ ，這個很容易就能判斷出來；另外實對稱矩陣的不同特徵值對應的特徵向量互相正交。這個證明很簡單，就不列出來了，有興趣的同學可以自己推到。
正交矩陣：正交矩陣指的是這樣一個矩陣A， $AA^T=A^TA=I$ ，其中I表示單位矩陣，因此正交矩陣的行向量為單位向量，且兩兩正交，列向量也為單位向量，且兩兩正交。簡單推導一下：設矩陣 $A=left[ egin{matrix} vec v_1 \vec v_2 \vec v_3 end{matrix} ight]$ ,其中 $vec v_i$ 為行向量，行向量之間互相正交，因此 $A^T=left[ egin{matrix} vec v_1^T &vec v_2^T&vec v_3^T end{matrix} ight]$ , $AA^T=left[ egin{matrix} vec v_1 \vec v_2 \vec v_3 end{matrix} ight]left[ egin{matrix} vec v_1^T &vec v_2^T&vec v_3^T end{matrix} ight]$ ,因為 $vec v_i$ 為單位向量，且向量之間正交，因此 $vec v_i vec v_i^T=1$ , $vec v_ivec v_j^T=0$ ,因此最後得到的是單位矩陣。因為逆矩陣的定義，因此正交矩陣的逆矩陣就是其原矩陣的轉置： $A^{-1}=A^T$
基於上述的性質，實對稱矩陣總能進行相似對角化，它的特徵基（上文描述過的）是一個正交陣。

奇異值分解

之前講到的特徵值分解只能運用於方陣，對於普通的非方陣就不適用了，但是奇異值分解更為普適，它能應用於各種維度的矩陣。首先我們將奇異值分解的定義和公式先放出來，讓我們先有個印象：假設當前有一個矩陣 $A in Re^{m*n}$ ,它能夠通過奇異值分解，得到如下等式：

$A=USigma V^T$ ,其中 $U in Re^{m*n}$ ,U為左奇異矩陣，列向量互相正交且為單位向量； $Sigma in Re^{n*n}$ ,且為對角陣，其中主對角元素為U對應列向量的奇異值； $V in Re^{n*n}$ ，為右奇異矩陣，列向量互相正交且為單位向量。現在有疑問了，這個奇異矩陣裡面的列向量到底是什麼呢？奇異值又是什麼呢？下面我將列出求解奇異矩陣和奇異值的過程，然後給出其幾何意義。

奇異值分解求解過程

首先我們回顧一下特徵值分解，它的目標是將一個坐標繫上的矩陣變換轉換到另一個坐標繫上，可以明確的是特徵值分解中，坐標系之間的維度是相同的。但是對於一個m*n的矩陣，它的變換並不會保持在相同的維度，與特徵值分解不同的是，它的目標是找到這樣一個變換，將行向量組成的空間（下面簡稱行空間）中的一組正交單位基轉換到列向量組成的空間（下面簡稱列空間）中的一組正交單位基。說得白話一點就是轉換的兩個坐標系的維度現在不一樣了。用圖來表示的話，如下所示：其中 $vec v_i$ 表示行空間的基向量， $vec u_i$ 表示列空間的基向量，而 $sigma_i$ 為對角陣 $Sigma$ 中主對角上對應的元素。

上圖表示為變換A能夠將行空間中的基向量變換到列空間中的基向量的同方向，由於基向量均為單位向量，因此還會有縮放的操作。用公式表示就是： $AV=USigma$ ，我們的目標就是要求解V，U和 $Sigma$ 。

備註：行空間和列空間的空間維度可能不同，但是由於存在零空間，且零空間的向量對應的 $sigma_i=0$ ，因此也滿足上式等式。在PCA中，SVD用於協方差矩陣，用於降維，原理簡單說就是協方差矩陣在行空間上存在向量能夠用其他向量線性組合表示，因此有信息冗餘，最大線性無關向量數為r，因此對應r個奇異值非0,其他奇異值為0的維度可以忽略這個維度的特徵，起到降維的作用，具體的下一篇文章講解，這裡只是提一下。

那麼怎麼求解所有的矩陣呢？

1、先得到A的表達式： $A=USigma V^{-1}$ ,因為V為正交陣，因此 $A=USigma V^{T}$

2、我們可以利用特徵向量的相似對角化來幫助我們求解，因此要構造一個對稱方陣，因為 $(A^TA)^T=A^TA$ ,且 $A^TA in Re^{n*n}$ ，因此可以可以對上述步驟1的等式兩邊左乘一個 $A^T$ ,因此得到:

$egin{equation} egin{aligned} A^TA&=VSigma^{T}U^TUSigma V^T\ &=VSigma^{T}ISigma V^T\ &=Vleft[ egin{matrix} sigma_1^2&0&cdots&0 \0&sigma_2^2&cdots&0 \vdots&vdots&ddots\0&0&cdots&sigma_n^2 end{matrix} ight]V^T end{aligned} end{equation}$

可以看到該等式就是前一篇文章講到的特徵值分解等式，其中V為實對稱方陣 $A^TA$ 的特徵向量歸一化後構成的矩陣，而中間的對角陣就是特徵向量對應的特徵值，且特徵值為非負的。因此可以用求特徵向量和特徵值的方法來求解V和 $Sigma$ 。

3、現在只剩下U矩陣未得到了，其實由步驟2，我們可以舉一反三，利用實對稱方陣 $AA^T$ 來得到U。同樣對步驟1的等式兩邊右乘一個 $A^T$ ,得到：

$egin{equation} egin{aligned} AA^T&=USigma V^TVSigma^{T}U^T\ &=USigma ISigma^T U^T\ &=Uleft[ egin{matrix} sigma_1^2&0&cdots&0 \0&sigma_2^2&cdots&0 \vdots&vdots&ddots\0&0&cdots&sigma_n^2 end{matrix} ight]U^T end{aligned} end{equation}$

同樣，我們可以得知U矩陣的列向量為方陣 $AA^T$ 的歸一化後的特徵向量，而其特徵值與 $A^TA$ 的是一樣的。求解U就很簡單了，與V類似的方法。

奇異值分解的意義

首先與特徵值分解進行類比，其實前面已經說到方陣對於特徵向量的變換相當於只做了縮放操作，它並沒有改變原空間的維度，因為它找的特徵向量就是要滿足這樣的條件，即矩陣變換後，特徵向量的只是做了縮放的操作。

而奇異值能夠做到兩個不同基底的向量空間之間的空間映射。具體效應如圖：（取自百度百科）

首先矩陣 $V^*$ (其實就是 $V^T$ )將向量做一個基變換，換到V的正交標準向量表示的空間上，然後通過對角陣變換，將向量進行縮放，縮放的程度對應於主對角線上的奇異值，然後再做一個U的變換，相當於將V的向量空間基變換到U的向量空間。綜合來講，對角陣中的奇異值對U和V兩個以不同基向量為底的向量空間做了空間映射，相當於中間橋樑的作用。在空間映射中，V中的某些維度會縮放成0，表現為對應奇異值為0。

從昨天討論特徵分解的角度，假設有向量 $vec v$ 是在U中正交標準向量組成的向量空間中的表示，此時有個矩陣變換M，它是以V里的正交標準向量構成的向量空間中變換矩陣，我要知道M在U中正交標準向量構成的向量空間中的表示，此時：

1、首先利用基變換矩陣，得到向量在V坐標系（簡化描述了）的向量表示： $Vvec v$

2、然後在新的V坐標繫上，對向量進行矩陣的線性變換： $MVvec v$ ，得到了V坐標系中轉換後的向量。

3、最後需要將V坐標系的新向量轉換回到U坐標系，因此對步驟2的得到的向量進行逆基變換： $U^{-1}MVvec v$ ,最後得到我想知道的變換後的向量在U坐標繫上的向量表示。

$U^{-1}MV$ 得到的應該是一個對角陣，與M表示的是同一種變換，但是是在U坐標系中的表示。與特徵分解不同的時，空間映射過程中，會有些基向量映射為零向量，而這些在PCA中就表示冗餘的信息量。

後記

奇異值分解的東西大體描述完了，鑒於本人的水平原因，可能會有些理解或者表述不清楚，希望各位大大指正。下一篇就準備聚焦在PCA上，然後利用SVD來解決PCA這個問題。

reference：

百度百科

MIT公開課

cs229公開課