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$

因此我们有

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

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

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

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

其中

被称为$A$的条件数。

从上述不等式我们可得:

或者,用比特表示精确度:

我们说

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

(小和大的定义和应用有关)

低秩近似

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

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

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

  • 因此$|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$的近似

证明:假设

那么

另一方面,我们有

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

从而

计算范数可得

因此

和奇异性的距离

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

即,和秩为$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}$的奇异值为

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

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

那么$\sigma_{i} u_{i} v_{i}^{T} x,i=5,\ldots ,30$都比噪声$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$,

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

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

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

离散时间LDS的可达性

考虑DT系统

我们有

其中

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

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

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

所以

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

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

本文标题:EE263 Lecture 18 SVD Applications

文章作者:Doraemonzzz

发布时间:2019年07月06日 - 23:14:00

最后更新:2019年07月11日 - 12:29:31

原始链接:http://doraemonzzz.com/2019/07/06/EE263 Lecture 18 SVD Applications/

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