Tag Archives: SVD

線代膠囊──奇異值分解

本文的閱讀等級:中級 令 為一個 階複矩陣。下式稱為 的奇異值分解 (singular value decomposition,簡稱 SVD): , 其中 是一個 階么正矩陣 (unitary matrix),滿足 , 稱為左奇異向量; 是一個 階么正矩陣,滿足 , 稱為右奇異向量; 是一個 階矩陣,, 和 ,,稱為奇異值。 若 是實矩陣,只要將 改為 即可,這時 和 稱為正交矩陣 (orthogonal matrix)。下面介紹一個簡短的奇異值分解推導法。 Advertisements

Posted in 線性代數專欄, 二次型 | Tagged , , | 3 Comments

主成分分析與奇異值分解

本文的閱讀等級:高級 給定一份樣本大小為 的數據 ,其中 是 維實向量,記錄 個變數的觀測值。所有的數據點 扣除平均數向量 可得 階離差矩陣 (deviation matrix) ,表示如下: , 其中 是第 個數據點的第 個變數值,也就是說, 的每一列 (row) 對應一個數據點,每一行 (column) 對應一個變數。假設 不存在常數行,即每個變數總是存在若干變異。如欲將數據予以標準化 (每一變數的平均數等於 ,變異數等於 ),將 的每一行的所有元除以該變數的樣本標準差 (樣本變異數的平方根),即有 , 其中 是第 個變數的樣本變異數, 是第 個變數的樣本平均數 (見“樣本平均數、變異數和共變異數”)。令 。標準化後的離差矩陣可表示為 。當數據集的變數總數 很大或變數具有相關性時,主成分分析 (principal … Continue reading

Posted in 線性代數專欄, 二次型 | Tagged , , , , , , , , , , | 4 Comments

主成分分析

本文的閱讀等級:高級 美國作家梭羅 (Henry D. Thoreau) 在《湖濱散記》談到他的幽居生活時,說道[1]: 我們的生活消耗在瑣碎之中。一個老實的人除了十指之外,便不必有更大的數字了,頂多加上十個足趾,其餘不妨勉強一下。簡單,簡單,簡單啊!我說,最好你的事祇兩三件,不要一百件或一千件;不必一百萬一百萬地計算,半打不夠計算嗎?總之,賬目可以記在大拇指甲上就好了。 我們也許不能複製梭羅在瓦爾登湖 (Walden) 的簡單生活,但是我們永遠可以通過化繁為簡來改善現況。處於資訊爆炸的時代,我們不免要面對變數很多且樣本數很大的資料。在分析高維度 (變數很多) 數據時,降維 (dimension reduction) 常是一個必要的前處理工作。主成分分析 (principal components analysis,簡稱 PCA) 由英國統計學家皮爾生 (Karl Pearson) 於1901年提出[2],是一種降低數據維度的有效技術。主成分分析的主要構想是分析共變異數矩陣 (covariance matrix) 的特徵性質 (見“共變異數矩陣與常態分布”),以得出數據的主成分 (即特徵向量) 與它們的權值 (即特徵值);透過保留低階主成分 (對應大特徵值),捨棄高階主成分 (對應小特徵值),達到減少數據集維度,同時保留最大數據集變異的目的。本文從線性代數觀點介紹主成分分析,並討論實際應用時可能遭遇的一些問題。

Posted in 機器學習 | Tagged , , , , , , , , , | 19 Comments

線性變換觀點下的奇異值分解

本文的閱讀等級:中級 1960年代初以前,奇異值分解 (singular value decomposition,簡稱 SVD) 普遍被視為一個模糊的理論概念,原因在於當時並不具備實際可行的算法。自從美國計算機科學教授格魯布 (Gene Golub) 與卡韓 (William Kahan) 於1965年率先發表了第一個有效的算法後,奇異值分解的價值才逐漸受到學者肯定,至今已成為線性代數中應用最廣的矩陣分解式[1]。為甚麼奇異值分解這麼重要?這個問題可以從兩個層面加以剖析:奇異值分解的運作原理是甚麼?奇異值分解有哪些經典的應用?本文針對第一個問題提供部分解答。我們從線性變換觀點解釋奇異值分解的運算與意義,並藉此聯繫線性代數的一些核心概念,如值域、核、基本子空間、正交基底和座標變換。 (關於奇異值分解的推導和應用請參閱“奇異值分解專題”列舉的相關文章。)

Posted in 線性代數專欄, 二次型 | Tagged , , , , , , , , | 4 Comments

條件數

本文的閱讀等級:高級 當一個線性系統受到極微小的擾動即可引發方程解劇烈變化時,我們將無從信任計算結果,便稱它是病態系統 (見“病態系統”)。條件數 (condition number) 是矩陣運算誤差分析的基本工具,它可以度量矩陣對於數值計算的敏感性與穩定性,也可以用來檢定病態系統。本文通過一個簡單的線性方程擾動問題介紹條件數的推導過程,推演工具是矩陣範數 的定義所含的兩個不等式 (見“矩陣範數”): , 。

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , , , , , , | 2 Comments

SVD 於矩陣近似的應用

本文的閱讀等級:高級 在一些涉及資料壓縮、特徵抽取或雜音消除的分析應用中,我們常希望得到一個矩陣的最佳近似矩陣,並透過設定矩陣的秩來控制近似誤差,這個問題稱為矩陣近似。詳細的問題陳述如下:若 為一個 階實矩陣,求同尺寸矩陣 使最小化 ,並滿足 且 。奇異值分解 (singular value decomposition) 提供了最佳矩陣近似的答案,由於具備這個特性再加上優異的數值穩定性,奇異值分解已逐漸成為應用最廣泛的矩陣計算法之一。

Posted in 線性代數專欄, 應用之道 | Tagged , , , , , , | 1 Comment

矩陣範數

本文的閱讀等級:中級 幾何向量 的大小表現於其長度 (原點至向量端點的歐氏距離),那麼矩陣 的大小應如何度量呢?矩陣的大小度量稱為矩陣範數 (norm),記為 。佈於相同數系 ( 或 ) 且尺寸相同的矩陣集合構成一個向量空間,因此最直接的度量方式是仿造向量長度來定義矩陣範數。令 階矩陣 的行向量 (column vector) 為 ,其中 。Frobenius 範數定義如下: 。 Frobenius 範數 也可以由下式算得: 。 直接展開計算可驗證上面二式相等: 。 另外,Frobenius 範數與 的奇異值有關。令 ,,,為 的奇異值,其中 。下式成立 (證明見“SVD 於矩陣近似的應用”): 。

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , , , , | 5 Comments

奇異值分解的幾何意義

本文的閱讀等級:高級 理解線性變換 的一個有效途徑是透過解釋其幾何意義來呈現向量從空間 經過 映射至空間 的變化性質。實際作法可由兩方面著手,一是在輸入空間 和輸出空間 中分別挑選出適當的基底,藉由基底之間的映射關係解析線性變換,這個結果稱為對角化;二是固定輸入向量 的某些幾何性質,從觀察輸出向量 的變化情況來瞭解 的作用。本文採用上述兩種方法解說奇異值分解 (singular value decomposition,簡稱 SVD) 的幾何意義 (見“奇異值分解 (SVD)”)。

Posted in 線性代數專欄, 二次型 | Tagged , , , , , , | 10 Comments

矩陣與複數的類比

本文的閱讀等級:高級 定義於向量空間 的任一線性變換可以用一個 階複矩陣表示 (參考某基底)。除了少數特殊矩陣,如對角矩陣、投影矩陣、旋轉矩陣,和鏡射矩陣等,學者經常無法清楚地掌握矩陣變換的確實行為,主要原因是人們很難想像高維 () 向量空間,遑論向量在這些空間中的變換。欲洞察任意方陣的映射行為雖非易事,但也不是全然無跡可循,本文介紹一個認識矩陣作為的方法──透過矩陣與複數的類比來區分界定重要的特殊方陣。對複矩陣陌生的讀者,請先閱讀背景文章 “從實數系到複數系”。

Posted in 線性代數專欄, 二次型 | Tagged , , , , , , , , , | 21 Comments

SVD 於剖析線性方程的應用

本文的閱讀等級:高級 考慮線性方程 ,其中 是 階實矩陣, 是 維向量,並設 。在一般情況下,高斯消去法是最普及的標準求解演算法,但假設我們已知矩陣 的奇異值分解 (SVD),那該如何運用這個優勢來計算方程式解?在“通過推導偽逆矩陣認識線性代數的深層結構”,我們曾經討論過這個問題,並從奇異值分解導出僞逆矩陣,本文則針對該文提出迴響及補充,用意是藉由奇異值分解產生的基底剖析線性方程的解。對奇異值分解陌生的讀者,請先參考“奇異值分解 (SVD)”。

Posted in 線性代數專欄, 二次型 | Tagged , , , , , , | 3 Comments