以下矩陣皆為實的有限維矩陣。證明使用本課程較早建立的奇異值分解與正交性結果。
兩種衡量近似的方法
假設以秩至多為 的較簡單矩陣 取代 。下面兩種範數回答不同的問題,雖然同一個截斷奇異值分解會同時令它們最小。
定義 4.4.1
(譜範數、弗羅貝尼烏斯(Frobenius)範數與截斷奇異值分解)
對 ,譜範數是 ,即所有單位輸入中的最大伸長量;弗羅貝尼烏斯(Frobenius)範數是 ,即各矩陣項平方和的平方根。
取完整奇異值分解 ,奇異值依次為 ,其中 , 為相應的標準正交奇異向量。秩 的截斷為
空和 是零矩陣。每個加項的秩至多為一,所以 。譜範數只由一個方向控制,弗羅貝尼烏斯範數則把所有被捨棄的方向加起來,所以下面陳述中兩個最小誤差的形式不同。
定理 4.4.2
(Eckart–Young 最佳低秩近似)
設 與 如上。對每個秩至多為 的 ,
當 ,,兩個最小誤差均為零。
證明分三部分:計算候選矩陣 的誤差,證明譜範數的下界,再證明弗羅貝尼烏斯範數的下界。這些是近似定理;捨棄小奇異值會改變矩陣,也可能改變逆問題。
先計算候選矩陣的誤差
引理 4.4.3
(截斷矩陣的誤差)
對 ,;當 ,。
證明
(奇異向量座標下候選矩陣的誤差)
正交座標變換保留歐氏長度及弗羅貝尼烏斯範數。對後者,一個直接證明是 ,且對正交 有 ;左乘正交矩陣的證明類似。在奇異向量座標下, 是矩形對角矩陣,其剩餘對角項為 。它的弗羅貝尼烏斯範數平方就是這些數的平方和。對矩形對角矩陣,單位向量的最大伸長量是最大對角項的絕對值:平方相加給出上界,選取對應的座標向量便取到上界。因此當 ,其譜範數是 。
為甚麼其他秩至多為 的矩陣不能改善最壞情況
證明
(譜範數下界:用被 消去的向量)
假設 。令 ,其維數為 。 限制在 上的像維數至多為 。秩–零度定理給出非零 滿足 ;將它標準化至 。寫 ,由標準正交性得 及
譜範數是所有單位輸入的最大值,所以至少為 ;候選矩陣恰好達到下界。即使有零奇異值或重複奇異值,此維數論證仍然有效;我們沒有假設 可逆。
證明透視
譜範數下界從何而來
論證靠兩個事實。第一, 的維數是 ,而 的秩至多為 ,所以 限制在 上不可能是單射;秩條件只在這裏用到。第二,在 上 都不小於 ,因為奇異值已按次序排列;次序只在這裏用到。不顯而易見的一步,是把測試向量取在 內,而不是直接比較 與 :這樣未知矩陣 就從 中消失。論證能夠收尾,是因為下界 恰好等於 的誤差,而 的核含有 。若 只有 維, 在其上可以是單射,就不能保證存在滿足 的非零 。
為甚麼誤差平方和也最小
證明
(弗羅貝尼烏斯下界:投影到行空間)
令 為 的行空間, 為到 的正交投影。則 且 。矩陣 與 在弗羅貝尼烏斯內積下正交:其跡乘積含有 。因此
把 延伸為 的標準正交基底 ,並對 設 。令 。正交投影給出 ,而 。在 基底下,
第二個等式成立,因為 時 ,其餘 都在零空間;也可以在奇異值分解的基底中取跡。
當 ,利用奇異值的次序,
中間的不等式使用 。整理(3)得 。當 ,,同一個下界立即成立。結合(2)即證得(1)的弗羅貝尼烏斯不等式。證明沒有假設最佳矩陣與 具有相同的奇異向量;它適用於每個符合秩條件的 。
反例模式
保留範數最大的列不是最佳秩一近似
有人以為秩一近似只需保留範數最大的列、把其餘列換成零。取 。則 的特徵多項式為 ,所以 ,。由(1),每個秩一的 都滿足 及 。第二列 的範數較大;保留它得 ,秩為一,而 ,兩種誤差都等於 。這個捷徑並不最佳;截斷奇異值分解用的是奇異方向 ,不是 的座標列。
例題
例題 4.4.4
(分清兩種誤差)
設 。求一個最佳秩一近似及其兩種範數誤差;再對秩至多為二的情況重做。
所列對角項就是按遞減次序排列的奇異值。最佳秩一近似之一為 。誤差是 ,所以 ,而 。對秩至多為二,,兩種誤差均為 。定理證明這些值在所有指定秩的矩陣中最小,而不只是對角候選矩陣中最小。
例題 4.4.5
(重複奇異值與不唯一性)
對 ,給出兩個不同的最佳秩一近似並計算誤差。
取 及 ,兩者秩均為一。其誤差的對角項分別是 及 ;兩者的譜範數均為 ,弗羅貝尼烏斯範數均為 。公式(1)證明兩者在兩種範數下都是最佳近似。首兩個奇異值相同,容許保留不同的奇異方向;不能由「截斷奇異值分解」這個名稱推斷唯一性。
例題 4.4.6
(秩為零與滿秩的極端情況)
對 ,取 及 。
當 ,唯一的近似矩陣是 ,誤差就是 本身:,,與(1)在 時一致。當 ,截斷矩陣 ,兩種誤差均為零;此時不使用譜範數公式 ,因為沒有 。
常見錯誤
常見錯誤
(以為兩種範數的誤差相同)
對 及 ,譜範數誤差是 ,弗羅貝尼烏斯範數誤差卻是 。截斷在兩種範數下都是最佳,但最佳值是不同的數:譜範數誤差只反映被捨棄的最大奇異值,弗羅貝尼烏斯範數誤差則反映全部。
即時檢查
快速檢查
(某矩陣的奇異值為 。它的最佳秩一近似的譜範數誤差與弗羅貝尼烏斯範數誤差各是多少?)
捨棄 。
解答 · 答案
由(1)取 ,譜範數誤差為 ,弗羅貝尼烏斯範數誤差為 。
快速檢查
(一個 矩陣的秩為 。在 中,哪些 使 的譜範數誤差為零?)
哪些奇異值為零?
解答 · 答案
此處 ,,而 。 時譜範數誤差為 , 時 。 時誤差為 。所以 或 。
快速檢查
(對 ,秩為一的矩陣 能否滿足 ?)
與 比較。
解答 · 答案
不能。由(1)取 ,每個秩至多為一的 都有 。 與 都達到這個下界。