刘 艳,李 雷

(南京邮电大学 非结构化数据计算理论与应用研究中心，江苏 南京 210046)

基于拟牛顿法的梯度追踪算法研究

刘 艳,李 雷

(南京邮电大学 非结构化数据计算理论与应用研究中心，江苏 南京 210046)

为了解决传统迭代算法中需要计算正交投影的问题，将拟牛顿法与梯度追踪算法(Gradient Pursuit)相结合，提出了基于拟牛顿法的梯度追踪算法(Quasi-Newton Method based Gradient Pursuit,QNMGP)。拟牛顿法是解决无约束最优化问题的有效方法，其避免了牛顿法需要求解Hesse矩阵的问题，降低了计算量，提高了收敛速度，新提出的算法通过限域拟牛顿法来求解更新方向，并将其运用到梯度追踪算法中。为验证新提出算法的可行性与有效性，基于MATLAB仿真平台，从重构时间、均方误差和峰值信噪比三个方面对QNMGP算法与其他贪婪算法进行了仿真对比实验验证。仿真实验结果表明，在同等的测试环境下，新提出的QNMGP算法重构效果远优于其他算法，且在重构时间上也具有一定的优势。

拟牛顿法；梯度追踪；最优化问题；重构算法

1 概 述

压缩感知[1-3](Compressive Sensing,CS)理论是近年来出现的一种新型压缩采样方法。该理论指出，如果信号可压缩或者在某个变换域上是稀疏的，就能用一个与变换基不相关的观测矩阵将高维信号投影到一个低维空间上，接着通过求解一个优化问题就能够从这些少量的投影中高概率地重构出原信号。

假设b∈Rn为一个已知的向量，A为m×n维的观测矩阵且满足m

b=Ax+ε

(1)

由于贪婪迭代算法的迭代过程比较简单，因此目前应用比较广泛，其主要是解决式(2)这类子空间优化问题，但是此类算法都需要通过计算量很大的正交投影来估计信号，在一定程度上增加了重构计算量，降低了收敛速度。……