线性代数基础

Base

对于矩阵 A，对齐做 SVD 分解，即 $U\Sigma V=svd(A)$. 其中 U 为 $A{A}^T$的特征向量，V 为 $A^{T}A$的特征向量。 $\Sigma$ 的对角元素为降序排序的特征值。显然，U、V矩阵中的列向量相互正交，所以也可以视 V 为svd分解给出了A的列向量空间的正交基，其中最大奇异值（或特征值）对应的特征向量捕捉了数据变化的最大方向。

求满足 Ax=0 的 x

显然该问题等价于 $$x^T{A}^{T}Ax=0$$.
此问题有非零解 => A不满秩 => 行列式为0 => $A^{T}A$ 的特征值至少有一个为0.

• 考虑$A$的秩的为 k-1, 那么 $A^{T}A$ 的特征值有一个为0。所以svd分解后V矩阵的最后一列 $x^{\ast }$ 就是特征值为 0 所对应的特征向量，即 $A^{T}A{x}^{\ast }=0\ast x^{\ast }=0$.
  对于超定方程，极有可能不存在解析解，但存在最小二乘解满足 $\Vert Ax{\Vert }_2$ 最小，即最小的特征值所对应的特征向量。常见的这类问题如：已知一些三维空间中大致落在二维平面上的点，用n*3的矩阵P描述，求这个平面的法向量 n。
• 考虑$A$的秩的为 k-2，那么那么 $A^{T}A$ 的特征值有两个为0。
  例如，已知一些落在直线上的三维点，用n*3的矩阵描述这些点，求这条线的方向n。那么显然就是求满足 $ma{x}_x\Vert Ax{\Vert }_2$的最小二乘解，也就是最大的特征值对应的特征向量。另外，两个为0的特征值所对应的特征向量反应了在垂直直线方向的趋势，或者说向量投影到垂直直线方向(法平面)的投影。
  另一个例子：存在一个bearing vector，由于bearing vector的模长固定为1，因此只能在球面上移动，其自由度为2。为了描述bearing vector的误差，所以采用bearing vector在其切平面的投影作为量化方式。那么对 bearing vectord的转置做SVD分解，则两个为0的奇异值对应的特征向量就是切平面的基。

求解Ax = b的x

此问题等价于求 $Ax-b=0$。

• 当 $rank(A|b)=rank(A)<k$, 有特解+通解多个解
• 当 $rank(A|b)=rank(A)=k$, 有唯一解
• 当 $rank(A|b)>rank(A)$, 无解

求解线性方程组 ( Ax = b ) 的方法有多种，具体选择取决于矩阵 ( A ) 的特性（例如，是否是方阵、是否是稀疏矩阵、是否满秩等）。以下是常见的几种方法：

1. 直接求解法

适用于方阵 ( A ) 为非奇异矩阵的情况（即 ( A ) 可逆）。

1.1 矩阵逆法

• 如果 ( A ) 是方阵且非奇异（满秩），我们可以通过矩阵的逆求解：
  $$x=A^{-1}b$$
• 优点：理论上适用于所有满秩方阵。
• 缺点：计算逆矩阵代价较高，尤其是对于大规模矩阵，数值不稳定性也可能导致精度问题。

1.2 高斯消去法

• 高斯消去法是一种通过初等行变换将 ( A ) 化为上三角矩阵，然后使用回代法求解 ( x ) 的方法。
• 步骤：
  1. 将 ( A ) 化为上三角矩阵（消元过程）。
  2. 从最后一个方程开始回代求解各个未知数。
• 优点：适合解决大部分线性方程组问题。
• 缺点：在稀疏矩阵或病态矩阵情况下可能表现不好。

1.3 LU 分解

• 将 ( A ) 分解为两个矩阵 ( L )（下三角矩阵）和 ( U )（上三角矩阵），使得 ( A = LU )。
• 分两步解决：
  1. 求解 ( Ly = b )（前向替换）。
  2. 求解 ( Ux = y )（回代）。
• 优点：可以高效地处理多次相同矩阵 ( A ) 但不同向量 ( b ) 的情况。
• 缺点：不适合奇异或病态矩阵。

2. 迭代求解法

适合大规模、稀疏矩阵，特别是在矩阵 ( A ) 具有特殊结构（例如稀疏或对称正定）的情况下。

2.1 Jacobi 方法

• 假设矩阵 ( A ) 可以分解为对角矩阵 ( D ) 和严格三角矩阵 ( L + U )，即 ( A = D + (L + U) )。
• 通过迭代更新：
  $$x^{(k+1)}=D^{-1}(b-(L+U)x^{(k)})$$
• 优点：实现简单，适合并行计算。
• 缺点：收敛速度较慢，且不适用于所有矩阵，尤其是条件数较大的矩阵。

2.2 Gauss-Seidel 方法

• 类似于 Jacobi 方法，但在每次更新时使用新的值：
  $$x_i^{(k+1)}=\frac{1}{A_{ii}}\left(b_i-\sum _{j=1}^{i-1}{A}_{ij}{x}_j^{(k+1)}-\sum _{j=i+1}^n{A}_{ij}{x}_j^{(k)}\right)$$
• 优点：比 Jacobi 方法收敛快。
• 缺点：仍可能在某些条件下收敛缓慢。

2.3 共轭梯度法

• 适用于对称正定矩阵。该方法是一种梯度下降的改进形式，通过寻找共轭方向来加速收敛。
• 步骤：
  1. 初始化 ( x_0 )。
  2. 迭代更新：
     $$x_{k+1}=x_k+{\alpha }_k{p}_k$$
     其中 ( p_k ) 是共轭方向，( \alpha_k ) 是步长。
• 优点：对大规模、稀疏、对称正定矩阵非常高效。
• 缺点：只适用于对称正定矩阵，且需要合适的预条件来保证收敛性。

3. 奇异值分解 (SVD)

适用于任意矩阵 ( A )，包括矩阵不满秩或奇异的情况。

• 奇异值分解将 ( A ) 分解为 ( A = U \Sigma V^T )，其中 ( U ) 和 ( V ) 是正交矩阵，( \Sigma ) 是对角矩阵，包含矩阵的奇异值。
• 求解过程为：
  $$x=V{\Sigma }^{-1}{U}^{T}b$$
• 优点：SVD 能处理任何矩阵，包括奇异矩阵和非方阵，是最为稳定的求解方法之一。
• 缺点：计算复杂度高，不适合大规模问题。

4. QR 分解

• QR 分解将矩阵 ( A ) 分解为正交矩阵 ( Q ) 和上三角矩阵 ( R )，即 ( A = QR )。
• 求解步骤：
  1. 将方程变为 ( QRx = b )。
  2. 左乘 ( Q^T )，得到 ( Rx = Q^T b )。
  3. 用回代法求解上三角矩阵 ( R ) 的方程。
• 优点：稳定性好，特别适用于不满秩的矩阵。
• 缺点：比高斯消去法稍微复杂，计算量略大。

5. 伪逆法（Moore-Penrose 逆）

适用于矩阵 ( A ) 不为方阵或不满秩的情况。

• 如果 ( A ) 是不方的或者不满秩，我们可以通过伪逆矩阵 ( A^+ ) 求解：
  $$x=A^{+}b$$
  其中 ( A^+ ) 是 ( A ) 的 Moore-Penrose 伪逆。
• 优点：适用于任何矩阵（包括矩阵不满秩、奇异的情况），能找到最小范数解。
• 缺点：计算伪逆较复杂，尤其是对于大规模矩阵。

总结

• 对于方阵且 ( A ) 可逆，常用 高斯消去法 或 LU 分解。
• 对于大规模稀疏矩阵或需要迭代求解时，Jacobi 方法、Gauss-Seidel 方法 和 共轭梯度法 适用。
• 对于奇异或不满秩的矩阵，SVD 或 伪逆法 能保证稳定的解。
• QR 分解 和 高斯消去法 常用于数值稳定性要求较高的情境。

Wahba问题 Rp = q求R的解法

有多对 $p$ 和 $q$ 向量满足 $Rp=q$，并且已知 $R$ 是旋转矩阵。
旋转矩阵的性质

1. 正交性：旋转矩阵 $R$ 是正交矩阵，满足：
   $$R^{T}R=I$$
   这意味着它的逆矩阵等于它的转置，即 $R^{-1}=R^T$。

2. 行列式：旋转矩阵的行列式为 1，即 $\det (R)=1$，这表示它是一个保形矩阵，不改变向量的长度。

3. 维数限制：在二维和三维空间，旋转矩阵分别具有特定的形式：

   • 在 二维 空间，旋转矩阵为：
     $$R=\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]$$
     其中 $\theta$ 是旋转角度。
   • 在 三维 空间，旋转矩阵可以通过旋转轴和旋转角度来表示。

1. $R=[I+[\omega {]}_{\times }]$

https://blog.csdn.net/J10527/article/details/70140264
https://openresearch.lsbu.ac.uk/download/e13aba3b625d9041f0f33b2beae1715ca347b3fd5ac684d97b47f5fe38f32a0a/84156/CayleyMap%28corrected%29.pdf

2. 求解二维旋转矩阵

在二维空间，旋转矩阵的形式是固定的，可以通过直接推导出旋转角度 $\theta$ 来构造旋转矩阵 $R$。

对于已知的一对向量 $p$ 和 $q$，根据旋转矩阵的定义：
$$q=Rp=\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]\left[\begin{array}{c}{p}_1\\ p_2\end{array}\right]$$
我们可以通过以下步骤求解旋转角度 $\theta$：

1. 归一化：确保 $p$ 和 $q$ 都是单位向量（如果不是，首先对它们进行归一化），因为旋转矩阵只改变方向而不改变向量的长度。
2. 计算旋转角度：使用向量 $p$ 和 $q$ 的点积与叉积来求解旋转角度 $\theta$：
   $$\cos \theta =\frac{p\cdot q}{\Vert p\Vert \Vert q\Vert }$$
   $$\sin \theta =\frac{\text{det}(p,q)}{\Vert p\Vert \Vert q\Vert }$$
   其中，$\text{det}(p,q)$ 是向量 $p$ 和 $q$ 的二维行列式：
   $$\text{det}(p,q)=p_1{q}_2-p_2{q}_1$$
3. 构造旋转矩阵：一旦得到了 $\theta$，就可以直接构造出旋转矩阵 $R$：
   $$R=\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]$$

3. 求解三维旋转矩阵

在三维空间，旋转矩阵 $R$ 可以通过轴角旋转表示（Rotation around an axis by an angle），即用旋转轴 $\mathbf{n}$ 和旋转角度 $\theta$ 来表示。

如果给定的向量对 $p$ 和 $q$ 是三维向量，可以通过以下步骤求解旋转矩阵：

1. 计算旋转轴：旋转轴 $\mathbf{n}$ 是垂直于 $p$ 和 $q$ 的单位向量，表示为它们的叉积：
   $$\mathbf{n}=\frac{p\times q}{\Vert p\times q\Vert }$$
   如果叉积为零（即 $p$ 和 $q$ 共线），说明旋转轴不确定，只有纯粹的角度旋转。

2. 计算旋转角度：旋转角度 $\theta$ 由 $p$ 和 $q$ 的点积决定：
   $$\cos \theta =\frac{p\cdot q}{\Vert p\Vert \Vert q\Vert }$$
   也可以用叉积的大小来确定角度的正负。

3. 构造旋转矩阵：使用 Rodrigues 旋转公式 构造旋转矩阵 $R$：
   $$R=I+\sin \theta [\mathbf{n}{]}_{\times }+(1-\cos \theta )[\mathbf{n}{]}_{\times }^2$$
   其中，$[\mathbf{n}{]}_{\times }$ 是旋转轴 $\mathbf{n}$ 的反对称矩阵：
   $$[\mathbf{n}{]}_{\times }=\left[\begin{array}{ccc}0& -n_3& n_2\\ n_3& 0& -n_1\\ -n_2& n_1& 0\end{array}\right]$$
   通过这个公式，可以直接构造出旋转矩阵。

4. 【SVD解法】多对向量的最小二乘法（针对旋转矩阵）

如果有多对 $p$ 和 $q$ 向量，并且 $R$ 是一个旋转矩阵，可以使用 Wahba’s 问题 来求解最优旋转矩阵。

Wahba’s 问题是一个经典的优化问题，目标是找到使得 $R{p}_i$ 最接近 $q_i$ 的旋转矩阵 $R$。其求解步骤如下：

1. 定义误差函数：
   $$\underset{R}{\min }\sum _i\Vert R{p}_i-q_i{\Vert }^2$$
2. 通过 Kabsch 算法 或 SVD 分解 来求解旋转矩阵。SVD 分解的步骤为：
   • 构造矩阵 $H=P{Q}^T$，其中 $P$ 和 $Q$ 分别是所有 $p$ 向量和 $q$ 向量的列组合矩阵。
   • 对 $H$ 进行 SVD 分解：$H=U\Sigma V^T$。
   • 最优旋转矩阵 $R$ 为：
     $$R=V{U}^T$$
     具体推导过程为：
     $$\begin{array}{c}\begin{array}{rl}& \underset{R}{\min }\sum _i\Vert R{p}_i-q_i{\Vert }_2\\ =& \underset{R}{\min }\sum _i((R{p}_i-q_i{)}^T(R{p}_i-q_i))\\ =& \underset{R}{\min }\sum _i(p_i^T{p}_i+q_i^T{q}_i-2q_i^{T}R{p}_i)\\ =& \underset{R}{\max }\sum _i(q_i^{T}R{p}_i)\\ =& \underset{R}{\max }tr(Q^{T}RP)\\ =& \underset{R}{\max }tr(RP{Q}^T)\\ =& \underset{R}{\max }tr(RH)\\ \Rightarrow & R^{\ast }=V^{T}U\end{array}\end{array}$$
     其中 $H = U\Sigma V^T $。