从 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 是那把万能钥匙。