EE263 Lecture 6 Least-squares applications

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

这次回顾第六讲,这一讲介绍最小二乘法以及其应用。

几何解释

$A x_{\text{ls}}​$是$\mathcal{R}(A)​$中最接近$y​$的点($A x_{\text{ls}}​$是$y​$在$\mathcal{R}(A)​$上的投影):

最小二乘(近似)求解

  • 假设$A$是满秩,瘦矩阵

  • 为了找到$x_{\text{ls}}$,我们将最小化残差的平方,

  • 令关于$x$的梯度为$0$得到:

  • 这产生正规方程:

  • 假设$A^TA$可逆,那么我们有

  • 从上式不难看出$x_{\text{ls}}$是$y$的线性函数

  • 如果$A$是方阵并且可逆,那么

  • 如果$y \in \mathcal{R}(A)$,那么$x_{\mathrm{ls}}$求解了方程$y=Ax_{\mathrm{ls}}$

  • $A^{\dagger}=\left(A^{T} A\right)^{-1} A^{T}​$被称为$A​$的伪逆矩阵

  • $A^{\dagger}$是$A$(满秩,瘦矩阵)的左逆:

$\mathcal R(A)$上的投影

$A x_{\text{ls}}​$是$\mathcal R(A)​$上最靠近$y​$的点,即是$y​$在$\mathcal R(A)​$上的投影:

  • 投影函数$\mathcal P_{\mathcal R(A)}$是线性的,由下式给出

  • $A\left(A^{T} A\right)^{-1} A^{T} $被称为投影矩阵

正交准则

最优残差

和$\mathcal R(A)​$正交:

其中$z\in \mathbb R^n$。

通过$QR$分解得到最小二乘法

  • $A\in \mathbb R^{m\times n}​$是瘦,满秩矩阵

  • 将$A$分解为$A=QR$,其中$Q^{T} Q=I_{n}$,$R \in \mathbb{R}^{n \times n}$是上三角可逆矩阵

  • 那么伪逆为

    所以$x_{\mathrm{ls}}=R^{-1} Q^{T} y$

  • $\mathcal R(A)$上的投影矩阵为

通过完全$QR$分解得到最小二乘法

  • 完全$QR$分解:

    其中$\left[Q_{1} Q_{2}\right] \in \mathbb{R}^{m \times m}$是正交矩阵,$R_{1} \in \mathbb{R}^{n \times n}​$是上三角可逆矩阵

  • 乘以正交矩阵不改变范数,所以

  • 很显然要使得上式最小,显然要取$x_{\mathrm{ls}}=R_{1}^{-1} Q_{1}^{T} y$

  • 最优$x$对应的残差为

  • $Q_1 Q_1^T ​$给出了到$\mathcal R(A)​$上的投影

  • $Q_2Q_2^T$给出了到$\mathcal{R}(A)^{\perp}​$上的投影

最小二乘估计

在反演,估计和重建问题中的许多问题的形式为

  • $x$是我们需要估计或者重建的量
  • $y$是传感器的测量值
  • $v$是未知的噪声或测量误差(假设很小)
  • $A$的第$i$行描述了第$i​$个传感器

最小二乘估计:选择$\hat{x}​$最小化

显然最小二乘估计为

BLUE性质

带有误差的线性测量:

其中$A$是瘦,满秩矩阵,考虑形如$\hat{x}=B y$的线性估计:

  • 称该估计式无偏的,如果$v=0$时有$\hat x = x$,这等价于$BA=I$,即$B$是$A$的左逆

  • 线性无偏估计的误差为

    显然,我们希望$B$很“小”(以及$BA=I$)

  • 实际上$A^{\dagger}=\left(A^{T} A\right)^{-1} A^{T}$是$A$的最小左逆,即对于任意满足$BA=I$的$B$,我们有

    即,最小二乘法给出了最小线性无偏估计(BLUE)

例子

考虑之前的一个例子:

  • 信号$u$是分段常数(每一秒),$0\le t\le 10$:

  • 根据带有脉冲响应$h(t)$的系统过滤:

  • 每$10\text{Hz}$采样:$\tilde{y}_{i}=w(0.1 i), i=1, \ldots, 100$

  • $3$比特量化:$y_{i}=Q\left(\tilde{y}_{i}\right), i=1, \dots, 100$,其中$Q$是三比特量化特征

  • 问题,给定$y \in \mathbb{R}^{100}$,估计$x\in \mathbb R^{10}$

实例:

我们有$y=Ax+v$,其中

  • $A\in \mathbb R^{100\times 10}$由$A_{i j}=\int_{j-1}^{j} h(0.1 i-\tau) d \tau$给出
  • $v\in \mathbb R^{100}$是量化误差:$v_{i}=Q\left(\tilde{y}_{i}\right)-\tilde{y}_{i}$,所以$\left|v_{i}\right| \leq 0.125$

最小二乘估计:

最后的效果如下:

RMS误差为

这里老师表示最难的部分是给该问题建立模型,而不是求解最小二乘本身。

Lecture 6 最小二乘的应用

最小二乘数据拟合

我们给定:

  • 函数$f_{1}, \dots, f_{n} : S \rightarrow \mathbb{R}$,这被称为回归量或基函数
  • 数据或测量$\left(s_{i}, g_{i}\right), i=1, \dots, m$,通常$s_i \in S, m\gg n$

问题:找到系数$x_{1}, \dots, x_{n} \in \mathbb{R}$,使得

即找到函数的线性组合来拟合数据。

最小二乘拟合:选择$x​$以最小化总平方拟合误差:

  • 使用矩阵记号,总平方拟合误差为$|A x-g|^{2}$,其中$A_{i j}=f_{j}\left(s_{i}\right)$

  • 因此,最小二乘估计由下式给出

    (假设$A$是瘦,满秩矩阵)

  • 相应的函数为

  • 应用:

    • 插值,外推,数据平滑
    • 推导简单的近似数据模型

最小二乘多项式拟合

问题:用次数小于$n$的多项式拟合数据$\left(t_{i}, y_{i}\right), i=1, \dots, m$

  • 基函数$f_j(t)=t^{j-1},j=1,\ldots ,n$

  • 矩阵$A$的形式为$A_{i j}=t_{i}^{j-1}​$

    该矩阵被称为范德蒙矩阵,假设对于$k\neq l$,$t_k\neq t_l$,以及$m\ge n$,那么$A$是满秩矩阵:

    • 假设$Aa=0$
    • 相应的多项式$p(t)=a_{0}+\cdots+a_{n-1} t^{n-1}$满足$p(t_i)= y_i$
    • $A$的列线性无关,即$A​$满秩

本文标题:EE263 Lecture 6 Least-squares applications

文章作者:Doraemonzzz

发布时间:2019年05月26日 - 12:30:00

最后更新:2019年05月29日 - 11:49:42

原始链接:http://doraemonzzz.com/2019/05/26/EE263 Lecture 6 Least-squares applications/

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