压缩感知中基于拟牛顿梯度追踪的重构算法研究

摘要

压缩感知(Compressed Sensing，CS)是一种利用信号稀疏结构将数据的采集和重建方法联合到一起的技术。贪婪类算法作为CS经典重构算法类型之一，由于自身具有快速迭代的特点而被广泛应用，其通过使用最小二乘法解决正交投影问题来计算估计信号。最小二乘法在非经典线性问题求解上精度并不高，且单次迭代中的正交投影均需求得矩阵的逆或者广义逆，计算量较大。论文基于梯度迭代替代贪婪类算法中正交投影的理论，针对牛顿追踪算法(Newton Pursuit，NP)引入高阶导数时重构效果优良但计算复杂度高的问题，研究基于拟牛顿梯度追踪的重构算法。 首先，论文简单概述了CS理论框架和发展应用，在对现有梯度追踪类算法研究的基础上，针对拟牛顿梯度追踪算法即基于变尺度法的梯度追踪算法(Variable Metric Method Based Gradient Pursuit，VMMGP)计算复杂度高的问题，考虑多步拟牛顿法这一无约束优化方法可构造Hessian矩阵的近似逆矩阵，提出一种改进算法——基于多步拟牛顿法的梯度追踪算法(Gradient Pursuit Algorithm Based on Multi-Step Quasi-Newton Method，MSQN-GP)。算法在VMMGP算法基础上，迭代中利用多步梯度差值信息直接逼近目标函数的Hessian矩阵的逆，避免了VMMGP算法更新迭代方向时复杂的矩阵求逆运算，降低了计算复杂度。 接着，从提高重建精度的角度考虑，由于VMMGP算法利用变尺度法求得近似矩阵与NP算法理论上的Hessian矩阵存在偏差，导致重建精度与NP算法仍有差距，而修正拟牛顿法则是利用函数值与梯度值构建扰动项修正此偏差。因此，论文在VMMGP算法的基础上进行了进一步改进，提出了基于修正拟牛顿法的梯度追踪算法(Gradient Pursuit Algorithm Based on Modified Quasi-Newton Method，MQN-GP)。算法利用函数值与梯度值为VMMGP中的单步梯度差值添加扰动项，修正迭代中近似矩阵偏差，提升了算法的重构精度。 而后，综合考虑算法的重构精度与计算复杂度性能，论文基于MSQN-GP与MQN-GP算法提出一种改进的多步拟牛顿梯度追踪算法(Improved Multi-step Quasi-Newton Gradient Pursuit Algorithm，IMSQN-GP)。IMSQN-GP算法利用迭代中的函数值与梯度值为MSQN-GP算法的多步梯度差值添加扰动项，以此更为精确地逼近Hessian逆矩阵，用于迭代方向的更新实现数据重建。算法不仅避免了二阶导数与矩阵逆的运算，降低了复杂度，而且扰动项的添加修正了近似矩阵与Hessian矩阵逆之间的偏差，提升了算法的重构精度。 论文通过理论推导证明了改进算法的下降性和二阶收敛性，并利用Matlab软件对现有的梯度追踪重构算法和改进算法进行了仿真实验分析。仿真实验主要从算法的重构精度、计算复杂度及存储需求的角度进行各算法重构性能的比较，验证了改进算法在较高的重构精度基础上有效降低了计算复杂度。