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)=\left\{x \in \mathbb{R}^{n} | A x=0\right\}$$

• $\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)=\left\{A x | x \in \mathbb{R}^{n}\right\} \subseteq \mathbb{R}^{m}$$

$\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}$表示，并且

  $$A A^{-1}=A^{-1} A=I$$

• $\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$，我们得到

  $$y=\sum_{i=1}^{n}\left(\tilde{b}_{i}^{T} y\right) a_{i}$$

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

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

矩阵的秩

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

$$\operatorname{rank}(A)=\operatorname{dim} \mathcal{R}(A)$$

有如下性质：

• $\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)$，其中

$$e_{i}=\left[ \begin{array}{c}{0} \\ {\vdots} \\ {1} \\ {\vdots} \\ {0}\end{array}\right]$$

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

显然我们有

$$x=x_{1} e_{1}+x_{2} e_{2}+\cdots+x_{n} e_{n}$$

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

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

$$x=\tilde{x}_{1} t_{1}+\tilde{x}_{2} t_{2}+\cdots+\tilde{x}_{n} t_{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 ​$，因此

$$\tilde{x}=T^{-1} 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$：

$$x=T \tilde{x}, \quad y=T \tilde{y}$$

那么

$$\tilde{y}=\left(T^{-1} A T\right) \tilde{x}$$

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

(欧几里得)范数

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

$$\|x\|=\sqrt{x_{1}^{2}+x_{2}^{2}+\cdots+x_{n}^{2}}=\sqrt{x^{T} x}$$

$| 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）：

$$\operatorname{rms}(x)=\left(\frac{1}{n} \sum_{i=1}^{n} x_{i}^{2}\right)^{1 / 2}=\frac{\|x\|}{\sqrt{n}}$$

向量的距离定义为

$$\operatorname{dist}(x, y)=\|x-y\|$$

内积

$$\langle x, y\rangle := x_{1} y_{1}+x_{2} y_{2}+\cdots+x_{n} y_{n}=x^{T} y$$

重要性质：

• $\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​$中（无符号）夹角定义为

  $$\theta=\angle(x, y)=\cos ^{-1} \frac{x^{T} y}{\|x\|\|y\|}$$

  因此

  $$x^{T} y=\|x\|\|y\| \cos \theta$$

特殊情形

• $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^{T} U=I_{k}$$

• 正交向量组线性无关

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

  $$\operatorname{span}\left(u_{1}, \ldots, u_{k}\right)=\mathcal{R}(U)$$

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