EE263 Lecture 8 Least-norm solutions of undetermined equations

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

这次回顾第八讲，这一讲结束正规化最小二乘法和牛顿高斯法，介绍了欠定方程。

加权目标

此时我们的目标函数为

$$J_{1}+\mu J_{2}=\|A x-y\|^{2}+\mu\|F x-g\|^{2}$$

• 参数$\mu \ge 0$给出了$J_1,J_2$的相对权重
• 加权和为常数的点，即$J_1 +\mu J_2=\alpha$，对应了$(J_2,J_1)$图上斜率为$-\mu​$的直线

• 从上图中不难看出$x^{(2)}$最小化加权和
• 将$\mu$从$0$变化到$+\infty$，可以扫过整个最优权衡曲线

最小化加权目标

可以将加权和表达为常规的最小二乘目标函数：

$$\begin{aligned} \|A x-y\|^{2}+\mu\|F x-g\|^{2} &=\left\| \left[ \begin{array}{c}{A} \\ {\sqrt{\mu} F}\end{array}\right] x-\left[ \begin{array}{c}{y} \\ {\sqrt{\mu} g}\end{array}\right] \right\|^{2} \\ &=\|\tilde{A} x-\tilde{y}\|^{2} \end{aligned}$$

其中

$$\tilde{A}=\left[ \begin{array}{c}{A} \\ {\sqrt{\mu} F}\end{array}\right], \quad \tilde{y}=\left[ \begin{array}{c}{y} \\ {\sqrt{\mu} g}\end{array}\right]$$

假设$\tilde A$满秩，那么问题的解为

$$\begin{aligned} x &=\left(\tilde{A}^{T} \tilde{A}\right)^{-1} \tilde{A}^{T} \tilde{y} \\ &=\left(A^{T} A+\mu F^{T} F\right)^{-1}\left(A^{T} y+\mu F^{T} g\right) \end{aligned}$$

正规化最小二乘

当$F=I,g=0$时，目标函数为

$$J_{1}=\|A x-y\|^{2}, \quad J_{2}=\|x\|^{2}$$

最小化加权和目标函数，我们得到

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

上式被称为$Ax\approx y$的加权最小二乘（近似）解。

• 这也被称为Tychonov正则项
• 对于$\mu >0 $，由于$A^{T} A+\mu I$正定，所以上述解对任意$A$成立

非线性最小二乘

非线性最小二乘（NLLS）问题：找到$x\in \mathbb R^n$最小化

$$\|r(x)\|^{2}=\sum_{i=1}^{m} r_{i}(x)^{2}$$

其中$r: \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$

• $r(x)$是残差向量
• 如果$r(x)=Ax-y$，上述问题简化为（线性）回归

高斯-牛顿法求解NLLS

• 通常，很难求解非线性最小二乘（NLLS）问题
• 但是有很多好的启发式算法计算局部最优解

高斯牛顿法：

• 给定$x$的初始猜测值
• 重复
  • 在当前值附近线性化$r$
  • 新的值为使用线性化的$r$的最小二乘问题的解
• 直至收敛

高斯牛顿法的细节

• 在当前的$x^{(k)}$附近线性化$r$：

  $$r(x) \approx r\left(x^{(k)}\right)+{Dr}(x^{(k)})\left(x-x^{(k)}\right)$$

  其中$Dr$为雅克比矩阵：$(D r)_{i j}=\partial r_{i} / \partial x_{j}$

• 将线性近似写成：

  $$\begin{array}{c}{r\left(x^{(k)}\right)+{Dr}\left(x^{(k)}\right)\left(x-x^{(k)}\right)=A^{(k)} x-b^{(k)}} \\ {A^{(k)}={Dr}\left(x^{(k)}\right), \quad b^{(k)}={Dr}\left(x^{(k)}\right) x^{(k)}-r\left(x^{(k)}\right)}\end{array}$$

• 在第$k$轮，我们将NLLS问题近似为线性最小二乘问题：

  $$\|r(x)\|^{2} \approx\left\|A^{(k)} x-b^{(k)}\right\|^{2}$$

• 下一轮求解上述线性最小二乘问题：

  $$x^{(k+1)}=\left(A^{(k) T} A^{(k)}\right)^{-1} A^{(k) T} b^{(k)}$$

• 重复上述步骤直至收敛（不能保证收敛）

由于泰勒展开只有局部近似性，所以实际中我们常常增加正则项，求解如下问题：

$$\left\|A^{(k)} x-b^{(k)}\right\|^{2}+\mu\left\|x-x^{(k)}\right\|^{2}$$

这样下一轮迭代的结果不会和上一轮距离太远（因此，线性化的模型仍然相当准确）

Lecture 8 欠定方程的最小范数解

欠定线性方程

我们考虑

$$y=Ax$$

其中$A\in \mathbb R^{m\times n}$是胖矩阵（$m<n$），即

• 未知数的数量多于方程数量
• $x$是未指定的，即，许多$x$的选择导致相同的$y$

我们假设$A$满秩（秩为$m$），所以对每个$y\in \mathbb R^m$，存在解，并且解的形式为

$$\{x | A x=y\}=\left\{x_{p}+z | z \in \mathcal{N}(A)\right\}$$

其中$x_p$是任意特解，即，

$$Ax_p =y$$

• $z$表示解的可选项
• 解有$\text{dim} \mathcal N(A)= n - m$的“自由度”
• 可以选择$z$以满足其他要求或进行优化