動機
兩個相同的列把同一效果描述了兩次。擬合問題可以決定兩個係數的和,卻不能決定這個和應怎樣分配。任選一種分配可能是有效的最小二乘答案,但不能稱它為唯一答案。最小範數規則增加第二個明確決定:在所有最佳擬合中,選取指定座標下最短的係數向量。
微小奇異值帶來另一種困難。它在精確算術中非零,因此係數仍被決定;但極小的數據改動可使該係數大幅變動。當數據無法分辨這個方向時,捨棄它可以合理。然而這一步改變了模型,並非用代數證明原矩陣的秩較小。
本節從奇異值分解推導這兩個決定,涵蓋長方形及零秩情況。先前 QR 單元假設滿列秩。
定義
定義 15.1.1
(奇異值分解)
設 、,秩為 。一個完整的奇異值分解為
其中 、 正交。長方形對角矩陣 有上述 個正元素,其餘為零。 分別是 的列向量。
定義 15.1.2
(偽逆與最小範數最小二乘解)
Moore–Penrose 偽逆定義為
若 ,兩個和都是空和,故 、。行空間為 ,零空間為 。最小二乘解在所有 中最小化 ;最小範數解則在整個最小二乘解集合中最小化 。這是兩階段優化,並非對固定正數 最小化 的同一目標。
定義 15.1.3
(閾值秩與截斷解)
給定明確的絕對閾值 ,定義
嚴格不等式指定了恰好等於閾值時如何處理。相對閾值如 ,或按測量不確定性、捨入預算制定的閾值,都需要明確說明其意義。沒有一個閾值能普遍適用於所有單位和雜訊尺度。
定理/命題
定理 15.1.4
(全部最小二乘解與唯一最短解)
對每個實長方形矩陣 及每個 ,全部最小二乘解為
其擬合向量及殘差唯一:
唯一最小範數解是 ,其範數平方為
不加「最小範數」限制時,最小二乘係數向量唯一,當且僅當 ,亦即 滿列秩。解的存在不要求滿秩,也不要求方程相容。
定理 15.1.5
(奇異值截斷保證了甚麼)
令 ,必要時把奇異值序列補零,則截斷給出
其中保留全部正奇異值時令 。若 ,則
是 的唯一最小範數最小二乘解,亦是把原矩陣 的係數限制在 後的唯一殘差極小者。它未必在原來所有係數向量中最小化殘差。若 ,則 、。
證明思路或證明
為何 SVD 存在
證明
(由 的譜定理得出存在性)
實對稱譜定理適用於 。因 ,其特徵值非負。選取標準正交特徵基 ,把正特徵值 排在前面。由 得 ,再由秩與零度定理可知恰有 個正特徵值。對每個正值令 ,則
若 對應零特徵值,則 ,所以 。把已有的 擴充成 的標準正交基。將任意向量按 展開,即證 。這裏以對稱譜定理為先備知識,給出存在性證明,並非建議藉形成 計算 SVD。形成該矩陣可使條件數平方,亦可能因捨入而抹去微小方向。
重複奇異值容許在相應子空間內選取不同標準正交基。因此個別奇異向量可以不唯一,但下述映射和投影保持相同。
分開能擬合與不能擬合的方向
證明
(奇異向量座標下的最小二乘解)
寫 、。由正交不變性,
第二個和與 無關。取 可令第一個和的每項為零。其餘 個 座標可任意選取,正好對應 。變換回去便證明全部極小者的形式及最優殘差公式。
同時,
最後一個和的唯一最小值為零,故最小範數解存在且唯一,也包括 。等價地, 與零空間正交,因此每個 都滿足 。三角求解返回一個看來較短的答案,仍必須符合此正交條件;把自由變量設為零並不足夠。
直接相乘得
這兩者是投影到列空間及行空間的對稱正交投影。因此 、、、。這四個恆等式刻畫 Moore–Penrose 偽逆。為證唯一性,設另一矩陣 亦滿足它們。則 對稱且冪等,值域包含於 ,並因 而固定每個 ,故 就是同一正交投影 。同樣, 對稱且冪等,並滿足 :一個方向直接成立,而 推出 。因此 投影到行空間。由 ,每個 都在行空間內,且滿足 。先前已證行空間內原像唯一,故每個 都有 ,即 。這也證明結果不依賴奇異向量基的選擇。
補充而言,即使秩不足,正規方程 仍是最小二乘的充要條件。把 的殘差平方展開,若正規方程成立,交叉項為零,目標只增加 。反之,若某方向交叉項非零,沿合適符號作足夠小位移便可減少目標。正規方程刻畫整個仿射解族,並不選出最短成員。
證明透視
兩種唯一性位於不同空間
決定性的一步是正交變量替換 、。選擇它,是因為兩階段問題的兩個目標同時變得可分離: 正交保持殘差範數, 正交保持係數範數,而 把每個 只與一個 聯繫。證明沒有用到任何秩或相容性假設;正奇異值只用於對 解出 。
兩種唯一性來自不同的座標。擬合唯一,因為座標 被迫取定,這正是 到列空間的正交投影唯一。係數不唯一,因為 完全不進入殘差;它們參數化 。只有第二個目標,即係數範數,迫使它們為零;而且這是唯一的,因為它們的貢獻是平方和 。把列空間(擬合所在)與行空間及零空間(係數所在)分開,便不會把正確的投影唯一性論證誤用為係數唯一性論證。
截斷與最佳低秩近似
證明
(截斷公式與秩 下界)
在奇異向量座標下, 在被捨棄方向上是對角作用,譜範數就是最大的被捨棄奇異值。每個保留方向的係數 精確重現 ;其餘殘差座標保持為 。這證明截斷公式、係數界及限制空間上的殘差極小化,而沒有聲稱被捨棄方向在原數據中精確為零。
矩陣近似本身亦有有效最優證書。固定 ,令 的秩至多 。將 維空間 經 映射,其核必非平凡。選取單位向量 使 ,則
在第 個奇異值後截斷正好達到此界,故它是最佳秩至多 的譜範數近似。這個定理關於矩陣近似,本身並不決定特定測量問題的不確定性應支持哪個 。
秩揭示是數值任務,並非秩的定義
精確 SVD 以正奇異值揭示精確秩。算出的 SVD 則有捨入誤差。若結果由後向關係 支持,正交因子精確且 ,所報奇異值便描述這個鄰近矩陣,並有
以下直接證明,而非無解釋地訴諸穩定性。奇異值滿足
上界可取 的生成空間。下界方面,由維數公式,每個容許的 與 均有非平凡交集;該交集內的單位向量,其像範數至少為 。把 換成 ,每個像範數的變化至多 。雙向使用極小極大公式便得到擾動不等式。因此閾值若位於某奇異值的這個誤差範圍內,便不能建立穩健的秩判定。間隙是否存在、數據不確定性有多大,兩者都重要。具體 SVD 實作需要自身經論證的後向誤差預算;本節並未實作。
帶列主元的 QR 是另一種實用秩評估方法:每步選取剩餘殘差範數最大的列,再以正交變換三角化。在精確的秩 分解中可得
令 、,則全部極小者滿足 。設 得到基本解。記 、,真正的最小範數成員須最小化
故先解 ,再取 。此係數矩陣正定,因為 時 。這個推導解釋了基本解缺少的最小範數步驟,並非建議在要求高的實作中形成這組正規方程。完整正交分解亦可實現相同幾何。
浮點算術中,尾部 QR 區塊夠小、前導區塊條件可接受,都是需要量化的證據。只看對角大小的規則並不是 SVD 的秩定義。普通貪心列主元選擇是有用啟發法,但更強秩揭示界或奇異值估計需要額外分析。本節定義了程序及其精確解幾何,並沒有證明生產用帶列主元 QR 程式的普遍秩保證。
算例
例題 15.1.6
(重複列、非零殘差及全部極小者)
令
取 、、。奇異值為 ,且 。因此
全部極小者為 ,共同擬合向量為 ,共同殘差為 ,範數 。係數範數平方是 ,唯一最小點為 。基本解 的擬合同樣好,但範數較大,為 。不可消除的殘差與係數不唯一,是不同事實。
例題 15.1.7
(欠定精確擬合仍需選擇規則)
對 、,兩行線性無關,且
此公式適用於這個滿行秩矩陣,並非任意秩下的一般定義。它給出 。每個解均為 ,範數平方為 。因此精確系統雖有無窮多解,最小範數解仍唯一。把第三變量設為零得到 ,範數平方是五而非二。
例題 15.1.8
(閾值以捨棄弱方向換取較小係數)
取 、。精確秩為二。最小範數最小二乘解是 ,殘差範數 。第二數據改變 ,相應係數便改變 。
用 時只保留第一個奇異方向,故 、。對原數據的殘差為 ,範數為 ,而 。係數向量大幅縮小,代價是殘差稍增。代價是否可接受,取決於數據不確定性,並非一個沒有解釋的機器常數。閾值改變模型的秩;原來精確矩陣仍是秩二。
常見錯誤
反例模式
跨越秩改變時偽逆不連續
對 、,有 ,但 。 在範數下趨向 ,其偽逆卻不收斂。取 ,精確最小範數解在秩消失時由 跳至零。穩定計算不能消除原問題的這種敏感性。
即使固定 且 ,直接得到的也只是右端的絕對敏感性界:
按奇異向量展開即可證明,沿 改變時達到等號。相對係數誤差還依賴可能為零或很小的 ;忽略此分母不能得到有限普遍相對界。若同時擾動 並容許秩改變,則需更多假設。
常見錯誤
(三角矩陣的對角不是奇異值表)
三角矩陣的對角也不是奇異值表。對 ,兩個對角元素均為一,但 ,且 ,所以 。此例警告不能把任意未選主元的對角當作 SVD 檢查,並非聲稱反駁每一個有量化假設的帶列主元 QR 定理。
常見錯誤
(把自由變量設為零並不給出最短解)
消元或三角求解若把自由座標設為零,返回的是基本解。它是最小二乘解,但一般不是最小範數解。在重複列的例子中,基本解 的範數為 ,而 的範數為 。檢驗方法是與零空間正交: 與零空間向量 的內積為 ,所以它不是最短成員。
概念視角結構
秩、可分辨程度及係數度量的選擇
精確秩計算固定數據的非零奇異方向。數值秩記錄指定不確定性及閾值能分辨哪些方向。最小歐氏(Euclidean)範數選取指定座標內最短的係數;縮放未知量會改變這個度量,也可能改變選出的解。這是三個明確的建模決定,並非同一個自動答案的三種名稱。
小結
SVD 分開可達擬合與不可消除的殘差,也分開被決定的係數方向與零空間。偽逆選出唯一位於行空間內的最小範數解。截斷具有精確近似及受限擬合意義,但需要明確的分辨決定。精確秩、算出的秩估計及穩定實作相互相關,卻各有不同假設。
練習
快速檢查
(令 、。求 、全部最小二乘解、最小範數成員及最優殘差,並驗證正規正交條件。)
解答 · 答案
寫 ,則 ,其中 ,所以 。故 ,全部極小者為 。擬合向量為 ,得 ,範數 。直接相乘得 ,而 證明它在仿射解族內範數最小。
快速檢查
(令 、,基本解為 。用 QR 討論中的 推導最小範數解。再以 作 ,改為最小化 ,證明選出的物理向量 改變了。)
解答 · 答案
此處 、、,故 。方程 給出 ,另一座標亦為 。更改度量後,;其最短精確係數向量為 ,故 。兩個物理向量均滿足 ,但最小化不同範數。第二規則最小化 ,而非 。
快速檢查
(對 、 及嚴格規則 ,分別求 、、、 時的 、殘差範數及矩陣近似誤差。)
解答 · 答案
或 時,保留兩個正方向:,殘差範數一,近似誤差零。 時等於閾值者被捨棄:,殘差範數 ,近似誤差 。 時不保留任何方向:,殘差範數 ,近似誤差三。每種情況的原矩陣精確秩仍為二。
快速檢查
(某算出的 SVD 已有譜範數後向誤差預算 ,報告奇異值 、、。取閾值 ,只據此資訊可認證原矩陣哪些秩主張?解釋閾值秩二實際描述甚麼。)
解答 · 答案
原第二奇異值位於 ,第三位於 。兩個區間都跨過閾值,所以原矩陣的閾值秩可以是一、二或三。第一奇異值必高於閾值;這組特定區間亦保證三個值均為正,所以原矩陣精確秩為三。報告的閾值秩二描述算出因子代表的鄰近矩陣在指定嚴格截斷下的結果;誤差區間與閾值重疊時,它不能認證原矩陣有相同截斷決定。