EE263 Lecture 8 Least-norm solutions of undetermined equations

距离上次更新已经 2127 天了，文章内容可能已经过时。

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

此时我们的目标函数为

J_{1} + μ J_{2} = ‖ A x - y ‖^{2} + μ ‖ F x - g ‖^{2}

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

\begin{aligned} ‖ A x - y ‖^{2} + μ ‖ F x - g ‖^{2} & = {‖ [\begin{array}{c} A \\ \sqrt{μ} F \end{array}] x - [\begin{array}{c} y \\ \sqrt{μ} g \end{array}] ‖}^{2} \\ = ‖ \tilde{A} x - \tilde{y} ‖^{2} \end{aligned}

其中

\tilde{A} = [\begin{matrix} A \\ \sqrt{μ} F \end{matrix}], \tilde{y} = [\begin{matrix} y \\ \sqrt{μ} g \end{matrix}]

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

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

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

J_{1} = ‖ A x - y ‖^{2}, J_{2} = ‖ x ‖^{2}

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

x = {(A^{T} A + μ I)}^{- 1} A^{T} y

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

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

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

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

高斯牛顿法：

在当前的 $x^{(k)}$ 附近线性化 $r$ ：
$r (x) \approx r (x^{(k)}) + D r (x^{(k)}) (x - x^{(k)})$
其中 $D r$ 为雅克比矩阵： $(D r)_{i j} = \partial r_{i} / \partial x_{j}$
将线性近似写成：
$\begin{matrix} r (x^{(k)}) + D r (x^{(k)}) (x - x^{(k)}) = A^{(k)} x - b^{(k)} \\ A^{(k)} = D r (x^{(k)}), b^{(k)} = D r (x^{(k)}) x^{(k)} - r (x^{(k)}) \end{matrix}$
在第 $k$ 轮，我们将NLLS问题近似为线性最小二乘问题：
$‖ r (x) ‖^{2} \approx {‖ A^{(k)} x - b^{(k)} ‖}^{2}$
下一轮求解上述线性最小二乘问题：
$x^{(k + 1)} = {(A^{(k) T} A^{(k)})}^{- 1} A^{(k) T} b^{(k)}$
重复上述步骤直至收敛（不能保证收敛）

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

{‖ A^{(k)} x - b^{(k)} ‖}^{2} + μ {‖ x - x^{(k)} ‖}^{2}

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

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

我们考虑

y = A x

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

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

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

其中 $x_{p}$ 是任意特解，即，

A x_{p} = y