凸优化第六章逼近与拟合 6.3正则化逼近

6.3正则化逼近

双准则式
正则化
例子

双准则式

目标是寻找向量x使其较小，而且使得残差Ax-b也较小。即 $minimize \, \, (\begin{Vmatrix} Ax-b\end{Vmatrix},\begin{Vmatrix} x \end{Vmatrix})$

其中 $A \in R^{m \times n}$ ，两个范数分别在 $R^m,R^n$ 上。

解释：

（1）估计解释：线性y=Ax+v,x是估计值，v是噪声，y是测量值，先验知识为x很小，目标就是在y=b的时候照的最好的估计值x。

（2）最优设计：x越小越偏析越高效，模型y=Ax只对较小的x有效。

（3）鲁棒性解释：目标函数为Ax-b，当A有误差e时，目标变成了(A+e)x-b=Ax-b+ex，x越小对结果造成的误差越小。

正则化

最常见的正则化的形式是极小化目标加权和，即 $minimize \, \, \begin{Vmatrix}Ax-b \end{Vmatrix}+\gamma \begin{Vmatrix}x \end{Vmatrix}$ ， $\gamma >0$ 。

或者 $minimize \, \, \begin{Vmatrix}Ax-b \end{Vmatrix}^2+\delta \begin{Vmatrix}x \end{Vmatrix}^2$ ， $\delta >0$ 。

Tikhonov正则化

$minimize \, \, \begin{Vmatrix} Ax-b\end{Vmatrix}_2^2+\delta \begin{Vmatrix} x \end{Vmatrix}_2^2$

这个正则化利用Euclid范数，得到一个二次凸优化问题。

此问题也等价于一个最小二乘问题：

$minimize \, \, \begin{Vmatrix}\begin{bmatrix} A\\ \delta I \end{bmatrix}x- \begin{bmatrix} b\\ 0 \end{bmatrix}\end{Vmatrix}_2^2=\begin{Vmatrix}\begin{bmatrix} Ax-b\\ \delta Ix \end{bmatrix}\end{Vmatrix}_2^2$

$\begin{Vmatrix} Ax-b\end{Vmatrix}_2^2+\delta \begin{Vmatrix} x \end{Vmatrix}_2^2=x^TA^TAx-2b^TAx+b^Tb+\delta x^Tx\\ =x^T(A^TA+\delta I)x-2b^TAx+b^Tb$

目标函数对x求导，得到 $\bigtriangledown _x=2(A^T+\delta I)x-2A^Tb$ ，令其为0，得到 $x=1/2(A^TA+\delta I)^{-1}A^Tb$ 。

最优输入设计

输入是u(t)，输出是y(t)， $y(t)=\sum_{\tau =0}^th(\tau )u(t-\tau),t=0,1,\cdots N$

目标是选择输入序列以达到一些目标：

跟踪输出：使输出跟目标输出一致，用二次函数表示输出误差： $J_{track}=\sm_t^N(y(t)-y_{des}(t))^2$ ，其中y(t)表示实际输出， $y_{des}(t)$ 表示目标输出。
小的输入：希望输入不能太大，用二次函数度量输入的幅值： $J_{mag}=\frac{1}{N+1}\sum^N_{t=0}u(t)^2$
较小的输入变化：希望输入不应该变化太快，依旧用二次函数度量： $J_{der}=\frac{1}{N}\sum _{t=0}^{N-1}(u(t+1)-u(t))^2$

正则化形式：

$minimize \, \, J_{track}+\delta J_{der}+\eta J_{mag}$

$\delta >0,\eta >0$

下图显示了对不同大小的 $\delta,\eta$ 得到的输出和输出图像：

最上面的图是对应 $\delta =0,\eta$ 具有很小的值，可以看出输入较大，输出具有较小的误差。

中间的图对应 $\delta =0,\eta$ 具有比上图大的值，可以看出，输入得值相比于上图较小，具有一定的误差。

最下面的图对应较大的 $\delta$ ，输入的值较小，而且变化较快，具有一定的误差。

信号重构

给定受污染的信号 $x_{cor}$ 的情况下，构建对原始信号x的估计值 $\hat{x}$ ，这一过程尘给信号重构。多数重构方法最终视作将某些光滑运算作用在 $x_{cor}$ 上以得到 $\hat{x}$ ，因此也称为光滑化。

$minimize \, \, (\begin{Vmatrix} \hat {x}-x_{cor}\end{Vmatrix}_2,\phi (\hat{x}))$

其中 $\hat{x}$ 是变量， $x_{cor}$ 是问题参数，函数 $\phi:R^n \rightarrow R$ 是凸的，称为正则化函数或光滑目标。

重构问题是在2范数下寻求接近被污染信号并且光滑的信号。

二次光滑：

$\phi_{quad}(x)=\sum_{i=1}^{n-1}(x_{i+1}-x_i)^2$

总构差重构：

$\phi_{tv}(x)=\sum_{i=1}^{n-1}|x_{i+1}-x_i|$

例子：

左侧上下两个图分别是估计值 $\hat{x}$ 和受污染信号 $x_{cor}$ ，右侧图从下往上 $\begin{Vmatrix} \hat{x}-x_{cor}\end{Vmatrix}_2$ 值由小到大， $\phi_{quad}(\hat{x})$ 光滑后的输入信号。可以看出 $\begin{Vmatrix} \hat{x}-x_{cor}\end{Vmatrix}_2$ 较小的时候，输入信号不够光滑，保留了太多噪声， $\begin{Vmatrix} \hat{x}-x_{cor}\end{Vmatrix}_2$ 适中的时候可以很好地保留信号变化信息。当 $\begin{Vmatrix} \hat{x}-x_{cor}\end{Vmatrix}_2$ 较大时，输入信号过于光滑，失去了信号的变化信息。

左侧上下两个图分别是估计值 $\hat{x}$ 和受污染信号 $x_{cor}$ ，右侧图从下往上 $\begin{Vmatrix} \hat{x}-x_{cor}\end{Vmatrix}_2$ 值由大到小， $\phi_{tv}(\hat{x})$ 光滑后的输入信号。可以看出 $\begin{Vmatrix} \hat{x}-x_{cor}\end{Vmatrix}_2$ 较小的时候，输入信号不够光滑，保留了太多噪声， $\begin{Vmatrix} \hat{x}-x_{cor}\end{Vmatrix}_2$ 适中的时候可以很好地保留信号变化信息。当 $\begin{Vmatrix} \hat{x}-x_{cor}\end{Vmatrix}_2$ 较大时，输入信号过于光滑，失去了信号的变化信息，此时，因为 $\phi_{tv}(\hat{x})=\sum_{i=1}^{n-1}|x_{i+1}-x_i|$ ，会使相邻的两个信号非常接近，所以会导致输入图像变成了分段线性函数，在有些区域会保持常量。