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}}$，我们将最小化残差的平方，

  $$\|r\|^{2}=x^{T} A^{T} A x-2 y^{T} A x+y^{T} y$$

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

  $$\nabla_{x}\|r\|^{2}=2 A^{T} A x-2 A^{T} y=0$$

• 这产生正规方程：

  $$A^{T} A x=A^{T} y$$

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

  $$x_{\text{ls}}=\left(A^{T} A\right)^{-1} A^{T} y$$

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

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

  $$x_{\text{ls}}=\left(A^{T} A\right)^{-1} A^{T} y=A^{-1}A^{-T}A^Ty =A^{-1}y$$

• 如果$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$（满秩，瘦矩阵）的左逆：

  $$A^{\dagger}A=\left(A^{T} A\right)^{-1} A^{T}A=I$$

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

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

$$A x_{\text{ls}} =\mathcal P_{\mathcal R(A)}(y)$$

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

  $$\mathcal P_{\mathcal R(A)}(y)= A x_{\text{ls}}=A\left(A^{T} A\right)^{-1} A^{T} y$$

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

正交准则

最优残差

$$r=A x_{\mathrm{ls}}-y=\left(A\left(A^{T} A\right)^{-1} A^{T}-I\right) y$$

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

$$\langle r, A z\rangle= y^{T}\left(A\left(A^{T} A\right)^{-1} A^{T}-I\right)^{T} A z=0$$

其中$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}$是上三角可逆矩阵

• 那么伪逆为

  $$\left(A^{T} A\right)^{-1} A^{T}=\left(R^{T} Q^{T} Q R\right)^{-1} R^{T} Q^{T}=R^{-1} Q^{T}$$

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

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

  $$A\left(A^{T} A\right)^{-1} A^{T}=A R^{-1} Q^{T}=QR R^{-1} Q^{T}=Q Q^{T}$$

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

• 完全$QR$分解：

  $$A=\left[Q_{1} Q_{2}\right] \left[ \begin{array}{c}{R_{1}} \\ {0}\end{array}\right]$$

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

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

  $$\begin{aligned} \|A x-y\|^{2} &=\left\|\left[Q_{1}\ Q_{2}\right] \left[ \begin{array}{c}{R_{1}} \\ {0}\end{array}\right] x-y \right\|^{2} \\ &=\left\|\left[Q_{1}\ Q_{2}\right]^{T}\left[Q_{1} Q_{2}\right] \left[ \begin{array}{c}{R_{1}} \\ {0}\end{array}\right] x-\left[Q_{1}\ Q_{2}\right]^{T} y \right\|^{2} \\ &=\left\| \left[ \begin{array}{c}{R_{1} x-Q_{1}^{T} y} \\ {-Q_{2}^{T} y}\end{array}\right] \right\|^{2} \\ &=\left\|R_{1} x-Q_{1}^{T} y\right\|^{2}+\left\|Q_{2}^{T} y\right\|^{2} \end{aligned}$$

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

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

  $$\begin{aligned} A x_{\mathrm{ls}}-y &=\left[Q_{1}\ Q_{2}\right] \left[ \begin{array}{c}{R_{1}} \\ {0}\end{array}\right]R_{1}^{-1} Q_{1}^{T} y -y \\ &= Q_1 Q_1^T y -\left[Q_{1}\ Q_{2}\right]\left[Q_{1}\ Q_{2}\right]^T y \\ & = Q_1 Q_1^T y - Q_1 Q_1^T y- Q_2 Q_2^T y \\ &=-Q_{2} Q_{2}^{T} y \end{aligned}$$

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

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

最小二乘估计

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

$$y=Ax+v$$

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

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

$$\|A \hat{x}-y\|$$

显然最小二乘估计为

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

BLUE性质

带有误差的线性测量：

$$y=Ax+v$$

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

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

• 线性无偏估计的误差为

  $$x-\hat{x}=x-B(A x+v)=-B v$$

  显然，我们希望$B$很“小”（以及$BA=I$）

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

  $$\sum_{i, j} B_{i j}^{2} \geq \sum_{i, j} A_{i j}^{\dagger 2}$$

  即，最小二乘法给出了最小线性无偏估计（BLUE）

例子

考虑之前的一个例子：

• 信号$u$是分段常数（每一秒），$0\le t\le 10$：

  $$u(t)=x_{j}, \quad j-1 \leq t<j, \quad j=1, \ldots, 10$$

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

  $$w(t)=\int_{0}^{t} h(t-\tau) u(\tau) d \tau$$

• 每$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$是三比特量化特征

  $$Q(a)=(1 / 4)(\text {round }(4 a+1 / 2)-1 / 2)$$

• 问题，给定$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$

最小二乘估计：

$$x_{\mathrm{ls}}=\left(A^{T} A\right)^{-1} A^{T} y$$

最后的效果如下：

RMS误差为

$$\frac{\left\|x-x_{1 \mathrm{s}}\right\|}{\sqrt{10}}=0.03$$

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

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_{1} f_{1}\left(s_{i}\right)+\cdots+x_{n} f_{n}\left(s_{i}\right) \approx g_{i}, \quad i=1, \ldots, m$$

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

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

$$\sum_{i=1}^{m}\left(x_{1} f_{1}\left(s_{i}\right)+\cdots+x_{n} f_{n}\left(s_{i}\right)-g_{i}\right)^{2}$$

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

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

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

  （假设$A$是瘦，满秩矩阵）

• 相应的函数为

  $$f_{\text { lsit }}(s)=x_{1} f_{1}(s)+\cdots+x_{n} f_{n}(s) |$$

• 应用：

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

最小二乘多项式拟合

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

$$p(t)=a_{0}+a_{1} t+\cdots+a_{n-1} t^{n-1}$$

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

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

  $$A= \left[ \begin{matrix} 1 & t_{1} & {t_{1}^{2}} & {\cdots} & t_{1}^{n-1} \\ 1 & t_{2} & {t_{2}^{2}} & {\cdots} & t_{2}^{n-1}\\ & \vdots & & &\vdots \\ 1 & t_{m} & {t_{m}^{2}} & {\cdots} & t_{m}^{n-1} \end{matrix} \right]$$

  该矩阵被称为范德蒙矩阵，假设对于$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​$满秩