Chapter 6. Norm Approximation Notes

1. 范数逼近问题

最简单的范数逼近问题具有如下形式:

minimize ∥Ax−b∥

其中A∈Rm×和b∈Rm是问题的数据，x∈Rn是参数，∥.∥是Rm上的一种范数，如1范数，l1,2范数,l2和最大范数\nsi等

上述范数逼近问题是一个可解的凸优化问题/或者转化为对偶问题之后，对偶问题是凸优化问题,且对偶问题与原问题的对偶间隙为0.例如l1不是凸优化问题，但是其对偶问题是凸优化问题.

逼近的回归解释
将Ax展开为:

Ax=x1a1+...+xnan

可以看出，范数逼近问题的目标是用A的列的线性组合，列的权重有x给定，来拟合b. 其损失大小有∥.∥度量.
逼近的估计解释

y=Ax+v

v为测量误差，

x=argminz∥Az−y∥
逼近的几何解释
考虑子空间A=R(A)⊆Rm和一个点b∈Rm.A中与点b距离最近的点是b在A中的投影u:
minimize∥u−b∥subjext tou∈A
将R(A)中的元素参数化为u=Ax,可以看出范数问题的解等价于计算投影点u.

加权范数逼近问题
对标准范数逼近问题拓展:
minimize∥W(Ax−b)∥
其中W∈Rm×m,称之为权矩阵,通常是对角的. 这时，权矩阵给出了对残差向量r=Ax−b的各分量之间不同的相对重视程度.

∥Wz∥通常用符号∥z∥W表示.

最小二乘逼近问题
当标准逼近问题的范数采用Euclid或者l2−范数时，问题具体化为最小二乘逼近问题:

minimize∥Ax−b∥=r21+r22+...+r2m

该目标函数为残差的平方和. 将该问题展开成为凸二次优化问题:

f(x)=xTATAx−2bTAx+bTb

根据凸优化问题的一阶条件:

▽f(x)=2ATAx−2ATb=0

即x满足正规方程

2ATAx=2ATb

因为我们假设A的列向量是独立的，因此最小二乘逼近问题总有唯一解:x=(ATA)−1ATb
Chebyshev/ 极小极大问题
当标准逼近问题的范数采用l2−范数时，范数逼近问题具体化为:

minimize∥Ax−b∥⋈=max{|r1|,...,|rm|}

该问题成为Chebyshev逼近问题或者极小极大问题.
通常，可以将该问题转化为上镜图形式，得到如下线性规划问题:

minimize tsubject to −t1⪯Ax−b⪯t1
残差绝对值之和逼近问题
当标准逼近问题的范数采用l1−范数时，范数逼近问题具体化为:
minimize∥Ax−b∥=|r1|+...+|rm|
如同Chebyshev问题，该问题可以转化为线性规划:
minimize 1Ttsubject to −t⪯Ax−b⪯t

罚函数逼近问题形式如下:

minimize ψ(r1)+...+ψ(rm)subject to r=Ax−b

ψ:R→R成为残差罚函数. 设ψ为凸函数，则该问题为凸优化问题.

一些常见的罚函数及其逼近问题:

带有死区的线性罚函数(死区宽度为a > 0):
ψ(u)={0|u|−a{|u| \le a} {|u| \gt a}
带有死区的线性函数对于小于a的残差不进行惩罚.
对数障碍罚函数(极限为a > 0):
公式无法显示...
图片直观显示:

鲁棒最小二乘\Huber罚函数:

公式无法显示...

图片直观显示:
Alt text

More penalty function:
Alt text

The Figure below shows the contours of the different regularization terms in the parameter space:
Alt text

minimize ∥x∥subject to Ax=b

此问题的解为Ax=b的最小范数解. 如果Ax = b 有解，那么这样的解总是存在的. 该问题同样可以转化为凸优化问题来解.

设x0为Ax=b的一个解，另Z∈Rn×k的列为A的零空间的基.因此Ax=b的通解可以表示为x0+Zu,其中u∈Rk 则，最小范数问题可以重构为标准范数逼近问题.

minimize ∥x0+Zu∥

问题的可行域{x|Ax=b}是仿射的,目标函数是x和0在范数∥.∥度量下的距离∥x−0∥. 最小范数问题是在仿射集合中寻找距离0最近的点,即求解0向仿射集合{x|Ax=b}的投影.

双准则式子如下定义，该式子是向量凸优化问题的特例，具体见Chapter 4的正常锥和向量优化部分.

minimize(关于R2+) (||Ax−b||,||x||)

上述问题的一个常用标准表量化方法是正则化，得到极小化目标函数的加权值:

minimize ||Ax−b||+γ||x||

在估计领域，附加的对大的||x||的惩罚可以解释为先验知识:||x||不是很大.
在建模问题中,y=(A+v)x,A是真实观察数据，v是测量误差，较小的x有利于降低测量误差，得到x和y之间的良好逼近