EE263 Lecture 8 Least-norm solutions of undetermined equations

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

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

加权目标

此时我们的目标函数为

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

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

最小化加权目标

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

其中

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

正规化最小二乘

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

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

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

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

非线性最小二乘

非线性最小二乘(NLLS)问题:找到$x\in \mathbb R^n$最小化

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

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

高斯-牛顿法求解NLLS

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

高斯牛顿法:

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

高斯牛顿法的细节

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

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

  • 将线性近似写成:

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

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

  • 重复上述步骤直至收敛(不能保证收敛)

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

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

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

欠定线性方程

我们考虑

其中$A\in \mathbb R^{m\times n}$是胖矩阵($m<n$),即

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

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

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

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

本文标题:EE263 Lecture 8 Least-norm solutions of undetermined equations

文章作者:Doraemonzzz

发布时间:2019年05月31日 - 22:50:00

最后更新:2019年06月05日 - 12:37:02

原始链接:http://doraemonzzz.com/2019/05/31/EE263 Lecture 8 Least-norm solutions of undetermined equations/

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