Matrix Decompositions（矩阵分解）¶
Matrix 分解将复杂 matrix 分解为更简单的因子，用于求解方程组、计算逆以及压缩数据。本节涵盖 Gaussian 消元、LU、QR、Cholesky、特征分解和 SVD——这些是 PCA、推荐系统和 ML 数值稳定性背后的算法。
-
Matrix 分解（或因式分解）将一个 matrix 拆解为更易处理的简单部分。可以类比整数分解：\(12 = 3 \times 4\) 比直接处理 12 更容易推理。
-
我们分解 matrix 的目的是：更快地求解方程组、稳定地计算逆、求 eigenvalue、压缩数据，以及理解变换的几何含义。
-
最基本的技术是 Gaussian 消元法（行化简）。思路很简单：给定方程组 \(A\mathbf{x} = \mathbf{b}\)，用三种允许的操作化简 \(A\)，直到答案显而易见。
-
这三种操作是：交换两行、将某行乘以非零 scalar、将某行的倍数加到另一行。
-
例如，为了消去第一列主元以下的元素，从下面各行中减去第 1 行的倍数：
- 目标是行阶梯形式（REF）：每个主元（每行的第一个非零元素）下方为零，且每个主元位于上方主元的右边，形成阶梯状。
-
进一步化简为简化行阶梯形式（RREF）：使每个主元等于 1，且是其列中唯一的非零元素。每个 matrix 都有唯一的 RREF。
-
化为三角形式后，通过回代求解：最后一行直接给出最后一个变量，然后向上逐行求解。
-
这是所有其他分解的基础——分解的目标正是将 matrix 化简为三角形式，这样就可以回代并求解变量。
-
LU 分解将 Gaussian 消元法形式化，将方阵分解为 \(A = LU\)（或带行交换时 \(A = PLU\)），其中 \(L\) 是下三角 matrix，\(U\) 是上三角 matrix。
-
求解 \(A\mathbf{x} = \mathbf{b}\)：首先通过前代（从上往下）求解 \(L\mathbf{y} = \mathbf{b}\)，然后通过回代（从下往上）求解 \(U\mathbf{x} = \mathbf{y}\)。两次简单的三角求解，而不是一次困难的一般求解。
-
与朴素 Gaussian 消元法相比，LU 分解的优势在于复用。一旦有了 \(L\) 和 \(U\)，就可以针对许多不同的 \(\mathbf{b}\) 向量求解，而无需重做分解。
-
如果需要对同一方程组求解 1000 个不同的右端向量（在仿真中很常见），只需分解一次并重复使用。
-
当 matrix 是对称正定的（如协方差 matrix）时，我们可以做得更好。
-
Cholesky 分解将其分解为 \(A = LL^T\)，其中 \(L\) 是下三角 matrix。例如：
-
这大约比 LU 快两倍，且保证数值稳定。可以把它看作 matrix 的"平方根"。
-
若分解失败（某个平方根下出现负数），则 matrix 不是正定的。因此，Cholesky 也可作为正定性的验证方法。
-
方阵 \(A\) 的 eigenvector 是变换时只会被拉伸或压缩而不旋转的特殊方向。Eigenvalue 是对应的缩放因子：
-
大多数 vector 在乘以 matrix 后会改变方向。但 eigenvector 是特殊的：输出与输入方向相同，只是被 \(\lambda\) 缩放。若 \(\lambda = 2\)，eigenvector 长度加倍；若 \(\lambda = -1\)，方向翻转；若 \(\lambda = 0\)，被压缩为零。
-
例如，对于：
vector \([1, 0]^T\) 是 eigenvalue 为 \(\lambda = 3\) 的 eigenvector，因为 \(A[1, 0]^T = [3, 0]^T = 3[1, 0]^T\)。
-
为了求 eigenvalue，求解特征多项式 \(\det(A - \lambda I) = 0\)。其根就是 eigenvalue。然后将每个 \(\lambda\) 代回 \((A - \lambda I)\mathbf{x} = \mathbf{0}\) 以求对应的 eigenvector。
-
关键性质：
- \(A\) 的迹等于其 eigenvalue 之和。
- \(A\) 的行列式等于其 eigenvalue 之积。
- 对称 matrix 有相互垂直的 eigenvector 和实数 eigenvalue。
- 正定 matrix 的 eigenvalue 全为正。
- 协方差 matrix（我们在统计学中会遇到）始终是半正定的。
-
对大 matrix 通过特征多项式计算 eigenvalue 是不切实际的。实际中使用迭代方法：
-
幂迭代：反复将 matrix 与某 vector 相乘并归一化。收敛到主 eigenvector（最大 eigenvalue）。简单，但只能找到一对特征对。
-
QR 算法：主力方法。反复用 QR 分解进行分解和重组，直到 matrix 收敛到三角形式，从而在对角线上揭示所有 eigenvalue。
-
逆迭代：找到最接近给定目标值的 eigenvector。在大致知道想要哪个 eigenvalue 时很有用。
-
对于大型稀疏 matrix，Arnoldi 和 Lanczos 迭代利用稀疏性提高效率。
-
-
若方阵有一组完整的线性无关 eigenvector，它就可以被对角化：\(A = PDP^{-1}\)，其中 \(D\) 是 eigenvalue 构成的对角 matrix，\(P\) 的各列是 eigenvector。
-
为什么有用？对角 matrix 极易处理。需要计算 \(A^{100}\)？与其将 \(A\) 与自身相乘 100 次，不如计算 \(PD^{100}P^{-1}\)——对角 matrix 的幂次只需对每个元素独立求幂。这将昂贵的运算变为廉价的运算。
-
特征基（eigenbasis）是完全由 eigenvector 构成的 basis。在这个 basis 中，matrix 变为对角形式，变换只是沿各 eigenvector 方向的独立缩放。这就像找到了变换的天然坐标系。
-
QR 分解将任意 matrix \(A\) 分解为 \(A = QR\)，其中 \(Q\) 是正交 matrix（各列正交归一），\(R\) 是上三角 matrix。可以把它理解为将"方向"信息（\(Q\)）与"缩放和混合"信息（\(R\)）分离。
-
Gram-Schmidt 过程逐列构建 \(Q\)。取 \(A\) 的第一列并归一化；取第二列，减去其在第一列上的投影（使其垂直），再归一化；对每一列重复这一过程。结果是一组正交归一的 vector。
-
QR 分解是求 eigenvalue 的 QR 算法的引擎。它也直接用于求解最小二乘问题：当 \(A\mathbf{x} = \mathbf{b}\) 没有精确解（方程多于未知量）时，QR 找到最佳近似解。
-
SVD（奇异值分解）是最一般、可以说也是最重要的分解。每个 matrix（任意形状、任意 rank）都有 SVD：\(A = U\Sigma V^T\)
- \(V^T\)（\(n \times n\)，正交）：旋转输入
- \(\Sigma\)（\(m \times n\)，对角）：沿正交轴缩放（singular value，非负，降序排列）
- \(U\)（\(m \times m\)，正交）：旋转输出
-
从几何上看，SVD 表明每个线性变换，无论多复杂，都不过是一次旋转，接着沿各轴的拉伸，再接着另一次旋转。圆变成了椭圆。
-
Singular value（\(\sigma_1 \geq \sigma_2 \geq \ldots\)）揭示了每个方向的"重要性"。Singular value 大的方向最为重要。\(A\) 的 rank 等于非零 singular value 的数量。
-
低 rank 近似：通过只保留 \(k\) 个最大的 singular value 并将其余置零，可以得到 \(A\) 的最佳 rank-\(k\) 近似。图像压缩就是这样工作的：一幅 \(1000 \times 1000\) 的图像可能只需 \(k = 50\) 个 singular value 就能几乎完全保真，压缩比达 20 倍。
-
SVD 也提供伪逆：\(A^+ = V\Sigma^+U^T\)，其中 \(\Sigma^+\) 对非零 singular value 取倒数。
-
特征分解只适用于方阵，而 SVD 适用于任意 matrix——这是它的核心优势。
-
PCA（主成分分析）利用特征分解（或 SVD）进行降维。
-
想象每个样本有 100 个 feature 的数据集（100 维 vector 堆叠成 matrix）。这些 feature 中许多是相关且冗余的。
-
PCA 找到数据实际变化的方向，让你只保留重要的部分。
-
第一主成分（PC1）是方差最大的方向。
-
第二主成分（PC2）捕捉剩余方差最多的部分，且与第一个主成分垂直。
-
如果大部分方差集中在少数几个方向上，就可以将数据投影到这些维度，丢弃其余部分，同时保持最小的信息损失。
-
步骤：
- 对数据进行标准化（减去均值，除以标准差），使所有 feature 平等地贡献
- 计算协方差 matrix
- 求其 eigenvalue 和 eigenvector
- 选取 eigenvalue 最大的 \(k\) 个 eigenvector（即主成分）
- 将数据投影到这些主成分上
-
标准化至关重要：若不进行标准化，以千米为单位的 feature 会主导以厘米为单位的 feature，无论其实际重要性如何。
-
在实际中，PCA 用于可视化（将高维数据投影到二维或三维）、降噪（丢弃主要是噪声的低方差方向），以及通过减少输入 feature 数量来加速 ML 模型。
-
Kernel PCA 将 PCA 扩展到非线性关系。它通过 kernel 函数将数据映射到高维空间，使结构变为线性，然后应用标准 PCA 并映射回来。
-
Schur 分解将方阵分解为 \(A = QTQ^\ast\)，其中 \(Q\) 是酉 matrix，\(T\) 是上三角 matrix。每个方阵都有 Schur 分解，即使它不能被对角化。
-
非负 Matrix 分解（NMF）将 matrix 分解为两个非负 matrix：\(A \approx WH\)，其中 \(W\) 和 \(H\) 的所有元素均 \(\geq 0\)。与 SVD 不同，NMF 只做加法，不做减法。这使得各部分具有可解释性：在主题建模中，\(W\) 给出每篇文档的主题权重，\(H\) 给出每个主题的词权重——全部非负，与我们对文档"含有多少各主题"的直觉一致。
-
谱定理指出，对称（或 Hermitian）matrix 总可以用正交（或酉）matrix 对角化。它们的 eigenvalue 总是实数，eigenvector 总是正交的。这是 PCA 的理论基础。
编程练习（使用 CoLab 或 notebook）¶
-
计算对称 matrix 的 eigenvalue 和 eigenvector。验证 eigenvector 垂直，并从特征分解重建 matrix。
import jax.numpy as jnp A = jnp.array([[4.0, 2.0], [2.0, 3.0]]) eigenvalues, eigenvectors = jnp.linalg.eigh(A) print(f"Eigenvalue: {eigenvalues}") print(f"Eigenvector 正交性: {jnp.dot(eigenvectors[:,0], eigenvectors[:,1]):.6f}") # 重建：A = P D P^T D = jnp.diag(eigenvalues) A_reconstructed = eigenvectors @ D @ eigenvectors.T print(f"重建结果匹配: {jnp.allclose(A, A_reconstructed)}") -
实现幂迭代求最大 eigenvalue，实现逆迭代求最小 eigenvalue。与
jnp.linalg.eigh比较。然后尝试自己实现 QR 算法。import jax.numpy as jnp A = jnp.array([[4.0, 2.0], [2.0, 3.0]]) # 幂迭代：求最大 eigenvalue v = jnp.array([1.0, 0.0]) for _ in range(20): v = A @ v v = v / jnp.linalg.norm(v) print(f"最大 eigenvalue: {v @ A @ v:.4f}") # 逆迭代：乘以 A^{-1} 而非 A，求最小 eigenvalue v = jnp.array([1.0, 0.0]) for _ in range(20): v = jnp.linalg.solve(A, v) v = v / jnp.linalg.norm(v) print(f"最小 eigenvalue: {1.0 / (v @ jnp.linalg.solve(A, v)):.4f}") print(f"jnp.linalg.eigh 结果: {jnp.linalg.eigh(A)[0]}") -
计算 matrix 的 SVD，然后仅使用前 k 个 singular value 重建，观察随 k 变化的近似质量。