EE263 Lecture 18 SVD Applications

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

这次回顾第十八讲，这一讲介绍了SVD的应用。

线性方程组对于数据误差的敏感度

考虑$y=A x$，$A \in \mathbb{R}^{n \times n}$可逆；所以$x=A^{-1} y$

假设$y$有误差或噪声，即$y$变成$y+\delta y$

那么$x$变成$x+\delta x$，其中$\delta x=A^{-1} \delta y$

因此我们有

$$\|\delta x\|=\left\|A^{-1} \delta y\right\| \le\left\|A^{-1}\right\|\|\delta y\|$$

如果$\left|A^{-1}\right|$很大，

• $y$的小误差会产生$x$的大误差
• 给定$y$，无法求解出很小误差的$x$
• 因此，在实际中可以认为$A$是奇异的

更精细的分析使用$x,y$的相对误差而不是绝对误差

因为$y=Ax$，我们有$|y| \leq|A||x|$，因此

$$\frac{\|\delta x\|}{\|x\|} \le \left\|A^{-1}\right\|\|\delta y\| \frac{\| A\|}{\| y\|}= \|A\|\|A^{-1}\| \frac{\|\delta y\|}{\|y\|}$$

其中

$$\kappa(A)=\|A\|\|A^{-1}\|=\sigma_{\max }(A) / \sigma_{\min }(A)$$

被称为$A$的条件数。

从上述不等式我们可得：

$$x的相对误差\le 条件数 . y的相对误差$$

或者，用比特表示精确度：

$$\# \text { bits accuracy in solution } \approx \# \text { bits accuracy in data }-\log _{2} \kappa$$

我们说

• $A$是well conditioned如果$\kappa$很小
• $A$是poorly conditioned如果$\kappa$很大

（小和大的定义和应用有关）

低秩近似

假设$A \in \mathbb{R}^{m \times n}, {\operatorname {Rank}}(A)=r$，SVD分解为

$$A=U \Sigma V^{T}=\sum_{i=1}^{r} \sigma_{i} u_{i} v_{i}^{T}$$

我们寻找矩阵$\hat A,\operatorname{Rank}(\hat{A}) \leq p<r$，使得$\hat{A} \approx A$（$|A-\hat{A}|$最小化）

解：秩为$p$的最佳近似为

$$\hat{A}=\sum_{i=1}^{p} \sigma_{i} u_{i} v_{i}^{T}$$

• 因此$|A-\hat{A}|=\left|\sum_{i=p+1}^{r} \sigma_{i} u_{i} v_{i}^{T}\right|=\sigma_{p+1}$
• 解释：$u_i v_i^T$按照重要度排序；根据$p$选择秩为$p$的近似

证明：假设

$$\operatorname{Rank}(B) \leq p$$

那么

$$\operatorname{dim} \mathcal{N}(B) \geq n-p$$

另一方面，我们有

$$\operatorname{dimspan}\left\{v_{1}, \ldots, v_{p+1}\right\}=p+1$$

所以两个子空间存在交集，即，存在公共向量$z \in \mathbb{R}^{n}$，使得

$$B z=0, \qquad z \in \operatorname{span}\left\{v_{1}, \ldots, v_{p+1}\right\}$$

从而

$$(A-B) z=A z=\sum_{i=1}^{p+1} \sigma_{i} u_{i} v_{i}^{T} z$$

计算范数可得

$$\|(A-B) z\|^{2}=\sum_{i=1}^{p+1} \sigma_{i}^{2}\left(v_{i}^{T} z\right)^{2} \geq \sigma_{p+1}^{2}\|z\|^{2}$$

因此

$$\|A-B\| \geq \sigma_{p+1}=\|A-\hat{A}\|$$

和奇异性的距离

另一种对$\sigma_i$的解释：

$$\sigma_{i}=\min \{\|A-B\| | \operatorname{Rank}(B) \leq i-1\}$$

即，和秩为$i-1$的矩阵的最近距离（用矩阵范数度量）

例如，如果$A \in \mathbb{R}^{n \times n}, \sigma_{n}=\sigma_{\min }$为和奇异矩阵的最近距离

因此，$\sigma_{\min }$很小意味着$A$和奇异矩阵很接近

应用：模型化简

假设$y=A x+v$，其中

• $A \in \mathbb{R}^{100 \times 30}$的奇异值为

  $$10,7,2,0.5,0.01, \ldots, 0.0001$$

• $| x|$的阶数为$1$

• 未知误差或噪声$v$的范数的阶为$0.1$

那么$\sigma_{i} u_{i} v_{i}^{T} x,i=5,\ldots ,30$都比噪声$v$小，得到如下简化模型：

$$y=\sum_{i=1}^{4} \sigma_{i} u_{i} v_{i}^{T} x+v$$

Lecture 18 可控性和状态转移

状态转移

考虑$\dot{x}=A x+B u$或$x(t+1)=A x(t)+B u(t)$在时间区间$\left[t_{i}, t_{f}\right]$

我们说输入$u :\left[t_{i}, t_{f}\right] \rightarrow \mathbb{R}^{m}$将状态$x(t_i)$转移到$x(t_f)$（在时间间隔$\left[t_{i}, t_{f}\right] $）

（角标代表初始和结束）

问题：

• $x(t_i)$在$t=t_f$可以被转移到哪？
• $x(t_i)$会以多快的速度转移到$x_{\text {target}}$？
• 如何找到$u$，将$x(t_i)$转移到$x(t_f)$
• 我们如何找到“小”或“高效”的$u$将$x(t_i)$转移到$x(t_f)$

可达性

考虑从$x(0)=0$到$x(t)$的状态转移

我们称$x(t)$是可达的（在$t$秒或$t$时刻）

我们定义$\mathcal{R}_{t} \subseteq \mathbb{R}^{n}$为$t$秒或$t$时刻可达的点，对于CT系统$\dot{x}=A x+B u$，

$$\mathcal{R}_{t}=\left\{\int_{0}^{t} e^{(t-\tau) A} B u(\tau) d \tau\ \Big| u :[0, t] \rightarrow \mathbb{R}^{m}\right\}$$

对于DT系统$x(t+1)=A x(t)+B u(t)$，

$$\mathcal{R}_{t}=\left\{\sum_{\tau=0}^{t-1} A^{t-1-\tau} B u(\tau) \Big| u(t) \in \mathbb{R}^{m}\right\}$$

• $\mathcal{R}_{t}$为$\mathbb R^n$的子空间
• 如果$t\le s$，那么$\mathcal{R}_{t} \subseteq \mathcal{R}_{s}$

我们定义可达集$\mathcal R$为在某个时刻$t$可达的点集全体：

$$\mathcal{R}=\bigcup_{t \geq 0} \mathcal{R}_{t}$$

离散时间LDS的可达性

考虑DT系统

$$x(t+1)=A x(t)+B u(t), x(t) \in \mathbb{R}^{n}$$

我们有

$$x(t)=\mathcal{C}_{t}\left[\begin{array}{c}{u(t-1)} \\ {\vdots} \\ {u(0)}\end{array}\right]$$

其中

$$\mathcal{C}_{t}=\left[\begin{array}{llll}{B} & {A B} & {\cdots} & {A^{t-1} B}\end{array}\right]$$

所以在$t$时刻的可达集为

$$\mathcal{R}_{t}=\operatorname{range}\left(\mathcal{C}_{t}\right)$$

根据C-H定理，我们可以将$A^k ,k\ge n$表达为$A^{0}, \ldots, A^{n-1}$的线性组合

因此，对于$t\ge n$，我们有

$$\operatorname{range}\left(\mathcal{C}_{t}\right)=\operatorname{range}\left(\mathcal{C}_{n}\right)$$

所以

$$\mathcal{R}_{t}=\left\{\begin{array}{ll}{\operatorname{range}\left(\mathcal{C}_{t}\right)} & {t<n} \\ {\operatorname{range}(\mathcal{C})} & {t \geq n}\end{array}\right.$$

其中$\mathcal C=\mathcal C_n$被称为可控性矩阵

• 任何可达的状态可以在$t=n$时刻到达
• 可达的集合为$\mathcal{R}=\operatorname{range}(\mathcal{C})$