正交

1. 正交的定义

• 正交向量 (Orthogonal Vectors)：如果两个向量 $v$ 和 $w$ 正交，那么它们的点积为0：

$$v^Tw=0$$

• 正交子空间 (Orthogonal Subspaces)：如果子空间 $V$ 和子空间 $W$ 是正交的，则 $V$ 中的每一个向量都必须垂直于 $W$ 中的每一个向量。

两个看上去垂直的平面并不一定是正交子空间，例如经典的“墙角”模型，虽然两个平面是垂直的，但是它们的交线属于这两个平面，一条线不可能垂直于它自己。

对于我们之前讨论的四个子空间：

• 行空间与零空间是正交的。
• 列空间与左零空间 (Nullspace of $A^T$) 是正交的。

下面我们证明一下矩阵 $A$ 的行向量所在的空间，会垂直于方程 $Ax=0$ 的解空间。对于方程：

$$\begin{bmatrix} \text{— row 1 —} \\ \vdots \\ \text{— row m —} \end{bmatrix} \begin{bmatrix} x \end{bmatrix} = \begin{bmatrix} 0 \\ \vdots \\ 0 \end{bmatrix}$$

这个矩阵乘法表明：

• $(\text{row 1})\cdot x = 0 \Rightarrow x \perp \text{(row 1)}$
• $(\text{row m})\cdot x = 0 \Rightarrow x \perp \text{(row m)}$

因为零空间向量 $x$ 垂直于每一行，则 $x$ 也垂直于这些行的任何线性组合，也即垂直于整个行空间。列空间与左零空间同理。

2. 正交补

正交补除了正交之外，还要求两个空间的维数相加等于整个空间的维数。一个子空间的正交补记作 $V^{\perp}$，它包含了所有垂直于 $V$ 的向量。

既然我们将 $\mathbb{R}^n$ 拆分成了两个正交补空间（这里我们以行空间和零空间为例），那么任意一个向量 $x$ 都可以被唯一地拆分为

$$x = x_r+x_n$$

其中 $x_r$ 为属于行空间的分量，$x_n$ 为属于零空间的分量。当我们让矩阵 $A$ 作用于 $x$ 上时：

$$Ax=A(x_r+x_n)$$

$x_n$ 这个零空间向量变成了0，真正有作用的行空间向量被映射到了列空间中。更为重要的是，这个映射是一一对应且可逆的。也就是说我们可以通过剥离零空间得到一个可逆的核心部分。例如下面的矩阵：

$$A=\begin{bmatrix} 3 & 0 & 0 & 0 & 0\\[4pt] 0 & 5 & 0 & 0 & 0\\[4pt] 0 & 0 & 0 & 0 & 0 \end{bmatrix}$$

实际有意义的部分为：

$$\begin{bmatrix}3 & 0\\0 & 5\end{bmatrix}$$

一一对应的证明：假设存在两个不同行空间向量 $x_a$、$x_b$ 满足 $Ax_a=b$ 且 $Ax_b=b$，那么$A(x_a-x_b)=0$，则 $x_a-x_b$ 这个向量在零空间中，但是因为 $x_a$ 与 $x_b$ 不相同的话，$x_a-x_b$ 属于行空间，矛盾！

3. 投影

$a.$ 直线上的投影

在研究到子空间的投影前，我们先从最简单的直线投影入手。假设我们想将 $b$ 投影到 $a$ 上，我们依照以下三个步骤计算投影：

1. 找系数 $\hat{x}$。
2. 找向量 $p$。
3. 找矩阵 $P$。

首先是找系数 $\hat{x}$。投影点 $p$ 既然在 $a$ 所在的直线上，那么 $p$ 一定是 $a$ 的某个倍数。我们把这个倍数设为 $\hat{x}$。对于投影点 $p$ 有如下重要性质：

• 误差向量 $e = b - p = b - \hat{x}a$ 必须垂直于直线 $a$。

也即：

$$a \cdot (b - \hat{x}a) = 0 \;\;\text{or}\;\; a^T (b - \hat{x}a) = 0$$

可解得：

$$\hat{x} = \frac{a^T b}{a^T a}$$

将求得的倍数代回，便可得到投影向量 $p$：

$$p = a \hat{x} = a \frac{a^T b}{a^T a}$$

将上面的式子改写成矩阵形式，有：

$$\begin{aligned} p &= \frac{a\,(a^T b)}{a^T a} \\ &= \left(\frac{a a^T}{a^T a}\right) b \\ \Rightarrow P &= \frac{a a^T}{a^T a} \end{aligned}$$

$P$ 即是投影矩阵。投影矩阵有如下的性质：

• 幂等性：$P^2 = P$
• 互补投影：$I - P$ 将向量投影到误差向量 $e$ 所在空间，也即投影到垂直于 $a$ 的平面上：

$$(I - P)b = b - Pb = b - p =$$

$b.$ 子空间中的投影

同样地，在多维子空间中，我们也按照前面的步骤进行投影，我们的目标是：给定向量 $b$ 和矩阵 $A$, $A$ 的列向量 $a_1, \dots, a_n$ 定义了子空间，找到系数向量 $\hat{x}$，使得投影 $p = A\hat{x}$ 离 $b$ 最近。

同样地，在多维子空间中，误差向量 $e = b - A\hat{x}$ 也必须垂直于子空间。这意味着 $e$ 必须垂直于子空间的每一个基向量（即 $A$ 的每一列）。

$$\begin{aligned} a_1^T\,(b - A\hat{x}) &= 0 \\ \vdots\quad\quad & \\ a_n^T\,(b - A\hat{x}) &= 0 \end{aligned}$$

也即：

$$A^T (b - A\hat{x}) = 0$$

整理上面的方程，我们得到了著名的正规方程：

$$A^T A \hat{x} = A^T b$$

接下来我们开始求解这个方程。如果 $A$ 的列线性无关，则 $A^T A$ 可逆：

$$\hat{x} = (A^T A)^{-1} A^T b$$

于是

$$p = A\hat{x} = A(A^T A)^{-1} A^T b \;\;\Rightarrow \;\; P = A(A^T A)^{-1} A^T$$

注意：当 $A$ 是长方形矩阵时，$A$ 不可逆，因此不要随意把 $P$ 的表达式中的 -1 打开！

4. 最小二乘法

$a.$ 引入

在现实中，我们会想用直线来拟合数据。假设我们需要对一系列数据点用 $y=Cx+D$，我们会得到下面的方程组：

$$\begin{aligned} C x_1 + D &= y_1 \\ C x_2 + D &= y_2 \\ \vdots\quad &\vdots \\ C x_n + D &= y_n \end{aligned}$$

写成矩阵形式：

$$Ax=b$$

但是当数据点不共线时，方程无解。使用前面投影的思路，我们可以不去找 $b$，而是找一个在 $A$ 的列空间里、距离 $b$ 最近 的向量，也即投影 $p$，于是我们的任务便变为求解：

$$A\hat{x}=p$$

这个向量到 $b$ 的距离就是我们前面提到的误差向量 $e=b-p$。同样地，$e$ 垂直于 $A$ 的列空间：

$$A^T e = 0$$

将 $e=b-p$ 带入，就得到了和前面一模一样的正规方程：

$$A^T A \hat{x} = A^T b$$

这个拟合方法就是最小二乘法。我们只需要求解正规方程，即可得到最小二乘拟合直线。

$b.$ 拟合步骤

给定数据点 $(t_1, y_1), (t_2, y_2), \dots, (t_m, y_m)$，我们希望拟合直线 $y = \beta_0 + \beta_1 t$。具体步骤如下：

1. 构造向量 $b$：这个就是我们的因变量：

$$b = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_m \end{bmatrix}$$

2. 构造矩阵 $A$：这个就是我们的自变量。由于线性方程里有一个截距项 $\beta_0$，它相当于 $\beta_0 \times 1$。所以我们需要在 $A$ 里人为添加一列全是 1 的列：

$$A = \begin{bmatrix} 1 & t_1 \\ 1 & t_2 \\ \vdots & \vdots \\ 1 & t_m \end{bmatrix}$$

我们需要求解：

$$x = \begin{bmatrix} \beta_0 \\ \beta_1 \end{bmatrix}$$

只需直接套用公式即可：

$$\hat{x} = (A^T A)^{-1} A^T b$$

注意，最小二乘拟合方法不局限于直线，对二次曲线等也可以拟合。例如对于 $y=Cx^2+DX+E$，我们依然可以将 $(x_i, y_i)$ 带入，得到 $C,D,E$ 的线性方程组，然后使用正规方程求解。

4. 正交化

$a.$ 正交矩阵

• 如果一组向量 $q_1, \dots, q_n$ 满足两个条件：
  • 互相垂直：$q_i^T q_j = 0$ ($i \neq j$)。
  • 长度为1：$q_i^T q_i = 1$ ($i = j$)。

那么它们就是标准正交向量。将这些向量放在矩阵 $Q$ 的列中，则 $Q^T Q$ 必然是单位矩阵。

如果 $Q$ 为方阵，则 $Q$ 被称为正交矩阵。

$b.$ 使用正交基投影

我们前面的子空间投影公式以及对应计算结果如下：

$$\begin{aligned} A^T A \,\hat{x} &= A^T b \\ \hat{x} &= (A^T A)^{-1} A^T b \\ p &= A\,(A^T A)^{-1} A^T b \\ P &= A\,(A^T A)^{-1} A^T \end{aligned}$$

当我们将 $A$ 换成正交矩阵后，这些计算结果会变的非常简洁：

$$\begin{aligned} I\hat{x} &= Q^T b \\ \hat{x} &= Q^T b \\ p &= Q Q^T b \\ P &= Q Q^T \end{aligned}$$

我们将 $p$ 的计算式展开：

$$\begin{aligned} p &= \begin{bmatrix} q_1 & \dots & q_n \end{bmatrix} \begin{bmatrix} q_1^T b \\[4pt] \vdots \\[4pt] q_n^T b \end{bmatrix} \\[6pt] &= \sum_{i=1}^{n} q_i\,(q_i^T b) \;=\; q_1(q_1^T b) + \dots + q_n(q_n^T b) \end{aligned}$$

这里的 $q_i^T b$ 是 $b$ 在 $q_i$ 方向上的投影长度。整个投影 $p$ 就是这些分量简单的叠加。因为 $q$ 之间是垂直的，求 $b$ 在 $q_1$ 上的分量时，完全不用管 $q_2$。

$c.$ Gram-Schmidt 正交化

$i.$ 正交化过程

下面我们详细讲解怎么将普通的基转换成正交基。一个简单的思路是从每个新向量中，减去它在旧向量方向上的投影。。

假设我们有三个向量 $a,b,c$，则我们按照如下步骤进行变换：

1. 确定第一个方向 $A$：直接取第一个向量 $A = a$。
2. 然后确定第二个方向 $B$：我们希望 $B \perp A$，于是用 $b$ 减去它在 $A$ 上的投影：$B = b - \frac{A^T b}{A^T A} A$。
3. 然后确定第三个方向 $C$：同样地，我们用 $c$，减去它在 $A$ 上的投影，再减去它在 $B$ 上的投影：$C = c - \text{proj}_A(c) - \text{proj}_B(c) = c - \frac{A^T c}{A^T A} A - \frac{B^T c}{B^T B} B$。
4. 最终我们将求得的向量归一化，即得标准正交基：

$$q_1 = \frac{A}{||A||}, \quad q_2 = \frac{B}{||B||}, \quad q_3 = \frac{C}{||C||}$$

$ii.$ QR 分解

如果说 LU 分解是高斯消元法的矩阵形式，那么 QR 分解就是 Gram–Schmidt 的矩阵形式。

我们从 $A$ 的列向量 $a_1, \dots, a_n$ 出发，经过前面的 Gram–Schmidt 过程，得到一组标准正交向量 $q_1, \dots, q_n$，把它们放进矩阵 $Q$ 中，有：

• $a_1 = r_{11}\,q_1$.
• $a_2 = r_{12}\,q_1 + r_{22}\,q_2$.
• 第 $k$ 步：$a_k = \displaystyle\sum_{j=1}^{k} r_{jk}\,q_j$.

用矩阵表示，我们可以得到下面的分解：

$$A = Q R = \begin{bmatrix} q_1 & q_2 & \cdots & q_n \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{bmatrix} = \begin{bmatrix} r_{11} q_1 & r_{12} q_1 + r_{22} q_2 & \cdots & r_{1n} q_1 + r_{2n} q_2 + \cdots + r_{nn} q_n \end{bmatrix}.$$

其中对角线元素 $r_{kk}$ 正好是 Gram-Schmidt 过程中计算出的那些长度（$||A||, ||B||, ||C||$）。它们都是正数。

QR 分解在最小二乘法中非常有用，回到我们的正规方程：

$$A^T A \hat{x} = A^T b$$

我们将 $A=QR$ 带入：

$$\begin{alignedat}{2} & A^T A &&= (QR)^T (QR) = R^T Q^T Q R \\ \Rightarrow\quad & A^T A &&= R^T R \end{alignedat}$$ $$\begin{alignedat}{2} & A^T b &&= (QR)^T b = R^T Q^T b \\ \Rightarrow\quad & R^T R\,\hat{x} &&= R^T Q^T b \\ \Rightarrow\quad & R\,\hat{x} &&= Q^T b \end{alignedat}$$

于是原方程化为：

$$R^T R \hat{x} = R^T Q^T b$$

由于 $R$ 是可逆上三角矩阵，左右同乘 $(R^T)^{-1}$：

$R \hat{x} = Q^T b$

这个式子非常好计算，由于 $R$ 是上三角矩阵，直接用回代法就能很快解出 $\hat{x}$