本節討論:在給定的矩陣擾動下,哪些關於秩的資訊得以保留;這與上一單元殘差與敏感度的分析是不同的問題。全程使用實有限矩陣()與譜範數。
精確整數也可能對擾動敏感
設 的奇異值為 ,其中 。其精確秩 是嚴格為正的奇異值數目。這個敘述針對一個精確矩陣。測量值或儲存的近似矩陣 可以十分接近 ,卻不具有相同的精確秩: 的秩為一,而 對每個 都有秩二,無論 多小。
前一篇低秩近似章節證明,當 ,令秩降至低於 所需的最小譜範數擾動大小為 。事實上,小於 的擾動不可能產生秩至多為 的矩陣;擾動 恰好達到該距離。在另一個方向上,若 ,則對每個 ,擾動 都使秩增加一;新的奇異值可能需要重新排序。若 ,任選單位向量 和 ,則每個 的 都有秩一。因此只要秩未達最大值,它便可能因任意小擾動而上升。若 ,秩不可能再上升,而且譜範數小於 的擾動會保留秩 。
閾值是一項明確決定
定義 6.2.1
(閾值秩)
對選定的容差 ,定義閾值秩 。嚴格大於的約定明確處理邊界。它不必等於精確秩:不大於 的正奇異值被刻意視為未能分辨。容差應反映問題的測量及計算誤差尺度;沒有這些背景,不能宣稱某個數值普遍正確。把資料矩陣乘以純量 ,會使所有奇異值乘以 ,因此絕對閾值帶有單位。
定理 6.2.2
(奇異值的穩定性)
假設精確矩陣 具有相同大小,且滿足 。奇異值的穩定性不等式是
證明
(極大極小公式與三角不等式)
為完整起見,證明使用變分刻畫
使用完整奇異值分解,其右奇異基底為 ;當 ,。前 個右奇異向量的生成空間使最小值至少為 。由維數計數,每個 維空間 都與 的生成空間有非零交集;該交集中某個單位向量滿足 。這證明了變分刻畫。對每個單位向量 ,三角不等式給出 。對每個 先取最小值,再對 取最大值,得到 ;交換 即證(1)。
證明透視
維數計數與三角不等式在哪裏起作用
選用極大極小公式,是因為它不借助奇異向量來描述 ,於是 與 可以在同一批子空間 上比較。關鍵一步是 對所有單位向量 一致成立(來自 ),而先取最小值再取最大值會保持這種一致不等式。維數計數只用來證明該公式: 維的 與 生成的 維空間,維數之和為 ,所以必有非零的公共向量。最後交換 與 ,把單邊不等式變成帶絕對值的不等式。這裏只假設兩矩陣大小相同且 ,對秩本身毫無假設;因此每個 至多移動 ,精確秩卻仍可跳變。
推論 6.2.3
(由不確定區間得出的秩界)
設 如穩定性定理所設,並設 為任意容差,則
證明
(在閾值兩側計數指標)
若 ,則由(1) 得 ,所以指標 被 計入;不同指標仍然不同,這給出左邊的不等式。若 ,則 ,所以 被右邊計入,這給出右邊的不等式。
下界數算肯定高於閾值的奇異值;上界包含每個可能高於閾值的奇異值。即使 ,兩界仍然成立。處於不確定區間的值,其分類未必能確定。這裏把 視為精確值;若算法輸出其近似值,使用此推理前還須把有證明的計算誤差納入不確定度。
例題
例題 6.2.4
(精確秩改變,閾值秩卻穩定)
設 、。比較它們的精確秩,並用 及 估計 。
解答。 有兩個正奇異值,秩為二; 有三個,秩為三。差 是 ,譜範數為 。對 ,恰有兩個奇異值大於 ,也恰有兩個大於 。(2) 的上下界都是二,所以 。此例的精確秩不同,閾值結論卻是穩定的。
例題 6.2.5
(不確定區間可能令結論無法確定)
已知矩陣 ;未知真實矩陣滿足 。這對 有甚麼啟示?
解答。 有一個奇異值大於 ,兩個大於 ,故(2) 給出 。兩種情況確實都會出現: 和 與 的距離均為 。按嚴格閾值規則,它們在容差 下的秩分別為一及二。沒有更多資訊便不能消除不確定性;把任一答案報成確定都會超出資料所支持的範圍。
例題 6.2.6
(失去秩的距離與嚴格閾值)
令 ,則 、,精確秩為二。擾動 滿足 ,而 的秩為一:秩可以在距離 處下降。對任何 的 ,不等式(1) 給出 ,所以秩仍為二。在容差 下,奇異值 並不嚴格大於 ,故 ,儘管精確秩是二。這個邊界情形說明,嚴格不等號是必須明確聲明的約定。
反例模式
相近的矩陣未必有相同的精確秩
斷言:若 很小,則 。這是假的。取 、,則 的譜範數為 ,但 、。能保留下來的是(2) 的兩個界:取 、,只有 大於 ,也只有它大於 (因為 ),所以 被確定下來。容差大於不確定度時答案穩定,精確秩則不然。
常見錯誤與細節
常見錯誤
(把量度矩陣的秩當作真實矩陣的秩)
第二個例題中 有 ,但在所述距離內的矩陣 有 。只對量度矩陣使用閾值,便忽略了不確定區間;誠實的答案是(2) 給出的區間。
常見錯誤
(忘記閾值帶有單位)
把資料矩陣乘以 ,所有奇異值都乘以 。取 ,矩陣 的閾值秩為一,而 的閾值秩為二。容差必須按資料的單位和誤差尺度來選取。
習題
快速檢查
(對 ,求精確秩及閾值秩 。)
先數嚴格為正的奇異值,再數大於 的奇異值。
解答 · 答案
奇異值為 ,所以精確秩為二。只有 大於 ,故 。
快速檢查
(設 、、。當 時,(2) 對 說了甚麼?)
把 的奇異值與 比較。
解答 · 答案
只有 大於 ,而 和 都大於 。因此 。兩個值都會出現: 給出一,與 距離為 的 給出二。
快速檢查
(若 且 ,穩定性不等式對 給出怎樣的範圍?)
取 應用(1)。
解答 · 答案
,所以 。特別地 , 至少有三個正奇異值。