奇異值分解

當特徵值不夠用時

到現在你已經能用冪法追特徵值，用反迭代把它磨利，再用QR 演算法把整個譜輾出來。但特徵值有兩個頑固的限制。第一，它們只對方陣存在——對一個 1000×3 的資料矩陣問特徵值是沒有意義的。第二，就算是方陣，特徵向量也不一定正交，而虧損矩陣甚至可能根本湊不齊一整組。幾何可能歪斜糾結，正是會摧毀數值信心的那種情況。

奇異值分解（SVD）繞過了這一切。它說：任何形狀為 m×n 的矩陣 A 都能分解成 A = U S V^T，其中 U 與 V 是正交的（它們的行向量是互相垂直的單位向量），而 S 是長方對角矩陣，對角線上的元素都非負。沒有虧損、沒有複數、沒有歪斜的軸——只有兩個誠實的旋轉，中間夾著一個純粹的伸縮。

奇異值從哪裡來

這裡有一座回到特徵值的橋。組出方陣 A^T A。它是對稱且半正定的，所以它有實的、非負的特徵值，以及一整組正交的特徵向量——這正是乖巧的對稱特徵問題。它的特徵向量就是 V 的行向量，而它的特徵值就是奇異值的平方：若 A^T A v = lambda v，則 sigma = sqrt(lambda)。奇異值永遠不會是負的，因為它們是非負數的平方根。

A v_i = sigma_i u_i        (input axis -> stretched output axis)
sigma_1 >= sigma_2 >= ... >= sigma_r > 0 = sigma_{r+1} = ...
rank(A) = r = number of nonzero singular values
A = U S V^T = sum_i sigma_i (u_i v_i^T)

四行寫完 SVD：成對的軸、由大到小排好的伸縮倍率、把秩看成非零奇異值的個數，以及把 A 重建成一堆秩 1 片段的和。

注意最後一行：A 是一堆秩 1 層 sigma_i 乘以 (u_i v_i^T) 的和，由最強的伸縮排到最弱。這個排序正是 SVD 在實務上如此好用的全部原因——它把 A 的方向依重要性排名，而這正是下一篇談低秩近似時要利用的東西。最大的 sigma 就是矩陣的 2-範數；比值 sigma_1 / sigma_n 就是它求逆的條件數。SVD 直接把問題的條件狀況交到你手上。

它實際上怎麼算出來

標準演算法是個巧妙的兩階段做法，呼應了 QR 演算法馴服一般矩陣的方式。第一階段用固定次數的正交運算把 A 精確地擠成一個更簡單的形狀；第二階段在那個簡單形狀上迭代，直到奇異值掉出來。因為每一步都是正交變換，長度與角度都被保留，這正是 SVD 著名的數值可靠性的秘密。

雙對角化。 用左右兩側的 Householder 反射，把 A 化簡成上雙對角矩陣 B（只有對角線與其上方一條對角線非零）。這就是 Golub-Kahan 雙對角化，以固定的 O(m n^2) 浮點運算完成——不需迭代，只是乾淨的正交掃描，而且不改變奇異值。
迭代到對角。 在雙對角矩陣 B 上跑一個隱式、帶位移的 QR 式掃描，以隱式方式處理 B，使 A^T A 永遠不被組出。每次掃描都把上對角線往零削；配上好的位移它三次方收斂，所以每個奇異值通常只需少數幾次掃描。
讀出並收尾。 收斂後的對角元素就是奇異值；取絕對值並由大到小排序。把 Householder 與旋轉運算累積進 U 與 V，就還原出完整的 A = U S V^T，接著把小於捨入下限的最小奇異值誠實地當成數值上的零。

這就是一行 `svd(A)` 背後的常式真正做的事，而且它是後向穩定的：算出的因子正好是某個非常接近 A 的矩陣的精確 SVD，差距約為機器 epsilon 乘以 A 的範數。這就是現實中的黃金標準——記得條件數那一階說過，精度 = 條件數乘以穩定性，所以就連這個漂亮又穩定的演算法，也救不回一個病態 A 早已埋進雜訊底下的奇異值。

為什麼大家都伸手拿它

SVD 是數值線性代數的瑞士刀，因為排好序的奇異值一次回答了好多問題。數值秩就是高於某個合理門檻的奇異值個數——遠比去追精確的零可靠，因為在電腦上沒有東西會剛好是零。條件數就是 sigma_1 / sigma_r，誠實地算出來，不必對任何東西求逆。而當最小平方問題秩虧損時，SVD 只要把非零的奇異值取倒數、把那些微小而不可信的留著不動，就能造出偽逆。

一個小小的具象例子：取一個 2×2 矩陣，把 x 軸拉長 3 倍、y 軸拉長 1 倍，再把結果旋轉 45 度。它的特徵值看起來很複雜，但它的奇異值恰好是 3 與 1——SVD 看穿了旋轉，直達真正的伸縮倍率。這就是它每天上演的奇蹟：SVD 報告一個映射真正的幾何，不被外面包著的任何旋轉所扭曲。

有個成本要誠實面對。完整的 SVD 要 O(m n^2) 浮點運算，還要存稠密的 U 與 V，對 1000×50 的矩陣沒問題，但對有上百萬列的稀疏矩陣就毫無希望。對那種情況，你不會想要全部奇異值，只想要最大的幾個——而這是上一階 Krylov 特徵解法器的工作，在 A^T A 或它的雙對角親戚上運行，根本不去組出那個巨大的矩陣。稠密 SVD 與稀疏迭代 SVD 是給不同規模用的不同工具；拿錯是最常見的 SVD 錯誤。

帶著走的東西

記住一個畫面和一個警告。畫面：任何矩陣都是旋轉—伸縮—旋轉，而奇異值就是伸縮倍率，由最重要排到最不重要。警告：透過雙對角化加隱式迭代來計算 SVD，絕不要去組 A^T A，因為平方會丟掉你一半的位數。手裡握著那串排好序的伸縮倍率，你就完全準備好迎接壓軸——只留下其中前面幾個，就能得到可能最好的低秩近似，這正是 PCA、影像壓縮與推薦系統背後的數學。

最後一個誠實檢查，和整條學習階梯上每一篇如影隨形的那個：SVD 是在浮點數中算出來的，所以它的奇異值與奇異向量都是近似的，精度大約是機器 epsilon 乘以 sigma_1。後向穩定的常式保證給你某個鄰近矩陣的精確 SVD，但它無法分辨兩個彼此靠得比捨入下限還近的奇異值，也救不回病態 A 早已淹沒的方向。SVD 是工具箱裡最可信的工具——它只是不是魔法，而清楚知道它的誠實在哪裡結束，正是「會用它」與「懂它」之間的差別。