從 A^T A 構建 SVD

為何 A^T A 是合適的對象

無論 A 是什麼，矩陣 A^T A 都是 n×n 方陣、對稱且半正定：x^T (A^T A) x = ||A x||^2 >= 0。由譜定理，它有一組標準正交特徵基，且特徵值非負。這就是一切的種子。

把這些特徵對寫成 A^T A v_i = lambda_i v_i，其中 lambda_1 >= lambda_2 >= ... >= 0。定義奇異值為 sigma_i = sqrt(lambda_i)。由於 lambda_i 非負，平方根是實的——這正是為什麼即便 A 擁有複的或負的特徵值，奇異值仍永遠是實的且非負。見奇異值與特徵值的對比。

製造左奇異向量

v_i 已到手。對每個 sigma_i > 0 的 i，定義 u_i = (A v_i) / sigma_i。兩個簡短的計算表明它們正是左奇異向量：它們是單位向量，並且彼此正交。

Unit length:
   ||u_i||^2 = (A v_i)^T (A v_i) / sigma_i^2
             = v_i^T (A^T A) v_i / sigma_i^2
             = v_i^T (lambda_i v_i) / sigma_i^2
             = lambda_i / sigma_i^2  =  1     (since sigma_i^2 = lambda_i)

Orthogonality (i != j):
   <u_i, u_j> = (A v_i)^T (A v_j) / (sigma_i sigma_j)
              = v_i^T (A^T A) v_j / (sigma_i sigma_j)
              = v_i^T (lambda_j v_j) / (sigma_i sigma_j)
              = (lambda_j / (sigma_i sigma_j)) <v_i, v_j>
              = 0                              (the v's are orthonormal)

=>  the u_i form an orthonormal set, and  A v_i = sigma_i u_i.

u_i = A v_i / sigma_i 自動是標準正交的——這就是全部訣竅。

拼裝出存在性證明

構造 A^T A；由譜定理得到標準正交特徵向量 v_1, ..., v_n，對應特徵值 lambda_1 >= ... >= lambda_n >= 0。
令 sigma_i = sqrt(lambda_i)；設 r 為嚴格為正的 sigma_i 的個數（此 r 即 A 的秩）。
對 i <= r 令 u_i = A v_i / sigma_i；把 u_1, ..., u_r 擴成 R^m 的完整標準正交基。
於是 A = U Sigma V^T 恰好成立。由於此構造從不要求 A 是方陣或可逆，故 SVD 對每個矩陣都存在。

實踐中無人在數值上構造 A^T A——對矩陣取平方會把其條件數也平方，損失精度。這個證明告訴你 SVD *存在*；真正的演算法以遠為穩定的方式來計算它。但要理解，A^T A 是那把萬能鑰匙。