EE263 Lecture 5 Least-squares

课程主页: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$的最小二乘(近似)解。

本文标题:EE263 Lecture 5 Least-squares

文章作者:Doraemonzzz

发布时间:2019年05月23日 - 22:17:00

最后更新:2019年05月24日 - 13:27:04

原始链接:http://doraemonzzz.com/2019/05/23/EE263 Lecture 5 Least-squares/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。