搜档网

搜档网

当前位置:搜档网 > L1_norm最小化阅读

L1_norm最小化阅读

L 1范数最小化算法论述

在实践中,信号倾向于可压缩的,而可压缩信号一般都可用稀疏信号近似。给定测量信号y 并且原始信号x 是稀疏的或者可压缩的,那么很自然地就想到通过解如下形式的优化问题而恢复x :

0?|||| s u b j e c t t o y =x

argmin x

x Φ=x 其中m n R Φ?∈,n x R ∈,m y R ∈,此即为原始的0l 范数最小化问题。

当测量值被少量的带限噪声所污染,故上述优化问题中的等式约束常松弛为允许某个误

差扰动0ε>,此时得到不等式约束的0l 范数最小化问题:

02?|||| subject to ||x -y||argmin x

x Φε=≤x

由于目标函数是零范数的,而零范数是非凸的,从而很难求解。故我们可以用一范数代替零范数,将非凸问题转化为凸问题的求解,且从某种直觉推理来看,一范数的最小化亦能使问题得到稀疏解。

求解一范数的常用方法有贪婪算法(正交匹配追踪和迭代阈值)、凸优化算法(LASSO 算法与LARS 算法(统计拟合方法),同伦算法、内点法和梯度算法)、贝叶斯框架、非凸优化、穷举算法等。现讨论这几种算法的特点及应用范围。

(1)贪婪算法:通过识别一个或者多个分量迭代的精细这个稀疏解,以获得质量上的提高。主要包括正交匹配追踪和迭代阈值。匹配追踪算法其思路是:首先寻找测量值与Ф最相似的列,然后用此部分表示的列减去原始的测量矢量,得到残差向量后,再字典矩阵中选择与残差向量最相似的若干列,组成子字典矩阵,再利用子字典矩阵更新残差向量,并更新系数向量与字典矩阵相对应的元素,如此迭代,直至残差能量足够小或者达到某个预先设定的最大迭代次数,最后得到信号的稀疏表示。而迭代阈值算法更加直接的,首先令x 的第k 个元素达到最大,而其他为零,迭代给定次数或者y Ax ≈时停止,迭代阈值算法在解决稀疏近似问题中的有效性是基于经验这一事实,但是在有噪声情况下简单的迭代阈值算法的性能很差。

(2)凸优化算法:用凸优化问题代替组合问题,利用问题的结构来设计算法找到最优或者次优解。在各种情景中,凸优化给出了最优及次优的解,文献给出了在限制等距性(RIP )条件下,优化松弛的性能很好。LASSO 算法具有收缩与选择功能,求解LASSO 问题的最有效方法是LARS 算法,基本思想保证当前残差和已入选变量之间的相关系数相等的方式,选择当前残差在已入选的构成空间的投影作为搜索路径,吸收新的变量加入,再调整求解路径。同伦算法是从简单解开始,通过迭代计算,变化到所希望的复杂解的搜索算法,有点类似于匹配追踪算法。内点法基于主对偶内点框架,通过迭代方法求取稀疏解,其性能没有梯度下降算法的解稀疏,但是鲁棒性好。梯度下降算法,其主要操作是在当前的迭代中计算出最小二乘项的梯度,再通过某种规则计算下一次的迭代值,其典型算法有迭代分割与阈值算法,定点迭代,借组可分离的稀疏重构。

(3)贝叶斯框架:假定未知的系数是稀疏的,且其先验分布已知,通过观测而得到最大后验估计,来辨识出最大的后验质量区域或者在最有可能的模型中取平均。

(4)非凸优化:松弛0l 问题到一个相关的非凸问题,并尝试着辨识出一个平稳点。

(5)穷举算法:寻找所有可能的支撑集,可使用切割平面的方法来减少可行解的数量。 贪婪算法和凸优化算法在计算上是可行的,在非常好的条件下可以得到相当正确的解。贝叶斯框架和非凸优化都基于健全的原理,但是并不常能够提供理论上的保证。穷举法在算法上是正确的,但是只适合解决小规模的问题。

现重点介绍梯度下降算法:

梯度下降算法又称一阶法,主要是求解下式:

2

211||x ||+||x|| 2min x

u Φτ- 在每次迭代过程中计算其梯度()T k

x y ΦΦ-,在下一次迭代中根据下式得到1k x +: 2

211arg min()()1||||||||2

()

T T k k k k k k k k k k z x x y z x z x x x x x

αλγ+++=-ΦΦ-+-+=+- 下面是梯度下降算法的框架:

输入 观测信号

,矩阵m n R ?Φ∈,正则化参数τ>0,系数向量的出事估计为0x 输出 系数矢量n x R ∈

步骤一 初始化,令k =1

步骤二 迭代:选择

0k α≥,得到k x +。若接受检验不通过,则增大k α,重复本次迭代。

步骤三 线性搜索:选择(0,1]k γ∈,并得到k x 。

步骤四 检验:若停止准则满足,则输出1k x x +=。否则,1k k ←+,返回步骤

二,并重复以上步骤。

当字典矩阵满足约束等距性时,梯度下降算法性能很好,并且若初始值接近解,收敛速率很快。

扩展的梯度下降算法:在x 分量非零的的子集中采用简化的牛顿法,其二阶信息可以用来增强梯度投影算法的性能。

参考文献:

Joel A. Tropp, Stephen J. Wright, “TI Computational Methods for Sparse Solution of Linear Inverse Problems,” Proceedings of the IEEE, Vol 98, No 6, June 2010