矩阵分解 -3- 方法综述

矩阵分解是把一个矩阵拆成若干结构清晰、计算可控的因子之积，是数值线性代数与数据科学的基础工具。本分类下已有《矩阵分解 -1- 概述》的方法清单与《矩阵分解 -2- 特征值分解》的单篇展开，本文作为方法综述，按几何与代数本质把常见分解归为四类——谱类、正交类、直接求解类、应用驱动类——对每类给出定义、因子的含义、适用条件与典型应用，并梳理方法之间的联系、复杂度与数值稳定性，最后给出选型决策。

本文注重「是什么、为什么、什么时候用」，公式以可读为先；特征分解的细节请参考专篇，这里只在谱类的框架下做必要复述。

一、矩阵分解的动机

一个矩阵本身往往是一团无结构的数。分解的目的是把它拆成因子的乘积，让隐藏的结构暴露出来，从而把原本困难或昂贵的计算变得可控。常见任务与分解的作用对应如下：

任务	分解的作用
解线性方程组 $Ax=b$	拆成三角形 $A=LU$，一次分解、多次回代
降维 / 压缩	用低秩近似 $A≈A_k$ 保留主信息、丢弃次要部分
降噪	信号集中在大奇异值方向，小奇异值对应噪声
特征提取	暴露主方向（特征向量、奇异向量）、潜在因子
求特征值	QR 算法把矩阵收敛到上三角，对角元即特征值
最小二乘	用正交（QR/SVD）或正定（Cholesky）结构稳定求解超定系统

不同分解对应不同目的。本文按几何与代数本质把它们归入四类，便于建立整体认知。

二、四类谱系总览

               矩阵分解
  ┌──────────────┬──────────────┬──────────────┬──────────────┐
谱类(特征结构)  正交类(任意矩阵) 直接求解类(三角) 应用驱动类(加约束)
  │              │              │              │
特征分解 QΛQ⁻¹   SVD  UΣVᵀ      LU   PA=LU     PCA(=中心化SVD)
Schur  A=UTU*    QR   A=QR      Cholesky LLᵀ   NMF(非负)
Jordan P⁻¹AP=J   极分解 A=UP                     ICA(独立)
                                                推荐MF(稀疏/潜在因子)
                                                张量分解 CP/Tucker
                                                矩阵补全(低秩)

刻画不变量与谱   适用于任意 m×n   三角结构，支撑   保留数学骨架同时
要求方阵；对      矩阵；后向稳定   Ax=b 的高效求解  引入领域假设
矩阵类型与稳定   (Householder/   LU: 2/3 n³      (非负/独立/稀疏/低秩)
性有要求          Givens/Cholesky) Chol: 1/3 n³
Jordan 病态，避用

一句话纲领：谱类刻画特征结构但对矩阵类型与稳定性要求严格；正交类适用于任意矩阵且后向稳定，是工程计算的主力；直接求解类以三角形结构支撑线性方程组的高效求解；应用驱动类在保留数学骨架的同时引入领域假设。其中 SVD 适用面最广，它修正了特征分解的主要局限，并以「旋转-拉伸-旋转」的几何结构自然桥接了 PCA 与低秩近似。

三、谱类分解——刻画特征结构

3.1 特征分解

对 $n$ 阶方阵 $A$，若存在可逆矩阵 $X$ 与对角矩阵 $Λ$ 使

{%raw%} $$ A = X\Lambda X^{-1} $$ {%endraw%}

则称 $A$ 可对角化。$X$ 的列是特征向量 $x_i$，对角元 $λ_i$ 是特征值，满足 $Ax_i = λ_i x_i$。对对称矩阵（更一般地，正规矩阵 $AA^*=A*A$），特征向量可取为两两正交，分解退化为 $A = QΛQ^\mathsf{T}$，这是最理想的形式。特征分解的细节（特征多项式、几何与代数重数、可对角化判据）见《矩阵分解 -2- 特征值分解》。

因子的含义：特征向量是矩阵作用下方向不变的方向，特征值是该方向上的拉伸因子（$|λ|>1$ 放大、$|λ|<1$ 压缩、$λ<0$ 反向）。整体上，$A$ 的作用可读作「换到特征向量坐标系 → 沿各轴独立拉伸 → 换回原坐标系」。

三大局限，正是引入 SVD 的动机：

1. 特征向量通常不正交，只有正规矩阵才有正交特征向量；
2. 未必有足够数量的特征向量——亏损矩阵不可对角化，例如剪切矩阵 $[[1,1],[0,1]]$ 只有一个独立特征向量；
3. 要求 $A$ 为方阵，长方阵（如数据矩阵）无法做特征分解。

适用条件：方阵且有 $n$ 个线性无关特征向量；对称矩阵总能正交对角化，最稳定常用。应用：振动模态分析、PCA 的理论基础、谱聚类、马氏距离、控制系统的稳定性判定（状态矩阵特征值实部全负则稳定）。

3.2 Schur 分解

任意方阵 $A$（复数域）都可分解为

{%raw%} $$ A = UTU^{*} $$ {%endraw%}

其中 $U$ 是酉矩阵（$U^*U=I$），$T$ 是上三角。关键性质：$T$ 的对角元就是 $A$ 的特征值。

因子的含义：$U$ 把 $A$ 相似变换到一个上三角坐标系，各列是一组正交归一的基（Schur 向量）；$T$ 的对角部分给出特征值，严格上三角部分表示各 Schur 向量方向之间的单向耦合。

适用条件与计算：任意方阵都有 Schur 分解，这是它优于特征分解之处（不要求可对角化）。它是 QR 算法的数学产物，也是数值计算特征值的标准方法。QR 算法迭代地做 $A_k = R_k Q_k = Q_k^* A_{k-1} Q_k$（一系列酉相似），最终收敛到 Schur 形，总体复杂度 $O(n^3)$。一个关键的工程优化是：直接对满矩阵做一步 QR 迭代代价约 $O(n^3)$，而先把矩阵归约为上 Hessenberg 形，则每步只需 $O(n^2)$，单步成本降低一个 $n$ 因子。

应用：LAPACK 求特征值的底层（$geev$ 等）即 QR 算法；控制论中用 Schur 形分析矩阵函数、求解 Lyapunov / Sylvester 方程。

3.3 Jordan 标准形

若方阵 $A$ 的特征多项式可分裂（任意复矩阵都满足），存在可逆 $P$ 使 $P^{-1}AP = J$，$J$ 由若干 Jordan 块拼成。每个块形如主对角线为特征值、紧邻上方为 1、其余为 0 的矩阵。

可对角化判据：$A$ 可对角化当且仅当每个特征值的几何重数等于代数重数（等价地，所有 Jordan 块都是 $1×1$）。否则 $A$ 亏损，大于 $1×1$ 的块用「广义特征向量链」补足缺失的特征向量结构。

数值病态，实际避免使用：在多重特征值附近，$O(ε)$ 量级的扰动就能定性改变 Jordan 结构——一个 $n×n$ 块在 $O(ε)$ 扰动下特征值会分裂为半径约 $ε^{1/n}$ 的环（Ma & Edelman, 1998）。因此 Jordan 形是优美的理论工具，但不是计算工具；数值分析中用稳定的 Schur 分解或伪谱替代。

应用：纯理论——证明矩阵函数 $e^{At}$、$Ak$ 的公式（指数项 $e^{λt}$ 加多项式项 $t^k e^{λt}$ 即来自 Jordan 块）、微分方程解的结构、最小多项式。

四、正交类分解——任意矩阵的通用利器

这一类的共同点是正交（酉）矩阵扮演主角。正交矩阵 $Q^\mathsf{T}Q=I$ 不改变长度、不放大误差，因此基于正交变换的算法天然后向稳定；而且它们对任意 $m×n$ 矩阵都成立。

4.1 奇异值分解 SVD

任意 $m×n$ 矩阵 $A$ 都可分解为

{%raw%} $$ A = U\Sigma V^{\mathsf{T}} $$ {%endraw%}

其中 $U$（$m×m$）、$V$（$n×n$）是正交矩阵，列向量分别称左、右奇异向量；$Σ$（$m×n$）是对角矩阵，对角元 $σ_1 ≥ σ_2 ≥ … ≥ σ_r > 0$ 称奇异值（非负、降序），非零奇异值个数 $r = \mathrm{rank}(A)$。

因子的含义（几何）：SVD 把任意线性变换拆成三步——旋转 $V^\mathsf{T}$ → 沿坐标轴拉伸 $Σ$ → 旋转 $U$。

• $σ_i$ 是变换沿第 $i$ 个正交方向的增益，$σ_1$ 最大、$σ_r$ 是最小非零增益；
• $v_i$ 是输入空间中被放大 $σ_i$ 倍后变成 $u_i$ 的方向，即 $Av_i = σ_i u_i$；
• $σ_\max / σ_\min$ 即条件数，衡量矩阵接近奇异的程度。

与特征分解的关系：右奇异向量恰是 $A^\mathsf{T}A$ 的正交特征向量，左奇异向量恰是 $AA^\mathsf{T}$ 的正交特征向量，且

{%raw%} $$ \sigma_i^{2} = \lambda_i(A^{\mathsf{T}}A) = \lambda_i(AA^{\mathsf{T}}) $$ {%endraw%}

数学上 SVD 可由 $A^\mathsf{T}A$ 的特征分解导出，但现代数值实现刻意避免显式形成 $A^\mathsf{T}A$——相乘会把条件数平方，小奇异值丢失精度；实际算法用 Golub-Kahan 双对角化加 QR 迭代，直接在 $A$ 上操作。

秩一展开与低秩近似：SVD 可写成有序秩一矩阵之和

A = σ₁u₁v₁ᵀ + σ₂u₂v₂ᵀ + … + σᵣuᵣvᵣᵀ

奇异值降序排列，故 $σ_1u_1v_1^\mathsf{T}$ 是最重要的分量。Eckart-Young 定理：截断 SVD 的前 $k$ 项 $A_k = U_k Σ_k V_k^\mathsf{T}$ 给出 $A$ 的最佳秩-$k$ 近似——在所有秩不超过 $k$ 的矩阵中，$A_k$ 使 $‖A - A_k‖$ 最小（谱范数与 Frobenius 范数皆然）。这是丢掉小奇异值方向等于最优地丢掉最不重要信息的数学保证。

适用条件：任意 $m×n$ 矩阵，永远存在；代价是计算量比 LU/QR 大（约 $O(\min(mn^2, m^2n))$），换来的是对病态与秩亏问题的强稳健性。应用：PCA（见 6.1）、图像与数据压缩、降噪、伪逆 $A^+ = VΣ^+U\mathsf{T}$、潜在语义分析 LSA、推荐系统。

4.2 QR 分解

任意 $m×n$ 矩阵 $A$（列满秩时）可分解为 $A = QR$，$Q$ 为正交矩阵（列正交归一），$R$ 为上三角。

因子的含义：$Q$ 的列是一组正交基，$A$ 的列空间即 $Q$ 前 $r$ 列张成的空间；$R$ 是 $A$ 的列在 $Q$ 这组基下的坐标，对角元 $R_{ii}$ 反映第 $i$ 个方向的长度。几何上就是把 $A$ 的列向量组正交化得到 $Q$，原列在新基下的坐标即 $R$。

算法与稳定性，差别很大：

算法	稳定性	说明
经典 Gram-Schmidt（CGS）	不后向稳定	即使 $R$ 对角元不太小也会累积正交性损失，最坏时算出的 $\hat{Q}$ 近奇异
修正 Gram-Schmidt（MGS）	较好但不完全修复	改善了 CGS，仍未根除
Householder 反射	后向稳定（默认）	每个反射的后向误差界 $O(ε_\mathrm{mach})‖A‖$，$j$ 个变换累乘为 $j·O(ε_\mathrm{mach})‖A‖$
Givens 旋转	后向稳定	同样的误差界，适合稀疏或逐元素引入零

生产环境几乎总用 Householder 或 Givens；NumPy / MATLAB / LAPACK 的 $qr$ 默认即 Householder。

适用条件：任意 $m×n$ 矩阵，约 $2mn^2 - \tfrac{2}{3}n^3$ flops（$m≥n$）。应用：最小二乘（比法方程稳定，不平方条件数）、QR 算法求特征值、正交化；此外 $|\det A| = \prod R_{ii}$，但 QR 只给行列式的绝对值。

4.3 极分解

任意实方阵 $A$ 都可分解为 $A = UP$，$U$ 为正交矩阵，$P$ 为对称半正定矩阵。它与 SVD 的关系直接：若 $A = UΣV^\mathsf{T}$，则

{%raw%} $$ A = (\,UV^{\mathsf{T}}\,)\,\underbrace{(\,V\Sigma V^{\mathsf{T}}\,)}_{P} $$ {%endraw%}

即把 SVD 的两次旋转合成一个 $UV^\mathsf{T}$，保留一个对称拉伸 $P$。

因子的含义：类比复数极坐标 $z = re^{iθ}$（模乘幅角），极分解把任意线性变换拆成纯拉伸 $P$ + 刚体旋转 $U$。$P$ 沿某组正交方向拉伸、不旋转，描述形状如何被扭曲；$U$ 是刚体旋转或反射，不改变形状与体积。

适用条件：任意方阵都有极分解（长方阵有推广形式），$A$ 可逆时分解唯一，可由一次 SVD 直接算出。应用：连续介质力学（变形梯度 $F = RU$，分离刚体旋转与纯应变是其物理原型）、计算机图形学中从含噪运动矩阵提取刚体旋转（正交 Procrustes 问题）、机器人运动学。

五、直接求解类——三角形结构与线性方程组

这一类的目标是把矩阵拆成三角形因子的乘积，把解 $Ax=b$ 变成两次 $O(n^2)$ 的三角回代。

5.1 LU 分解

把方阵 $A$ 分解为下三角 $L$ 与上三角 $U$：$A = LU$。实际几乎总用部分主元版本 $PA = LU$，$P$ 为置换矩阵——等价于对行重排后的矩阵做无主元 LU，每步选当前列绝对值最大的元作主元，避免用小元作除数。

因子的含义：$L$ 记录高斯消元各步的乘数，$U$ 是消元得到的上三角结果，$P$ 记录行交换。

适用条件与稳定性：要求方阵；后向稳定，计算的因子精确分解一个邻近矩阵 $P(A+ΔA) = \tilde{L}\tilde{U}$，误差界 $|ΔB| ≤ γ_n|\tilde{L}||\tilde{U}|$。需要说明的是，稳定性来自主元选择与三角求解的误差界，而不是「行置换不产生误差」——置换本身确实无舍入，但这不是稳定性的来源。复杂度约 $\tfrac{2}{3}n^3$。应用：解 $Ax=b$（分解一次、反复回代）、求行列式 $\det A = \pm\prod U_{ii}$（LU 是少数能直接给行列式符号的分解）、求逆。LU 是高斯消元的矩阵形式。

5.2 Cholesky 分解

对对称正定矩阵 $A$，存在唯一的下三角 $L$（对角元为正）使 $A = LL^\mathsf{T}$。

因子的含义：$L$ 是一个下三角「平方根」——正定二次型 $x^\mathsf{T}Ax = ‖L^{\mathsf{T}x‖}2 ≥ 0$，故 $L^\mathsf{T}$ 把椭圆 $x^\mathsf{T}Ax=1$ 映成单位球。

适用条件：严格要求对称（Hermite）正定，不正定则分解失败（对负数开方）；无需主元（正定性保证稳定），复杂度约 $\tfrac{1}{3}n^3$，只有 LU 的一半。应用：解对称正定方程组（如最小二乘法方程 $A^\mathsf{T}Ax=b$、高斯过程的协方差求解、有限元刚度矩阵）、蒙特卡洛中用 $A=LL^\mathsf{T}$ 把独立高斯变成相关高斯、牛顿法中求解 Hessian 方向、Kalman 滤波的协方差传播。求逆矩阵与广义逆的细节见《逆矩阵》。

六、应用驱动类——引入领域假设

这一类保留「分解为因子相乘」的骨架，但为解决特定问题在分解上施加额外约束（非负、独立、稀疏、低秩），与前面的纯数学分解既有联系又有区别。

6.1 主成分分析 PCA

PCA 寻找数据方差最大的方向。设数据矩阵 $X$（每列一个样本，已中心化），样本协方差为 $Σ = \tfrac{1}{n-1}XX^\mathsf{T}$，PCA 即求 $Σ$ 的特征分解：特征向量是主成分方向，特征值是各方向方差。

与 SVD 的本质联系：对中心化 $X$ 做 SVD 得 $X = UΣV^\mathsf{T}$，则主成分方向就是 $V$ 的列（右奇异向量），协方差特征值等于 $σ_i^2$（差一个 $\tfrac{1}{n}$ 或 $\tfrac{1}{n-1}$ 的尺度因子），主成分得分为 $UΣ$ 的列。因此 PCA 在数值实现上就是对中心化数据做 SVD——库函数（如 scikit-learn 的 $PCA$）底层都走 SVD，以避免显式形成协方差矩阵而平方条件数。

因子的含义：对高斯数据，等概率面是椭球，主成分是椭球主轴方向、各方向方差是半轴长度平方。$λ_1 ≫ λ_2$ 表示数据沿主轴拉得很长、本质低维、可压缩；$λ_1 ≈ λ_2$ 表示椭球接近球，主成分不稳定且不可压缩。

适用条件：数据大致线性相关（PCA 是线性方法，非线性结构应用核 PCA / t-SNE / 自编码器）；需先中心化，建议再标准化。应用：降维、可视化、降噪、特征去相关、工业过程监控、人脸识别（Eigenfaces）。

6.2 非负矩阵分解 NMF

对非负矩阵 $V ≥ 0$，找非负因子 $W, H ≥ 0$ 使 $V ≈ WH$，$W$ 是基矩阵（部件字典），$H$ 是编码系数，通过最小化 $‖V - WH‖^2$ 或 KL 散度求解，常用乘法更新或交替最小二乘。

与 PCA/SVD 的区别：非负约束改变了分解性质——不再是正交分解，而是「部分之和」（parts-based）的加性表示，每个因子是零件、组合成整体，可解释性强；代价是分解一般不唯一，需要正则化或稀疏约束确定。

适用条件：数据本身非负（计数、强度、像素、词频）；追求可解释的潜在因子。应用：主题模型（$W$ 是主题词分布、$H$ 是文档-主题分布）、人脸部件发现（NMF 自动分出眼/鼻/嘴，而 PCA 给出整体幽灵脸）、音频分离、聚类、基因表达分析。

6.3 独立成分分析 ICA

给定观测信号 $X$（假设是若干统计独立源 $S$ 的线性混合 $X = AS$），ICA 估计分离矩阵 $W ≈ A^{-1}$ 以恢复源 $\hat{S} = WX$，经典算法 FastICA 通过最大化非高斯性（负熵或峰度）逐个提取独立成分。

与 PCA 的关系：PCA 找不相关（二阶）方向，只去相关；ICA 找统计独立（所有阶）方向，约束更强。标准流程是先用 PCA 白化（去相关且单位化），再在白化空间中旋转找独立方向。关键假设：源需非高斯——中心极限定理使混合比源更高斯，故「最不像高斯」的方向即独立方向；若源本身高斯则不可分离（至多一个高斯源）。

适用条件：源统计独立、非高斯、线性瞬时混合、观测数不少于源数。应用：盲源分离（经典的鸡尾酒会问题——从多麦克风混合中分出各说话人）、脑科学（fMRI / EEG 信号分离）、金融因子分解、图像边缘特征提取。

6.4 推荐系统中的矩阵分解

把用户×物品评分矩阵 $R$ 分解为两个低维矩阵 $R ≈ PQ^\mathsf{T}$，$p_u$、$q_i$ 分别是用户与物品的 $f$ 维潜在因子向量（$f$ 典型 20–100），预测评分取内积 $\hat{r}_{ui} = q_i^\mathsf{T}p_u$。

为什么不用标准 SVD：评分矩阵极度稀疏，大量项缺失，而标准 SVD 要求完整矩阵（“conventional SVD is undefined when knowledge about the matrix is incomplete”，Koren 等 2009）。从业者不填补缺失值，而是只对已观测评分最小化正则化平方误差

{%raw%} $$ \min_{P,Q}\ \sum_{(u,i)\in\kappa}\bigl(r_{ui}-q_i^{\mathsf{T}}p_u\bigr)^{2} + \lambda\bigl(\|p_u\|^{2}+\|q_i\|^{2}\bigr) $$ {%endraw%}

用梯度下降（Funk SVD，Simon Funk 2006）或交替最小二乘（ALS）求解。

因子的含义：$P$ 是每个用户在品味空间中的位置，$Q$ 是每个物品在同一空间中的位置，内积度量偏好与特征的匹配度。应用：协同过滤；Netflix Prize（2006–2009，480,189 用户 × 17,770 部电影、约一亿条评分）使该方法一举成名，至今仍是推荐系统的基线。变体有带偏置的 MF、融入隐式反馈的 SVD++、深度学习时代的神经协同过滤。

6.5 张量分解

矩阵是二阶数组，张量是 $N$ 阶（$N$ 维）数组。张量分解是矩阵分解的高阶推广，处理（用户×物品×上下文）、（样本×特征×时间）等多模态数据。两种主要形式：

• CP / PARAFAC：$\mathcal{X} ≈ \sum_{r=1}^{R} λ_r, a_r^{(1)} \circ a_r^{(2)} \circ \dots \circ a_r^{(N)}$，即 $R$ 个秩一张量之和，$R$ 的最小值定义张量秩。
• Tucker：$\mathcal{X} ≈ \mathcal{G} \times_1 A^{(1)} \times_2 \dots \times_N A^{(N)}$，$\mathcal{G}$ 是小的核心张量，可看作带核心调度的多模态 PCA。

CP 是 Tucker 的特殊情形（核心张量限制为超对角）。一个重要区别是唯一性：CP 在温和条件下通常唯一（强于矩阵 SVD——矩阵分解本身不唯一，需靠 SVD 的正交性约束），而 Tucker 不唯一（核心张量可被旋转）。应用：融入上下文的推荐、化学计量学（三维荧光光谱 PARAFAC 分离混合荧光成分）、多通道脑电、知识图谱补全；深度学习中衍生 Tensor-Train、Kronecker 因子分解等权重压缩技术。张量秩分解是 NP-hard，算法多用 ALS。

6.6 矩阵补全

给定大部分元素缺失的矩阵 $M$（只观测到 $\Omega$），目标是填满它。若假设真实矩阵低秩，则求 $\min \mathrm{rank}(X)$ s.t. $X_\Omega = M_\Omega$；因秩最小化是 NP-hard，实际用核范数 $‖X‖_* = \sum σ_i$ 作为秩的凸松弛

{%raw%} $$ \min_{X}\ \|X\|_{*} \quad \text{s.t.}\quad X_{\Omega} = M_{\Omega} $$ {%endraw%}

可用半定规划或软阈值迭代（SVT、ALM）求解，理论与压缩感知的受限等容性质（RIP）相通。

与推荐 MF 的关系：推荐 MF 是矩阵补全的一种非凸启发式实现（直接用 $R ≈ PQ^\mathsf{T}$ 的低秩参数化加 SGD/ALS）；核范数最小化是凸的理论工具，保证全局最优但计算更重。二者思想一致：用低秩先验从稀疏观测恢复完整矩阵。低秩先验之所以有效，是因为许多真实矩阵本质低秩（评分由少数品味驱动、图像由低频主导），只要观测足够随机且矩阵相干性低，远少于 $mn$ 个观测就能唯一恢复。应用：推荐系统、图像修复、传感网信号恢复、基因表达矩阵补全、调查数据缺失值填补。

七、方法之间的关系

理解矩阵分解，关键是看清它们如何互相转化、互为特例。

关系一：PCA ⟺ SVD。对中心化数据 $X$ 做 SVD $X = UΣV^\mathsf{T}$，主成分方向即 $V$ 的列、方差即 $σ_i^2$、得分即 $UΣ$ 的列。PCA 在数值上就是中心化数据的 SVD。

数据矩阵 X(中心化) ──SVD──> X = UΣVᵀ
                               │
                ┌──────────────┼──────────────┐
                ↓              ↓              ↓
          主成分方向       主成分方差      主成分得分
          = V 的列        = σᵢ²/(n-1)     = UΣ 的列

关系二：特征分解 ⟵ SVD。$A^\mathsf{T}A = VΣ^2V\mathsf{T}$、$AA^\mathsf{T} = UΣ^2U\mathsf{T}$，即 $σ^2 = λ$。SVD 把「对方阵做特征分解」推广到任意矩阵，且保证正交。

关系三：Schur ⟵ Jordan。理论上 $P^{-1}AP = J$ 完整刻画亏损结构，但数值病态；计算上用 $A = UTU^*$（Schur，QR 算法的产物，后向稳定）替代。

关系四：最小二乘的三大分解统一。对超定满秩 $A ∈ \mathbb{R}^{{m×n}$（$m>n$），$A}\mathsf{T}A$ 对称正定，其 Cholesky 因子 $A^\mathsf{T}A = R^\mathsf{T}R$ 中的 $R$ 恰好就是经济型 QR 分解 $A = QR$ 的 $R$，且 $Q = AR^{-1}$ 的列正交。三种方法解同一个最小二乘问题，区别在稳定性与速度：

方法	做法	条件数	速度	稳定性
法方程 + Cholesky	解 $A^\mathsf{T}Ax = A^\mathsf{T}b$	平方 $κ^2$	最快	病态时危险
QR	解 $Rx = Q^\mathsf{T}b$	不变 $κ$	中	标准推荐
SVD	伪逆 $x = A^+b$	最稳，可处理秩亏	最慢	最强

关系五：极分解 ⟵ SVD。$A = UΣV^\mathsf{T}$（旋转-拉伸-旋转）合并两次旋转即得 $A = (UV^{\mathsf{T})(VΣV}\mathsf{T})$（旋转-对称拉伸）。

关系六：推荐 MF ⟵ 截断 SVD 的思想。完整矩阵的低秩近似用截断 SVD $A_k = U_kΣ_kV_k^\mathsf{T}$；稀疏评分矩阵无法用标准 SVD，改造为只拟合已观测项的 Funk SVD / ALS，保留「低秩潜在结构」的思想。

八、复杂度与数值稳定性

分解	形式	适用矩阵	复杂度（flops）	数值稳定性	典型用途
特征分解	$XΛX^{-1}$	可对角化方阵	$O(n^3)$	可能病态	谱分析、振动模态、PCA 理论
Schur	$UTU^*$	任意方阵	$O(n^3)$（Hessenberg 后每步 $O(n^2)$）	后向稳定	计算特征值的标准
Jordan	$P^{-1}AP=J$	特征多项式可分裂	—	病态，避免使用	纯理论
SVD	$UΣV^\mathsf{T}$	任意 $m×n$	$O(\min(mn^2, m^2n))$	极稳	PCA、压缩、伪逆、低秩近似
QR	$QR$	任意 $m×n$	$2mn^2 - \tfrac{2}{3}n^3$	后向稳定（Householder）	最小二乘、正交化、QR 算法
极分解	$UP$	任意方阵	一次 SVD	稳定	力学、图形学
LU	$PA=LU$	方阵	$\tfrac{2}{3}n^3$	后向稳定	解 $Ax=b$、行列式、求逆
Cholesky	$LL^\mathsf{T}$	对称正定	$\tfrac{1}{3}n^3$	无需主元	解正定方程组（最快）
PCA	协方差特征分解 / SVD	数据矩阵	$O(d^2n)$	稳（用 SVD）	降维、可视化、降噪
NMF	$WH$，非负	非负矩阵	迭代	非唯一	主题模型、部件发现
ICA	$X=AS$	混合信号	迭代	需非高斯约束	盲源分离
推荐 MF	$PQ^\mathsf{T}$	稀疏矩阵	迭代（SGD/ALS）	非凸	推荐系统
张量分解	CP / Tucker	多维张量	NP-hard 秩	—	多模态数据
矩阵补全	核范数最小化	稀疏矩阵	迭代	凸	缺失值填补

关于 QR 算法的常数：满矩阵单步成本因记账方式不同有 $\tfrac{7}{3}n^3$ 与 $\tfrac{11}{6}n^3$ 两种说法（取决于 $RQ$ 的形成方式与是否利用对称性），但「Hessenberg 归约后每步从 $O(n^3)$ 降到 $O(n^2)$」这一核心结论是一致的。

九、选型决策

按问题类型选择分解：

• 解 $Ax=b$：一般方阵用 LU（部分主元）；对称正定用 Cholesky（最快且稳定）；需多次求解则分解一次、反复回代；病态或接近奇异考虑 SVD 加正则化。
• 最小二乘 $\min‖Ax-b‖^2$：默认用 QR（后向稳定、不平方条件数）；$A$ 良态且追求速度用法方程 + Cholesky；秩亏或高度病态用 SVD（伪逆，可诊断秩）。
• 求特征值：用 QR 算法（收敛到 Schur 形）；对称矩阵用对称 QR / 分治 / Jacobi；不要直接算 Jordan 形。
• 降维 / 压缩 / 降噪：线性降维用 PCA（即中心化数据 SVD）；任意矩阵低秩近似用截断 SVD（Eckart-Young 保证最优）；数据非负且要可解释用 NMF；非线性结构用核 PCA / t-SNE / UMAP / 自编码器。
• 分离混合信号：只需去相关用 PCA；需要统计独立（盲源分离）用 ICA（要求非高斯源）。
• 推荐 / 缺失值填补：稀疏用户-物品矩阵用推荐 MF（Funk SVD / ALS）；需要凸保证用核范数最小化。
• 多模态 / 多维数据：用张量分解（CP 唯一性好，Tucker 更灵活）。
• 分离刚体旋转与变形：用极分解 $A = UP$。

兜底原则：遇到不确定的矩阵、病态问题、或需要最稳健的解时，SVD 几乎总能用，代价是慢。

十、SVD 解最小二乘

SVD 解最小二乘的价值在于：它把「病态」和「秩亏」这两个让法方程崩溃的问题，变成一目了然的「奇异值大小」问题。

给定超定系统 $Ax = b$（$A \in \mathbb{R}^{m\times n}$，$m>n$），通常无精确解，求 $\hat{x} = \arg\min |Ax-b|^2$。设 $A = U\Sigma V^{\mathsf{T}}$，秩 $r$。因正交矩阵不改变 2-范数，

$$ \|Ax - b\|^2 = \|\Sigma V^{\mathsf{T}}x - U^{\mathsf{T}}b\|^2 $$

令 $y = V^{\mathsf{T}}x$、$c = U^{\mathsf{T}}b$，问题等价于 $\min |\Sigma y - c|^2$。因 $\Sigma$ 是对角的，各分量独立，展开为

$$ \|\Sigma y - c\|^2 = \sum_{i=1}^{r}(\sigma_i y_i - c_i)^2 + \sum_{i>r} c_i^2 $$

左半（$i \le r$）与 $y$ 有关、右半（$i>r$）与 $y$ 无关。对 $i \le r$，令 $y_i = c_i/\sigma_i$ 使该项为零；对 $i>r$，$y_i$ 不影响残差，最小范数解取 $y_i=0$。代回 $x = Vy$（$V$ 正交故 $V^{-1}=V{\mathsf{T}}$），得

$$ \boxed{\,\hat{x} = \sum_{i=1}^{r}\frac{u_i^{\mathsf{T}}b}{\sigma_i}\,v_i = A^{+}b\,} $$

这正是伪逆 $A^+ = V\Sigma^+U{\mathsf{T}}$（$\Sigma^+$ 把非零奇异值取倒数、其余置零）。最小残差 $|A\hat{x}-b|^2 = \sum_{i>r}(u_i^{{\mathsf{T}}b)}2$，即 $b$ 落在 $A$ 列空间正交补上的能量。

解是 $V$ 的列的线性组合——「右奇异向量展开」

上式揭示了一个深刻结构：最小二乘解 $\hat{x}$ 是 $V$ 的列（右奇异向量）的线性组合，每个 $v_i$ 的系数为 $\dfrac{u_i^{\mathsf{T}}b}{\sigma_i}$。

为什么 V 的列构成解：$V$ 是 $n\times n$ 正交矩阵，其列 ${v_1, \dots, v_n}$ 是 $\mathbb{R}^n$ 的一组标准正交基。$\mathbb{R}^n$ 中任何向量（包括解 $x$）都能写成这组基的线性组合 $x = \sum_i \alpha_i v_i$。SVD 解出的恰恰是这些系数：$\alpha_i = u_i^{\mathsf{T}}b / \sigma_i$（$i \le r$），$\alpha_i = 0$（$i > r$）。

推导：伪逆 $A^+ = V\Sigma^+U{\mathsf{T}}$ 可展开为外积之和（秩一分解）：

$$ A^+ = \sum_{i=1}^{r}\frac{1}{\sigma_i}\,v_i\,u_i^{\mathsf{T}} $$

右乘 $b$：

$$ A^+b = \sum_{i=1}^{r}\frac{1}{\sigma_i}\,v_i\,\underbrace{(u_i^{\mathsf{T}}b)}_{\text{标量}} = \sum_{i=1}^{r}\frac{u_i^{\mathsf{T}}b}{\sigma_i}\,v_i $$

每个 $v_i$ 是 $V$ 的一列，$u_i^{\mathsf{T}}b$ 是一个标量，故整个解就是「V 的列按 $\frac{u_i^{\mathsf{T}}b}{\sigma_i}$ 加权求和」。

物理含义（逐个奇异方向看）：

• $Av_i = \sigma_i u_i$，即输入方向的 $v_i$ 被放大 $\sigma_i$ 倍映射到输出方向的 $u_i$；
• $u_i^{\mathsf{T}}b$ = 右端 $b$ 在输出方向 $u_i$ 上的分量；
• $\frac{u_i^{\mathsf{T}}b}{\sigma_i}$ = 要产生这个输出分量，需要多少输入沿 $v_i$ 方向——即「逆向求解」$v_i$ 方向的贡献；
• $\sigma_i$ 大（信号方向）→ 系数小、稳定；$\sigma_i$ 小（噪声方向）→ 系数大、放大噪声。

这与对称矩阵的特征分解求逆 $A^{-1} = \sum \frac{1}{\lambda_i} x_i x_i^{\mathsf{T}}$ 完全类比——SVD 把它推广到任意矩阵，用两组正交基（$U$ 和 $V$）分别代替一组特征向量。

病态处理：截断与正则化

当某些 $\sigma_i$ 很小但非零时，$1/\sigma_i$ 会放大 $c_i$ 中的噪声。两种标准对策：

• 截断 SVD（TSVD）：只用前 $k$ 个 $\hat{x} = \sum_{i=1}^{k} \frac{u_i^{\mathsf{T}}b}{\sigma_i} v_i$，丢弃小奇异值方向；
• Tikhonov 正则化（岭回归）：解 $\min |Ax-b|^2 + \lambda|x|^2$，闭式为

$$ \hat{x}_\lambda = \sum_{i=1}^{r}\frac{\sigma_i}{\sigma_i^{2}+\lambda}(u_i^{\mathsf{T}}b)\,v_i $$

滤波因子 $\sigma_i/(\sigma_i^2+\lambda)$ 对大 $\sigma_i$ 近似 $1/\sigma_i$（保留信号）、对小 $\sigma_i$ 近似 $\sigma_i/\lambda$（衰减噪声），是比 TSVD 硬截断更平滑的软衰减。两种对策的本质都是压制 V 的列中对应小奇异值的那几项——因为这些项的系数 $1/\sigma_i$ 过大，会放大噪声。

十一、代码示例

NumPy / scikit-learn 的底层即文中所述算法（$linalg.qr$ 用 Householder、$linalg.svd$ 用 Golub-Kahan、$linalg.cholesky$ 用 Cholesky）：

import numpy as np
from numpy.linalg import lu, qr, cholesky, svd, eig
from sklearn.decomposition import PCA, NMF, FastICA, TruncatedSVD

np.random.seed(0)
A = np.random.randn(5, 5)
S = A @ A.T + 5*np.eye(5)                      # 对称正定

# 特征分解
w, V = eig(S)

# SVD 与低秩近似(Eckart-Young)
U, s, Vt = svd(A)
k = 2
A_k = U[:, :k] @ np.diag(s[:k]) @ Vt[:k, :]
A_pinv = Vt.T @ np.diag(1/s) @ U.T             # Moore-Penrose 伪逆

# LU / Cholesky / QR
P, L, Ulu = lu(A)                              # P @ A = L @ U
Lch = cholesky(S)                              # S = L @ L.T
Q, R = qr(A)                                   # A = Q @ R (Householder)

# PCA = 中心化数据 SVD
X = np.random.randn(5, 20)
Xc = X - X.mean(axis=1, keepdims=True)
pca = PCA(n_components=2).fit(Xc.T)

# SVD 解最小二乘(含截断 / 岭正则)
def svd_lstsq(A, b, trunc=None, ridge=0.0):
    U, s, Vt = np.linalg.svd(A, full_matrices=False)
    c = U.T @ b
    if trunc is not None:
        s_inv = np.zeros_like(s); s_inv[:trunc] = 1.0 / s[:trunc]
    elif ridge > 0:
        s_inv = s / (s**2 + ridge)
    else:
        s_inv = np.where(s > 1e-12, 1.0 / s, 0.0)
    return Vt.T @ (s_inv * c), s

实践中通常直接调 $np.linalg.lstsq(A, b, rcond=None)$（内部 SVD，自动处理秩亏）或 $np.linalg.pinv(A) @ b$（最小范数最小二乘解），其中 $rcond$ 控制多小的奇异值当零处理，正是内置的截断阈值。

参考资料

• Gilbert Strang, MIT 18.06 Lecture 29 — Singular Value Decomposition: https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/resources/lecture-29-singular-value-decomposition/
• Stanford CS131 — SVD and PCA: http://vision.stanford.edu/teaching/cs131_fal1819/files/12_svd_PCA.pdf
• Stanford CS229 Notes 10 — Principal Components Analysis: https://cs229.stanford.edu/notes2020spring/cs229-notes10.pdf
• Gene H. Golub, Charles F. Van Loan — Matrix Computations (4th ed.)
• Lloyd N. Trefethen, David Bau — Numerical Linear Algebra
• Peter Arbenz, ETH Zürich — QR Algorithm lecture notes: https://people.inf.ethz.ch/arbenz/ewp/Lnotes/chapter4.pdf
• David Bindel, Cornell CS6210 — Matrix Computations lectures: https://www.cs.cornell.edu/courses/cs6210/2022fa/lec/2022-09-22.pdf
• UT Austin LAFF — LU with partial pivoting stability: https://www.cs.utexas.edu/~flame/laff/alaff/chapter06-partial-pivoting-stability.html
• Koren, Bell, Volinsky (2009) — Matrix Factorization Techniques for Recommender Systems, IEEE Computer
• Wikipedia — Singular value decomposition / Principal component analysis / QR decomposition / QR algorithm / Jordan normal form / Matrix factorization (recommender systems) / Tensor rank decomposition

文章链接：
https://www.zywvvd.com/notes/study/linear-algebra/matrix-decomp/matrix-decomp-overview/matrix-decomp-overview/