分段正交匹配追踪(StOMP)算法改进研究
汪浩然;夏克文;牛文佳
【摘 要】信号重构是压缩感知的核心技术之一,而其重构精度和所耗时长直接影响其应用效果.现今分段正交匹配追踪算法(StOMP)因耗时短而得到广泛应用,但也存在着重构精度差、稳定性低的缺点.提出一种基于粒子优化(PSO)算法且同时具有回溯特性的StOMP改进算法(ba-IWPSO-StOMP),即首先在StOMP算法的一次原子选择上,引入回溯策略,实现原子的二次筛选;在每次迭代计算中,使用具有惯性权重指数递减的PSO(IWPSO)算法对传感矩阵中部分原子进行优化,从而实现更高精度,更少迭代次数的信号重构.对一维信号和二维图像的重构结果表明,在稀疏条件相同的情况下,算法在收敛时间较短的情况下,其重构精度明显优于StOMP等同类算法.%Signal reconstruction is one of the core technologies of compressed sensing, and the reconstruction accuracy and time-consuming directly affects its application effect. Nowadays, Stagewise Orthogonal Matching Pursuit(StOMP) algorithm has been widely used for short running time, but its reconstruction accuracy is unsatisfactory. To make up for the defects of the StOMP algorithm, this paper presents a variant of StOMP, called backtracking-based ada
ptive and iner-tia weight index decreasing particle swarm optimization-based StOMP(ba-IWPSO-StOMP)algorithm. As an extension of the StOMP algorithm, in each iteration, the proposed ba-IWPSO-StOMP algorithm incorporates a backtracking tech-nique to select atoms by the second screening, then uses the IWPSO algorithm to optimize atoms in the measurement matrix. Through these modifications, the ba-IWPSO-StOMP algorithm achieves superior reconstruction accuracy and less times of iteration compared with other OMP-type algorithms. Moreover, unlike its predecessors, the ba-IWPSO-StOMP algorithm does not require to know the sparsity level in advance. The experiments demonstrate the performance of ba-IWPSO-StOMP algorithm is superior to several other OMP-type algorithms.
【期刊名称】《计算机工程与应用》
【年(卷),期】2017(053)016
【总页数】7页(P55-61)
【关键词】压缩感知;分段正交匹配追踪;粒子优化
【作 者】汪浩然;夏克文;牛文佳
【作者单位】河北工业大学 电子与信息工程学院,天津 300401;河北工业大学 电子与信息工程学院,天津 300401;河北工业大学 电子与信息工程学院,天津 300401
【正文语种】中 文
【中图分类】TP391
压缩感知（CS）理论是由Donoho和Candes等在2005年提出的一种从信号稀疏分解和逼近理论发展而来的新的信号处理理论[1-3]。该理论表明，用远低于Nyquist采样定理要求的频率对信号进行采样也能够实现信号的精确重构。其本质内容是：可压缩信号（即在某个基上具有稀疏描述的信号）的少量随机的线性投影即包含了重构和处理该信号的足够信息，即仅仅利用信号可压缩的先验知识和少量全局的线性测量就可以获得精确重建。这种观测策略可以显著减少测量时间、采样率，节省模数转换资源和存储空间。
压缩感知包括3个环节：原始信号稀疏表示、测量矩阵设计和利用观测值重构原始信号。其中，重构算法的作用是将采集到的低维数据尽可能地恢复成高维的原信号，也可以看作是获
得的已知信号在给定字典上的稀疏分解的过程。按寻优目标函数的表示方式，重构算法主要可分为：（1）使信号l1范数最小的凸松弛[4-5]和非凸局部最优方法；（2）基于匹配追踪策略的、使信号l0范数最小的贪婪寻优算法。在第一类方法中，凸松弛是最常用的重构策略之一，它首先在冗余字典中全局搜索稀疏基，将信号l1范数最小化问题转化为一类有约束条件的极值问题，然后利用线性规划（LP）求解。凸松弛算法中最典型的是基追踪（BP）[6-7]算法，它使用线性规划中的内点法，在字典的所有基矢量中搜索使全局目标函数极小化的最优基矢量，搜索结果为全局最优；其精确重建具备充分的理论依据并且所需的观测数目少，但算法复杂度极高[8]。而第二类l0范数最小化贪婪寻优算法通过每次迭代时选择一个局部最优解来逐步逼近原始信号。贪婪算法的每次迭代主要包括以下两步：（1）原子匹配（到一个或多个原子，使其与上一轮迭代所得残差的内积最大，将这些原子加入基原子候选集）；（2）更新（更新逼近系数，使当前残差的范数最小，更新残差）。贪婪算法虽然精度比凸松弛法略低，但由于其易于实现、重构速度快的特点而得到广泛应用。典型代表包括匹配追踪（MP）算法[9]、正交匹配追踪（OMP）算法[10]和正则化正交匹配追踪（ROMP）算法[11]等。
匹配追踪（MP）算法是最早的一种匹配追踪迭代算法，与BP算法相比计算复杂度低并具有
渐近收敛性，但由于其在已选定原子（传感矩阵的列向量）集合上的投影的非正交性导致每次迭代的结果都是次最优的，因此需要经过很多次的迭代才能实现收敛。针对这一缺陷，正交匹配追踪（OMP）算法沿用了MP算法的原子选择准则，通过递归地正交化已选择原子集合来保证每次迭代所选的原子最优，相较于MP算法收敛速度得到了明显提升。OMP算法利用Gram-Schmidt正交化过程将投影方向正交化，从而提高了追踪的效率，但是其正交化过程却引入了新的计算开销，导致计算时间过长。为解决这一问题，2012年Donoho D提出了分段正交匹配追踪（StOMP）算法[12]，将OMP算法进行进一步的简化，大大提高了运算速度。这一算法的本质在于每次匹配追踪时选出的是多个匹配原子而不是单个原子，减少了匹配次数，但该算法的重构精度不够理想。另一种改善OMP类算法性能的算法是由Huang于2011年提出的基于回溯策略的匹配追踪（baOMP）算法，baOMP算法将迭代过程分为多个阶段，在每个阶段通过余量的更新进行若干次迭代，通过设置一个可变步长多次迭代逐步逼近稀疏度。该算法可实现对稀疏度自适应，且重构精度较高。
文中针对欠采样条件下的信号重建问题，结合了StOMP算法中的分段匹配追踪策略和baOMP算法中的回溯策略，并对每次迭代所得到的传感矩阵使用惯性权重指数递减粒子优化算法（IWPSO）进行原子优化，提出一种基于惯性权重指数递减粒子优化算法和回溯策
略的分段正交匹配追踪（ba-IWPSO-StOMP）算法。通过回溯策略和IWPSO算法优化，本文使用的传感矩阵中的原子质量得到了明显改善，从而克服了StOMP算法重构精度受限于阈值选取的不足，可以对信号进行更高精度的稀疏重构。文中对本文算法和多种同类算法进行了仿真比较和结果分析。
2.1 压缩感知基本理论
假设x是一个一维有限长的实值离散时域信号，长度为N,x可在某组正交基Ψ=[ψ1,ψ1,…,ψN]上被表示为：
其中s为x在Ψ域的稀疏系数，x和s均为N×1维向量。若s中大部分系数为零或按降序排列后呈指数级衰减且趋近于零，则认为信号x是可压缩的。信号可压缩（稀疏）是压缩感知应用的前提条件。使用一个M×N维的测量矩阵Θ(M＜＜N)对信号x进行线性测量，得到M×1维的测量向量y，即
式中，Φ=ΘΨ是M×N维的矩阵，称Φ为传感矩阵。若传感矩阵Φ满足等距限制性准则（RIP），则x的稀疏系数s可以通过求解如下优化问题实现精确重构：
式中，””表示0范数，即”⋅”中非零元素的个数。最终由式（1）得到重构的原始信号x。
目前常见的恢复算法主要有两种，一种是凸松弛法，包括BP（基追踪）、SL0（平滑l0范数）等。另一种是匹配追踪类算法，包括MP（匹配追踪）、OMP（正交匹配追踪）等。其他的重构方法包括贝叶斯方法，迭代加权方法和非凸方法，等等。本文主要研究匹配追踪类算法。
2.2 分段正交匹配追踪算法
正交匹配追踪（OMP）算法是在匹配追踪（MP）算法基础上提出的一种改进算法。与匹配追踪相比，该算法特点是在每次迭代中将选出的列用Gram-Schimidt正交化方法进行正交化处理，再将采样值在已选列组成的张量空间上投影，其目的是加快算法收敛速度。虽然OMP算法精度高于MP算法，但该算法仍然保留了MP算法在每次迭代过程中只选择一个原子的策略，这导致了OMP算法面对大规模问题时收敛速度过慢的问题[13]。
StOMP算法将OMP算法进行一定程度的简化，以逼近精度为代价进一步提高计算速度。该算法与OMP算法的区别在于选择子坐标集时设定了一个门限值，在每个迭代阶段，形成匹配
滤波器，识别出所有幅值超过设定门限值所对应的坐标。StOMP算法每次迭代选择若干元素，而OMP算法每次迭代仅选出一个元素，所以StOMP算法比OMP算法执行速度快，更适合于解决大规模问题。StOMP算法描述如下。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。