EE263 Lecture 4 Orthonormal sets of vectors and QR factorization

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

这次回顾第四讲,这一讲继续复习线性代数,然后介绍了正交的概念。

矩阵的零空间

$A\in \mathbb R^{m\times n}$的零空间定义为

  • $\mathcal N(A)$是通过$y=Ax$映射到零向量的向量
  • $\mathcal N(A) $是和$A$的所有行向量都正交的向量的集合
  • 如果$y=Ax,z\in \mathcal N(A)$,那么$y=A(x+z)$
  • 相反,如果$y=Ax, y=\tilde A x$,那么存在某个$z\in \mathcal N(A)$,使得$\tilde x = x+z$

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$
  • $\text{det}(A^TA)\neq 0$

这部分的证明后续会补充。

零空间的解释

假设$z\in \mathcal N(A)$,$y=Ax$代表对于$x$的度量。

  • 传感器无法检测到$z$,因为传感器读数为零
  • $x$和$x+z$无法区分开,因为$Ax=A(x+z)$

$\mathcal N(A)$表征由度量$y=Ax $中$x$的模糊度。

$y=Ax$代表输入$x$的输出

  • $z$是没有结果的输出
  • $x$和$x+z$有同样的结果

矩阵的值域

$A\in \mathbb R^{m\times n}$的值域定义为

$\mathcal{R}(A)$可以被解释为

  • 可以通过线性映射$y=Ax$“命中”的向量集合
  • $A$的列张成的空间
  • 使得$Ax = y$有解的向量$y$的集合

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$

最后两个性质后续会证明。

值域的解释

假设$v \in \mathcal{R}(A), w \notin \mathcal{R}(A)$。

$y=Ax$代表对于$x$的度量。

  • $y=v$是一种可能的或相容的传感器信号
  • $y=w$是不可能或不相容的; 传感器出现故障或模型出错

$y=Ax$表示输入$x$产生的输出

  • $v$是可能的结果或输出
  • $w$不可能是结果或输出

$\mathcal R(A)$表征可能的结果或可实现的输出。

$A\in \mathbb R^{n\times n}$可逆或者非奇异,如果$\operatorname{det} A \neq 0$,这等价于

  • $A​$的列是$\mathbb R^n​$的基

  • $A$的行是$\mathbb R^n$的基

  • $y=Ax$对每个$y\in \mathbb R^n$有唯一解

  • $A$有(左和右)逆,用$A^{-1} \in \mathbb{R}^{n \times n}$表示,并且

  • $\mathcal{N}(A)=\{0\}$

  • $\mathcal{R}(A)=\mathbb{R}^{n}$

  • $\operatorname{det} A^{T} A=\operatorname{det} A A^{T} \neq 0$

最后两个性质后续会证明。

逆的解释

假设$A\in \mathbb R^{n\times n }$有逆$B=A^{-1}$

  • $x=By$是通道$y=Ax $的完美(前置或后置)均衡器
  • $x=By$是$Ax=y$的唯一解

对偶基的解释

  • 令$a_i$是$A$的列,$\tilde b_i^T$是$B=A^{-1}$的行

  • 从$y=x_{1} a_{1}+\cdots+x_{n} a_{n}$以及$x_{i}=\tilde{b}_{i}^{T} y$,我们得到

    因此,逆矩阵的行的内积给出了矩阵列向量展开的系数

  • $\tilde{b}_{1}, \ldots, \tilde{b}_{n}$和$a_{1}, \dots, a_{n}​$被称为对偶基

矩阵的秩

我们定义矩阵$A\in \mathbb R^{m\times n }$的秩为

有如下性质:

  • $\operatorname{rank}(A)=\operatorname{rank}\left(A^{T}\right)$
  • $\text{rank}(A)$是$A$的行向量和列向量极大线性无关组的数量,因此$\operatorname{rank}(A) \leq \min (m, n)$
  • $\operatorname{rank}(A)+\operatorname{dim} \mathcal{N}(A)=n​$

维度守恒

$\operatorname{rank}(A)+\operatorname{dim} \mathcal{N}(A)=n​$的解释如下:

  • $\text{rank}(A)$是映射$y=Ax$“命中”的集合的维度
  • $\text{dim}\mathcal N(A)​$是通过$y = Ax​$是“压缩”为$0​$的集合的维度
  • “维度守恒”:输入的每个维度都被压缩为零或最终输出
  • 粗糙的说:
    • $n$是输入$x$的自由度
    • $\text{dim}\mathcal N(A)$是从$x$到$y = Ax$的映射中丢失的自由度
    • $\text{rank}(A)$是输出$y$的自由度

“编码”对秩的解释

  • 乘积的秩:$\operatorname{rank}(B C) \leq \min \{\operatorname{rank}(B), \operatorname{rank}(C)\}$

  • 因此如果$A=BC, B \in \mathbb{R}^{m \times r}, C \in \mathbb{R}^{r \times n}​$,那么$\operatorname{rank}(A) \leq r​$

  • 相反:如果$\operatorname{rank}(A) = r$,那么$A\in \mathbb R^{m\times n }$可以被分解$A=BC, B\in \mathbb R^{m\times r},C\in \mathbb R^{r\times n}$:

  • $\operatorname{rank}(A) = r$是从$x$重构$y$需要的最小的向量数量

应用:快速矩阵乘法

  • 我们需要计算矩阵向量乘积$y=Ax,A\in \mathbb R^{m\times n}$
  • $A$有分解$A=BC, B\in \mathbb R^{m\times r}$
  • 直接计算$y=Ax$需要$mn$个操作
  • 利用$y=B(Cx)$计算$y=Ax$需要$r n+m r=(m+n) r$
  • 如果$r \ll \min \{m, n\}$,那么可以节省大量运算

满秩矩阵

对于矩阵$A\in \mathbb R^{m\times n}$,我们总有$\operatorname{rank}(A) \leq \min (m, n)$;如果$\operatorname{rank}(A) =\min (m, n)$,那么称$A$满秩。

  • 对于方阵,满秩意味着非奇异。
  • 对于瘦矩阵($m\ge n​$),满秩意味着列向量线性无关
  • 对胖矩阵($m\le n$),满秩意味着行向量线性无关

坐标变换

$\mathbb R^n$的标准基向量:$\left(e_{1}, e_{2}, \ldots, e_{n}\right)$,其中

第$i$个元素是$1$。

显然我们有

$x_i$被称为在标准基下的坐标。

如果$\left(t_{1}, t_{2}, \ldots, t_{n}\right)​$是$\mathbb R^n​$下另一组基,我们有

其中$\tilde x_i​$是$x​$在基$\left(t_{1}, t_{2}, \ldots, t_{n}\right)​$下的坐标。

定义$T=\left[ \begin{array}{llll}{t_{1}} & {t_{2}} & {\cdots} & {t_{n}}\end{array}\right]​$,那么$x=T\tilde x ​$,因此

(因为$t_i$是基,所以$T$可逆)

$T^{-1}​$将$x​$标准基下的坐标转换为$t_i​$坐标,$T^{-1}​$的第$i​$行和$x​$的内积提取$x​$的$t_i ​$坐标。

考虑线性变换$y=Ax ,A\in \mathbb R^{n\times n}$,用$t_{1}, t_{2} \ldots, t_{n}$表示$x,y$:

那么

  • $A \longrightarrow T^{-1} A T$被称为相似变换

(欧几里得)范数

对于$x\in \mathbb R^n $,我们定义(欧几里得)范数为

$| x|$测量(距离原点的)矢量长度,重要性质:

  • $|\alpha x|=|\alpha||x|$
  • $|x+y| \leq|x|+|y|​$
  • $|x| \ge 0​$
  • $|x|=0 \Longleftrightarrow x=0$

RMS值和(欧几里得)距离

$x\in \mathbb R^n$的均方误差(RMS):

向量的距离定义为

内积

重要性质:

  • $\langle\alpha x, y\rangle=\alpha\langle x, y\rangle$
  • $\langle x+y, z\rangle=\langle x, z\rangle+\langle y, z\rangle$
  • $\langle x, y\rangle=\langle y, x\rangle$
  • $\langle x, x\rangle \geq 0​$
  • $\langle x, x\rangle= 0 \Longleftrightarrow x=0​$

$f(y) =\langle x,y\rangle​$是由行向量$x^T​$定义的$\mathbb R^n\to \mathbb R​$的线性函数。

Cauchy-Schwartz不等式和向量夹角

  • $x, y \in \mathbb{R}^{n},\left|x^{T} y\right| \leq|x||y|​$

  • $\mathbb R^n​$中(无符号)夹角定义为

    因此

特殊情形

  • $x,y​$同向,即(如果$x\neq 0​$)$y=\alpha x ,\alpha \ge 0 ​$:$\theta=0 ; x^{T} y=|x||y|​$
  • $x,y$反向,即(如果$x\neq 0$)$y=-\alpha x ,\alpha \ge 0 $:$\theta=\pi ; x^{T} y=-|x||y|$
  • $x,y$正交:$\theta = \pi /2,-\pi /2$;那么$x^T y=0$,用$x \perp y$表示

Lecture 4 正交向量和$QR$分解

正交向量组

向量组$u_{1}, \dots, u_{k} \in \mathbb{R}^{n}$是

  • 规范的如果$\left|u_{i}\right|=1, i=1, \ldots, k​$
  • 正交的如果$u_{i} \perp u_{j}, i\neq j$
  • 单位正交如果满足上述两个条件

用矩阵形式$U=\left[ \begin{array}{lll}{u_{1}} & {\cdots} & {u_{k}}\end{array}\right]$,单位正交意味着:

  • 正交向量组线性无关

  • 因此$u_{1}, \dots, u_{k}$是如下空间的标准正交基:

  • 如果$k<n$,那么$UU^T\neq I$

本文标题:EE263 Lecture 4 Orthonormal sets of vectors and QR factorization

文章作者:Doraemonzzz

发布时间:2019年05月20日 - 22:10:00

最后更新:2019年05月22日 - 11:39:57

原始链接:http://doraemonzzz.com/2019/05/20/EE263 Lecture 4 Orthonormal sets of vectors and QR factorization/

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