课程主页：https://see.stanford.edu/Course/EE263

这次回顾第五讲，这一讲介绍了正交以及最小二乘法。

几何性质

假设$U=\left[ \begin{array}{lll}{u_{1}} & {\cdots} & {u_{k}}\end{array}\right]$正交，如果$w=Uz$，那么$|w|=|z|$，这说明

  • 乘以$U$不改变范数

  • $w=Uz$是保距的：保持距离不变

  • 性质的证明：

  • 内积同样保持不变：$\langle U z, U \tilde{z}\rangle=\langle z, \tilde{z}\rangle$

  • 如果$w=Uz,\tilde{w}=U \tilde{z}​$，那么

  • 因为范数和内积保持不变，所以角度保持不变：

  • 因此，乘以$U​$保持内积，角度和距离不变

$\mathbb R^n$的正交基

  • 假设$u_{1}, \dots, u_{n}$是$\mathbb R^n$的正交基

  • 那么称$U=\left[u_{1} \cdot \cdot \cdot u_{n}\right]$是正交的：它是方阵并且$U^TU=I$

  • 由于$U^{-1}=U^{T}$，所以$U U^{T}=I​$，即

正交基的扩张

假设$U​$是正交矩阵，所以$x=UU^Tx​$，即

  • $u_{i}^{T} x$被称为$x$在方向$u_i$上的组件
  • $a=U^Tx$将$x$解析为其$u_i$组件的向量
  • $x=Ua$从其$u_i$组件重构$x$
  • $x=U a=\sum_{i=1}^{n} a_{i} u_{i}$被称为$x$的$(u_i-)$展开

几何解释

如果$U$为正交矩阵，考虑变换$w=Uz$

  • 保持范数，即$|U z|=|z|$
  • 保持向量的角度，即$\angle(U z, U \tilde{z})=\angle(z, \tilde{z})$
例子
  • 选择（关于某些轴）
  • 反射（通过某个平面）

在$\mathbb R^2$中旋转$\theta​$的矩阵为：

这是因为$e_{1} \rightarrow(\cos \theta, \sin \theta), e_{2} \rightarrow(-\sin \theta, \cos \theta)$

通过直线$x_{2}=x_{1} \tan (\theta / 2)$反射的矩阵为：

这是因为$e_{1} \rightarrow(\cos \theta, \sin \theta), e_{2} \rightarrow(\sin \theta,-\cos \theta)$

图示如下：

Gram-Schmidt过程

  • 给定线性无关的向量$a_{1}, \ldots, a_{k} \in \mathbb{R}^{n}$，G-S过程找到正交向量$q_{1}, \dots, q_{k}$，使得

  • 因此，$q_{1}, \dots, q_{r}$是$\operatorname{span}\left(a_{1}, \ldots, a_{r}\right)$的正交基

  • 方法的粗略思想：首先使每个向量关于之前的向量正交化；然后将向量归一化为$1​$。

具体步骤如下：

  • 步骤1a：$\tilde{q}_{1} :=a_{1}$
  • 步骤1b：$q_{1} :=\tilde{q}_{1} /\left|\tilde{q}_{1}\right|​$（正规化）
  • 步骤2a：$\tilde{q}_{2} :=a_{2}-\left(q_{1}^{T} a_{2}\right) q_{1}​$（从$a_2​$中删除$q_1​$组件）
  • 步骤2b：$q_{2} :=\tilde{q}_{2} /\left|\tilde{q}_{2}\right|$（正规化）
  • 步骤3a：$\tilde{q}_{3} :=a_{3}-\left(q_{1}^{T} a_{3}\right) q_{1}-\left(q_{2}^{T} a_{3}\right) q_{2}​$（从$a_2​$中删除$q_1,q_2​$组件）
  • 步骤3b：$q_{3} :=\tilde{q}_{3} /\left|\tilde{q}_{3}\right|$（正规化）
  • 以此类推

几何意义如下：

对于第$k$步，我们有

所以对$i=1,2,\ldots ,k​$，我们有

注意到$r_{ii}\neq 0$。

$QR$分解

将之前的内容写成矩阵形式得到：$A=Q R​$，其中$A \in \mathbb{R}^{n \times k}, Q \in \mathbb{R}^{n \times k}, R \in \mathbb{R}^{k \times k}​$：

  • $Q^TQ=I_k$，$R$是上三角可逆矩阵
  • 称上述表达为$A$的$QR$分解
  • 通常使用Gram-Schmidt程序的变体计算，因为该变体程序对数值（舍入）误差不太敏感
  • $Q$的列是$\mathcal R(A)$的正交基

Gram-Schmidt的一般程序

  • 在基本的G-S中我们假设$a_{1}, \dots, a_{k} \in \mathbb{R}^{n}$是线性无关
  • 如果$a_{1}, \dots, a_{k}$线性相关，那么存在某个$j$，使得$\tilde{q}_{j}=0$，这意味着$a_j$和$a_{1}, \dots, a_{j-1}$线性相关
  • 修改后的算法：当遇到$\tilde q_j = 0$时，跳到下一个向量$a_{j+1}$并继续：
    • $r=0$
    • 对$i=1,\ldots ,k$
    • {
      • $\tilde{a}=a_{i}-\sum_{j=1}^{r} q_{j} q_{j}^{T} a_{i}$
      • 如果$\tilde{a} \neq 0${
        • $r=r+1 ; q_{r}=\tilde{a} /|\tilde{a}|$
      • }
    • }
  • $q_{1}, \dots, q_{r}$是$\mathcal R(A)$的正交基（因此$r=\operatorname{Rank}(A)$）
  • 每个$a_i$是先前生成的$q_j$的线性组合

用矩阵记号，我们有$A=QR$，并$Q^TQ=I_r$并且$R\in \mathbb R^{r\times k}$是分块阶梯矩阵：

其中$\times $非零，这里我们显然有$R$的行向量线性无关。

可以对列置换，使得$\times ​$成为矩阵的前一部分：

其中：

  • $Q^{T} Q=I_{r}​$
  • $\tilde{R} \in \mathbb{R}^{r \times r}$上三角可逆矩阵
  • $P \in \mathbb{R}^{k \times k}$是置换矩阵

应用

  • 直接产生$\mathcal{R}(A)$的正交基
  • 产生分解$A=BC$，其中$B \in \mathbb{R}^{n \times r}, C \in \mathbb{R}^{r \times k}, r=\operatorname{Rank}(A)$
  • 检查是否$b \in \operatorname{span}\left(a_{1}, \ldots, a_{k}\right)$：对$\left[a_{1} \cdots a_{k} \ b\right]$使用Gram-Schmidt
  • $R​$中的阶梯模式显示$A​$的哪些列依赖于先前的列

逐步工作：对于$p=1, \dots, k​$，一个G-S程序产生$\left[ \begin{array}{lll}{a_{1}} & {\cdots} & {a_{p}}\end{array}\right]​$的QR分解：

其中$s=\operatorname{Rank}\left(\left[a_{1} \cdots a_{p}\right]\right)$以及$R_{p}$是$R$的前$p$列构成的$s\times p$矩阵。

完全$QR$分解

利用之前的$QR$分解$A=Q_{1} R_{1}​$，我们可以写成

其中$\left[Q_{1}\ Q_{2}\right]​$正交，即$Q_{2} \in \mathbb{R}^{n \times(n-r)}​$的列和$Q_1​$正交。

为了找到$Q_2$：

  • 找到任何矩阵$\tilde{A}$，使得$[A\ \tilde{A}]$满秩，例如$\tilde{A}=I$
  • 对$[A\ \tilde{A}]$使用一般的Gram-Schmidt
  • $Q_1$是从$A$的列中获得的正交向量
  • $Q_2$是从$\tilde A$的列中获得的正交向量

即任何一组$\mathbb R^n​$中正交向量都可以扩展到标准正交基。

$\mathcal{R}\left(Q_{1}\right)​$和$\mathcal{R}\left(Q_{2}\right)​$被称为互补子空间，这是因为

  • 它们正交（即第一个子空间中的每个向量都与第二个子空间中的每个向量正交）
  • 它们的和是$\mathbb R^n$（即中的每个向量可以表示为两个向量之和，每个子空间各一个）

这可以表达为

  • $\mathcal{R}\left(Q_{1}\right) \stackrel{\perp}{+} \mathcal{R}\left(Q_{2}\right)=\mathbb{R}^{n}​$
  • $\mathcal{R}\left(Q_{2}\right)=\mathcal{R}\left(Q_{1}\right)^{\perp},\mathcal{R}\left(Q_{1}\right)=\mathcal{R}\left(Q_{2}\right)^{\perp}$（每个子空间和另一个正交互补）

我们知道$\mathcal{R}\left(Q_{1}\right)=\mathcal{R}(A)​$，那么它的正交互补空间$\mathcal{R}\left(Q_{2}\right)​$如何呢？下一部分将回答该问题。

$A$引导的正交分解

从$A^{T}=\left[ \begin{array}{cc}{R_{1}^{T}} & {0}\end{array}\right] \left[ \begin{array}{c}{Q_{1}^{T}} \\ {Q_{2}^{T}}\end{array}\right]​$，我们得出

有之前讨论可得$R_1$的行向量线性无关，所以上述事实等价于

因$\mathcal{R}\left(Q_{2}\right)=\mathcal{N}\left(A^{T}\right)​$（事实上$Q​$的列是$\mathcal{N}\left(A^{T}\right)​$的正交基）

我们得到如下结论：$\mathcal{R}(A)​$和$\mathcal{N}\left(A^{T}\right)​$是互补空间（注意$\mathcal{R}\left(Q_{1}\right)=\mathcal{R}(A)​$）：

  • $\mathcal{R}(A) \stackrel{\perp}{+} \mathcal{N}\left(A^{T}\right)=\mathbb{R}^{n}, A\in \mathbb R^{n\times k}​$

  • $\mathcal{R}(A)^{\perp}=\mathcal{N}\left(A^{T}\right),\mathcal{N}\left(A^{T}\right)^{\perp}=\mathcal{R}(A)$

  • 这称为$A\in \mathbb R^{n\times k}​$引导的$\mathbb R^n​$的正交分解

  • 每个$y\in \mathbb R^n$可以被唯一写成$y=z+w$，其中$z \in \mathcal{R}(A),w \in \mathcal{N}\left(A^{T}\right)$

  • 将$A \in \mathbb{R}^{n \times k}$换成$A^{T} \in \mathbb{R}^{k \times n}$给出$\mathbb R^k$的分解：

利用这部分的内容可以证明之前的结论：

zero零空间

$A​$称为一对一如果$\mathcal N(A) = \{0\}​$，这等价于：

  • $x$可以由$y=Ax$唯一决定（即，线性变换$y=Ax$不损失信息。）
  • 从$x$到$Ax$的映射是一对一的：不同的$x$映射到不同的$y$
  • $A$的列向量线性无关
  • $A$存在左逆，即存在$B\in \mathbb R^{n\times m}$，使得$BA=I_n$
  • $\text{det}(A^TA)\neq 0​$

结论1,2,3显然，这里补充证明结论4,5。

注意此时$A$的$QR$分解为

注意$R​$可逆。

(4)取

那么

(5)因为

所以

Onto矩阵

矩阵$A​$被称为onto，如果$\mathcal{R}(A)=\mathbb{R}^{m}​$，这等价于

  • 对任意$y$，$Ax=y$都有解
  • $A$的列张成了$\mathbb{R}^{m}$
  • $A$有右逆，即存在$B\in \mathbb R^{n\times m}$，使得$AB=I$
  • $A$的行向量线性无关
  • $\mathcal{N}\left(A^{T}\right)=\{0\}$
  • $\operatorname{det}\left(A A^{T}\right) \neq 0$

因为

所以如果$\mathcal{R}(A)=\mathbb{R}^{m}$，那么$\mathcal{N}\left(A^{T}\right)= \{0\}$，那么对$A^T$使用前一部分的结论即可。特别的，如果$A^T $的$QR$分解为

其中$R​$可逆，取

那么

Lecture 5 最小二乘法

超定线性方程组

考虑$y=Ax$，其中$A \in \mathbb{R}^{m \times n}$是严格瘦矩阵，即$m>n$，我们称

  • 该线性方程组超定（方程数量比未知数多）
  • 对大多数$y$，无法求解$x$

一个方法是近似求解$y=Ax$：

  • 定义残差或误差$r=Ax-y$
  • 找到$x=x_{\text{ls}}​$最小化$|r|​$

$x_{\text{ls}}$被称为$y=Ax$的最小二乘（近似）解。