附录 A 线性代数与数值技巧 (Linear Algebra and Numerical Techniques)
核心结论
-
矩阵分解：LU 分解 / QR 分解 / SVD / Cholesky；不同分解适合不同问题。
-
线性系统求解：直接法（高斯消元）/ 迭代法（共轭梯度）；病态系统需正则化。
-
特征值与奇异值：SVD 用于 PCA / 矩阵伪逆；特征值用于谱分析。
-
非线性最小二乘：Gauss-Newton / Levenberg-Marquardt；曲线拟合 / 相机标定。
-
稀疏矩阵求解：稀疏 Cholesky / 共轭梯度；大尺度 SfM / SLAM 后端。
|
本章主旨
附录 A 是 CV 数值计算的数学基础——把第 4 章的线性代数 / 优化公式具象化为"工具"。理解后才能看懂 OpenCV / Ceres / g2o 等库的内部实现。 |
一、核心概念
本章围绕 5 个核心概念展开：矩阵分解 → 线性系统 → 特征值 → 非线性最小二乘 → 稀疏求解。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
矩阵分解 |
LU / QR / SVD / Cholesky；不同分解适合不同问题。 |
A.1；CV 算法的基础工具。 |
线性系统求解 |
直接法（高斯消元）/ 迭代法（CG）；病态系统需正则化。 |
A.2；SfM / SLAM 后端常用。 |
特征值与奇异值 |
SVD 用于 PCA / 矩阵伪逆；特征值用于谱聚类 / Hessian 分析。 |
A.3；很多 CV 算法基于谱方法。 |
非线性最小二乘 |
Gauss-Newton / Levenberg-Marquardt；曲线拟合 / 相机标定。 |
A.4；几乎所有 CV 优化都用。 |
稀疏矩阵求解 |
稀疏 Cholesky / 共轭梯度；大尺度 SfM / SLAM 后端。 |
A.5；几千相机 + 百万点也能高效求解。 |
二、详细笔记
2.1 矩阵分解 (Matrix Decomposition)
What：把矩阵分解为更简单的形式，便于求解 / 分析。
Why：CV 算法几乎都用矩阵分解（SfM 后端 / 优化 / 特征提取）。
How：
常见分解：
-
LU 分解：
A = LU；解Ax = b→Ly = b, Ux = y。 -
QR 分解：
A = QR（Q 正交）；最小二乘首选。 -
SVD：
A = U Σ Vᵀ；秩 / 伪逆 / PCA。 -
Cholesky：
A = LLᵀ（A 正定）；高效。
|
矩阵分解选择
|
When：所有 CV 算法的数学基础。
Example*：np.linalg.solve(A, b)；np.linalg.lstsq(A, b)；scipy.linalg.cholesky。
2.2 线性系统求解 (Linear System Solving)
What：求解 Ax = b；A 是 n×n 矩阵。
Why：CV 中很多问题（相机标定 / SfM / 立体匹配）都归结为线性系统。
How：
求解方法：
-
直接法：高斯消元 / LU 分解；O(n³)；精度高。
-
迭代法：共轭梯度（CG）；O(n² · iter)；适合大稀疏。
-
正则化：Tikhonov
||Ax - b||² + λ||x||²；防过拟合 / 病态。
|
病态系统的诊断
|
When：SfM BA（直接法）；稀疏 SLAM 后端（CG）；深度学习（线性层反向传播）。
Example*：np.linalg.solve；scipy.sparse.linalg.cg；g2o / Ceres 用稀疏 Cholesky + CG。
2.3 特征值与奇异值 (Eigenvalues & SVD)
What：Av = λv（特征值）；A = U Σ Vᵀ（SVD）。
Why：SVD 是矩阵分析的"瑞士军刀"——PCA / 伪逆 / 秩 / 谱方法都基于它。
How：
SVD 应用：
-
PCA：
X = U Σ Vᵀ；主成分 =V[:, :k]。 -
伪逆：
A⁺ = V Σ⁺ Uᵀ；解最小二乘。 -
低秩近似：
X ≈ U[:, :k] Σ[:k, :k] V[:, :k]ᵀ。
|
SVD 的几何意义
|
When：PCA / 特征降维；矩阵伪逆；谱聚类；低秩矩阵恢复。
Example*：np.linalg.svd；sklearn.decomposition.PCA；cv2.SVD。
2.4 非线性最小二乘 (Nonlinear Least Squares)
What：最小化 ||f(x)||²；f 是非线性函数。
Why：CV 中曲线拟合 / 相机标定 / PnP / BA 都用。
How：
求解算法：
-
Gauss-Newton：
x ← x - (Jᵀ J)⁻¹ Jᵀ f(x)（J = Jacobian）；快但需初始接近。 -
Levenberg-Marquardt：
x ← x - (Jᵀ J + λI)⁻¹ Jᵀ f(x)；调节 λ 平衡收敛。
|
LM vs Gauss-Newton
|
When：曲线 / 表面拟合；相机标定；SfM / SLAM 后端；BA 优化。
Example*：scipy.optimize.least_squares(method='lm')；Ceres / g2o；OpenCV cv2.solvePnP。
2.5 稀疏矩阵求解 (Sparse Matrix Solving)
What：A 是稀疏矩阵（多数元素为 0）的 Ax = b 求解。
Why：SfM / SLAM 中 BA 的 Hessian 矩阵是稀疏的；高效稀疏求解是实时性的关键。
How：
稀疏求解：
-
稀疏 Cholesky：利用稀疏模式分解；O(n^1.5) 而非 O(n³)。
-
共轭梯度 (CG)：迭代法；O(n · iter)；无需分解。
-
预条件子：加速 CG 收敛。
|
SLAM 后端的稀疏性
|
When：SfM / SLAM 后端；SLAM 闭环；稀疏机器学习。
Example*：g2o（通用图优化）；Ceres（非线性最小二乘）；GTSAM（因子图）。
三、关键图表
非可视化条目
|
非可视化条目（表 / 算法）
|
核心公式对照表
|
核心公式对照表
|