Tag Archives: 最小平方法

約束最小平方問題

本文的閱讀等級:中級 令 為一個 階實矩陣,。如果線性方程 是不一致的 (即不存在解),實務的作法是將線性方程問題改為最小平方近似問題: , 其中 是2-範數 (見“向量範數”),即 與 的歐幾里得距離。根據正交原則,最小平方解 滿足正規方程 (normal equation) (見“從線性變換解釋最小平方近似”)。若 ,也就是說 的行向量 (column vector) 構成一個線性獨立集合,則存在唯一的最小平方解 。 如果最小平方解必須滿足某些束縛條件,則稱為約束最小平方問題 (constrained least-squares problem)。本文討論兩種常出現在多種應用場合的約束形式。線性約束最小平方問題是指束縛條件為線性方程[1]: , 其中 是一個 階實矩陣,。正則 (regularized) 最小平方問題限制未知向量的長度必須固定: 。 Advertisements

Posted in 線性代數專欄, 內積空間 | Tagged , , , , | 4 Comments

每週問題 December 29, 2014

這是最小平方法應用於矩陣之線性變換的問題。 Let be the vector space formed by real matrices. Let and . Consider the following transformation from to : . Determine a matrix that minimizes , where denotes Frobenius norm.

Posted in pow 內積空間, 每週問題 | Tagged , | Leave a comment

每週問題 July 21, 2014

這是內積空間於傅立葉級數的應用問題,取自“台聯大2014年碩士班招生考試試題 (電機類工程數學A)”。 Let be defined as follows: Also, define Find the coeffiicents such that is minimized.

Posted in pow 內積空間, 每週問題 | Tagged , | 3 Comments

費雪的判別分析與線性判別分析

本文的閱讀等級:高級 在許多現實應用中,我們往往要面對高維度 (多變數) 數據,為便利分析,降維 (dimension reduction) 常是一個必要的前處理工作。主成分分析 (principal components analysis) 是目前普遍被採用的降維技術 (見“主成分分析”)。主成分分析是一種非教導式學習法 (unsupervised learning),根據樣本自身的統計性質降維,並不在乎 (甚至不知道) 這些數據的後續應用。在機器學習領域,分類 (classification) 與回歸 (regression) 是兩個最具代表性的問題描述典範。所謂分類是指識別出數據點所屬的類別。本文介紹英國統計學家費雪 (Ronald Fisher) 最早提出的一個專為包含兩個類別樣本所設計的教導式 (supervised) 降維法,稱作費雪的判別分析 (Fisher’s discriminant analysis),隨後並討論三個延伸問題: 甚麼是線性判別分析 (linear discriminant analysis)?它與費雪的判別分析有何關係? 線性判別分析與最小平方法有甚麼關聯性? 費雪的判別分析如何推廣至多類別 (類別數大於2) 判別分析?

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

每週問題 January 27, 2014

這是最小平方法的正規方程的等價表達問題。 Let be an real matrix and . Show that is a least squares solution for if and only if is part of a solution to the larger system

Posted in pow 內積空間, 每週問題 | Tagged , | Leave a comment

每週問題 January 13, 2014

本週問題是利用奇異值分解表達最小平方近似解。 Let be an real matrix, , with . Suppose the singular value decomposition of is , where is an real orthogonal matrix, is an real orthogonal matrix, and is , with and for all . Show that the least … Continue reading

Posted in pow 二次型, 每週問題 | Tagged , | Leave a comment

凸優化──凸函數的最小化

本文的閱讀等級:中級 凸優化 (convex optimization) 是最佳化理論的一個分支。顧名思義,凸優化探討定義於一個凸集的凸函數最小化問題[1]。令 為凸集且 為凸函數。我們的目標要找出一個點 ,使得每一 滿足 。在最佳化理論中, 稱為可行域 (feasible set), 稱為目標函數, 稱為全域最佳解[2]。任一凸優化問題皆可表示為下列標準型: 其中 是凸函數, 是仿射函數,即 ,,。最小平方法與線性規劃是兩種常見的凸優化問題。令 為一個 階實矩陣, 為 維實向量, 為 維實向量。最小平方法是一個無約束 (unconstrained) 最佳化問題: 。 線性規劃標準型問題具有下列形式 (見“線性規劃 (一):標準型問題”): 本文介紹凸優化的一個重要性質:任一局部最佳解 (亦稱相對最佳解) 即為全域最佳解。所謂局部最佳解 是指存在 使得集合 中每一點 滿足 。

Posted in 線性代數專欄, 仿射幾何 | Tagged , , , | 4 Comments

矩陣導數

本文的閱讀等級:中級 令 為一個多變量可導函數,或記為 ,其中 。我們定義 的梯度 (gradient) 為下列 維向量: , 其中 的第 元是 對變數 的一階偏導數 。如果給定 個多變量函數 ,則有 個梯度 。將所有 梯度合併成一個矩陣,取轉置,可得 階矩陣 , 稱為 Jacobian 矩陣。另一方面,如果 是二階可導函數,我們可以計算 的每一元 的梯度,如此可得 , 稱為 Hessian 矩陣。請注意,梯度 的 Jacobian 矩陣即為 的 Hessian 矩陣 (見“Jacobian … Continue reading

Posted in 特別主題 | Tagged , , , , , | 26 Comments

每週問題 December 24, 2012

這是最小平方近似函數練習問題。 Let be the continuous functions on the interval with the inner product defined by . Find the closest straight line to over .

Posted in pow 內積空間, 每週問題 | Tagged , | Leave a comment

偽逆矩陣與轉置矩陣的二三事

本文的閱讀等級:高級 令 為一個 階實矩陣且 。設矩陣 的奇異值分解為 ,其中 和 分別是 階和 階正交矩陣 (orthogonal matrix),滿足 和 , 階矩陣 包含可逆分塊 ,主對角元 為非零奇異值。偽逆矩陣 (pseudoinverse) 定義為下列 階矩陣 (見“Moore-Penrose 偽逆矩陣”): , 其中 是 階對角矩陣。偽逆矩陣 的表達式即為其奇異值分解。見下例 (取自“SVD 於剖析線性方程的應用”): 偽逆矩陣計算如下: 。 偽逆矩陣 與轉置矩陣 皆為 階,兩者同為 映至 的線性變換。下文以問答方式解說偽逆矩陣與轉置矩陣的一些性質。開始之前,請讀者先參閱背景文章:“奇異值分解(SVD)”和“通過推導偽逆矩陣認識線性代數的深層結構”。

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