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