基于二次筛选的回溯广义正交匹配追踪算法的稀疏信号重构

张连娜,张慧萍,李荣鹏,宋学力

(长安大学理学院,陕西 西安 710064)

0 引 言

基于奈奎斯特采样定理的传统信号处理方式存在数据处理效率低、资源浪费严重等问题。压缩感知[1]是一种新型的信号采样及重构理论，能够在远低于奈奎斯特采样率的条件下重构出原始稀疏信号，在核磁共振成像[2]、无线通信[3]和模式识别[4]等领域具有十分广泛的应用。压缩感知理论主要包括信号的稀疏表示、观测矩阵的设定和信号重构3个部分[1]，其中信号重构是指从较少的观测值中精确重构出原始稀疏信号。高效的信号重构算法是压缩感知由理论转向实际应用的枢纽，因此信号重构的研究具有重要的实际意义。

现有的信号重构算法主要有凸松弛算法、非凸松弛算法和贪婪算法等。凸松弛算法是将稀疏条件下的欠定线性问题转化为凸问题，如基追踪方法[5]、内点法[6]和梯度投影法[7]等。凸松弛算法所需的观测值较少，但其计算复杂度较高，算法收敛速度慢,不适合求解大规模问题。非凸松弛算法是通过构造近似l0范数的函数来恢复稀疏信号，如光滑l0算法[8]、逐次凹稀疏逼近算法[9]和非凸复合稀疏基算法[10]等。非凸松弛算法重构精度高，但其函数较为复杂，计算速度较慢，不适用于复杂的实际问题。贪婪算法利用内积匹配准则选取感知矩阵与信号残差相关性最大的原子，组成信号的支撑集，然后以支撑集为基础根据最小二乘法估计原始稀疏信号。贪婪算法因其算法理论简单、计算量小等优点备受关注。传统的贪婪算法有匹配追踪算法[11](Matching Pursuit, MP)、正交匹配追踪算法[12-13](Orthogonal Matching Pursuit, OMP)、正则化正交匹配追踪算法[14](Regularization Orthogonal Matching Pursuit, ROMP)、压缩采样匹配追踪算法[15](Compression Sample Match Pursuit, CoSaMP)、子空间追踪算法[16](Subspace Pursuit, SP)和广义正交匹配追踪算法[17](Generalized Orthogonal Matching Pursuit, GOMP)等。GOMP算法是基于OMP算法改进的，该算法在每次迭代时选取S个匹配原子，其中S是小于稀疏度K的一个固定常数。GOMP算法加快了原子选取速度，减少了迭代次数，降低了计算复杂度，因此该算法应用较为广泛。为了剔除GOMP算法支撑集中的错误原子，减小算法的计算代价，2017年，Zhao等人[18]提出了回溯广义正交匹配追踪算法(Backtracking Generalized Orthogonal Matching Pursuit, BGOMP)，将SP算法中的回溯过程引入到GOMP算法中，提高了算法的重构精度。

然而，BGOMP算法仍存在不足，即算法在原子识别过程中，利用内积匹配准则进行相似性度量时，内积匹配准则侧重于从方向的角度区别2个向量的差异，但对绝对数值不敏感，无法完整利用2个向量的原始信息，影响原子选取的准确率。广义Jaccard系数准则在分母中将2个向量的相同部分去掉，凸显了2个向量差异部分，从而将向量元素的作用效果放大，使得原子不容易混淆。因此，本文为了既保留内积匹配准则利用方向对向量进行相似性度量的优势，同时利用广义Jaccard系数准则弥补内积准则对数值不敏感的缺陷，提出一种基于二次筛选的回溯广义正交匹配追踪算法,该算法首先采用内积匹配准则选取较大数目的相关原子，再利用广义Jaccard系数准则对已选出的原子进行二次筛选，选出其中最优的匹配原子，优化原子选取方式。在仿真实验中，通过与其他贪婪算法对比，验证了本文提出的算法在重构误差和重构成功率方面效果更好。

1 压缩感知理论模型

压缩感知理论是指从较少的观测值中恢复原始的稀疏信号。但实际应用中，不是所有的信号都是稀疏的，因此考虑将信号f转换到某些线性基Ψ上，使其变为稀疏信号，计算公式为：

(1)

其中，Ψ=[φ1,φ2,…,φN]是N×N维的稀疏矩阵，x=[x1,x2,…,xN]T是稀疏度为K的N×1维稀疏信号，即向量x中只有K个不为0的值。

然后利用预设的投影矩阵Φ，将高维信号投影到一个低维空间上，计算公式为：

y=Φf

(2)

其中，Φ为M×N(M

结合公式(1)和公式(2)可得：

y=Φf=ΦΨx=Ax

(3)

其中，A=ΦΨ是M×N维的感知矩阵。感知矩阵A需满足有限等距性质[19-20](Restricted Isometry Property, RIP)，即若K阶向量x∈RN和常数0<δk<1满足式(4)：

(1-δk)‖x‖2≤‖Ax‖≤(1+δk)‖x‖2

(4)

则称感知矩阵A符合RIP特性。

信号重构是指从观测得到的M维信号y中重构出完整的N维的原始信号x。由于x具有稀疏性，信号重构可转化为l0范数问题来求解[18]，计算公式为：

(5)

关于公式(5)的求解，典型的贪婪算法有OMP，ROMP、SP、GOMP等算法，贪婪算法的基本思想是在每次迭代时根据感知矩阵和信号残差的相关性，选取感知矩阵A中相关性最大的列向量(原子)加入到支撑集中，再根据支撑集中的原子利用最小二乘法恢复原始信号。

2 回溯广义正交匹配追踪算法

2017年，Zhao等人[18]对GOMP算法进行了改进，提出了回溯广义正交匹配追踪算法。该算法在估计稀疏信号和更新残差步骤之间加入了回溯过程，对支撑集中的原子重新进行判断，每次迭代时选取支撑集中的K个较大元素对应的原子来进行后面的残差更新，剔除其中的错误原子，从而减小了计算代价，有效地提高了算法的重构精度。

回溯广义正交匹配追踪算法具体步骤如下所示，其中AΛt†是指AΛt的伪逆。迭代停止条件中t=M/S是为了使支撑集中原子构成的矩阵满足列满秩[18]。

输入：测量值y，感知矩阵A，稀疏度K，正整数S

初始化：迭代次数t=1，初始残差r0=y，支撑集Λ0=∅

算法具体步骤：

1)原子识别。

计算，从||中选取S个最大元素相对应的原子，并记下它们的原子序号{λ(i)}i=1,2,…,S。

2)扩大支撑集。

Λt=Λt-1∪{λ(1),λ(2),…,λ(S)}

3)利用最小二乘法估计稀疏信号。

4)回溯。

5)更新残差。

6)当t≥min{K,M/S}或‖rt‖2<ε时，停止迭代，否则t=t+1，返回步骤1。

3 基于二次筛选的回溯广义正交匹配追踪算法

回溯广义正交匹配追踪算法在原子识别过程中采用内积匹配准则进行相似性度量。内积准则实际上求的是2个向量的夹角余弦值，侧重于从方向的角度计算相似度，相似度和向量的余弦值呈正相关，2个向量越相似，余弦值越大。内积准则的表达式为：

(6)

由公式(6)可以看出，内积准则将向量归一化，导致在计算相似度时数据重要的部分不够突出，因此利用内积准则在原子识别过程中可能会导致信号重要信息的丢失[22]，进而使得原子相关性计算不准确，影响重构效果。

为了提高原子选取的准确率，本文考虑在内积准则的基础上再利用广义Jaccard系数准则对原子进行二次筛选。广义Jaccard系数[23-24]也是对2个向量x,y之间相似度的一种衡量，它的表达式为：

(7)

其中，x=(x1,x2,…,xn)，y=(y1,y2,…,yn)。

由公式(7)可以看出，它的分母是2个向量模的平方和减去这2个向量的乘积，即将2个向量相同的部分去掉，从而增大了2个向量的差异，将其中各个元素的作用效果放大，原子变得不容易混淆，避免了信号重要信息的丢失，对支撑集进行了优化，进而实现了重构精度的提高。

为了验证二次筛选的可行性和有效性，本文分别利用内积准则，广义Jaccard系数准则以及利用2种准则进行二次筛选作为相关性度量方法来判断感知矩阵与残差信号的相关性，选取最佳原子。实验选取256×1维的稀疏随机信号，稀疏度K=40，感知矩阵为128×256的随机高斯矩阵。在这3种相关性度量方法下，残差向量的模随迭代次数的变化情况如图1所示。

图1 不同匹配准则对残差的影响

由图1可以看出，随着迭代次数的增加，这3种方法的残差模的值都在减小，但利用内积准则和广义Jaccard系数准则进行二次筛选的残差值趋于0的速度更快，说明原子识别阶段利用内积准则和广义Jaccard系数准则进行二次筛选的效果不仅优于利用内积准则的效果，也优于利用广义Jaccard系数准则的效果，利用二次筛选进行原子相关性计算能更准确地找到与残差信号相匹配的原子。

因此，本文提出一种基于二次筛选的回溯广义正交匹配追踪算法(Backtracking Generalized Orthogonal Matching Pursuit Based on Secondary Screening, SSBGOMP)。该算法在原子选取阶段，首先利用内积准则选取2S个相关性最大的原子，然后再利用广义Jaccard系数准则对已选出的原子进行二次筛选，选出其中S个最相关的原子，既保留了内积匹配准则利用方向对向量进行相似性度量的优势，又利用广义Jaccard系数准则弥补了内积准则对数值不敏感的缺陷，从而提高了原子选取的正确率，优化了支撑集。

SSBGOMP算法的具体步骤如下：

输入：测量值y，感知矩阵A，稀疏度K，正整数S

初始化：迭代次数t=1，初始残差r0=y，支撑集Λ0=∅

算法具体步骤：

1)原子识别。

计算，从||中选取2S个最大元素所对应的原子，取A中这些值对应的原子构成新的相关矩阵B。

计算Jaccard(BTrt-1)，从|Jaccard(BTrt-1)|中选取S个最大元素相对应的原子，并记下它们的原子序号{λ(i)}i=1,2,…,S。

2)扩大估计支撑集。

Λt=Λt-1∪{λ(1),λ(2),…,λ(S)}

3)利用最小二乘法估计稀疏信号。

4)回溯。

5)更新残差。

6)当t≥min{K,M/S}或‖rt‖2<ε时，停止迭代，否则t=t+1，返回步骤1。

4 仿真实验

为了验证本文提出的SSBGOMP算法的重构性能，对该算法进行仿真实验，以下实验结果是在MATLABR2014a的条件下获得的。选择N×1维的稀疏随机信号，M×N维的高斯随机矩阵作为感知矩阵，其中N=256,选取原子个数S在不说明的情况下默认为K/4(当K<4时，S=1)。

实验1 各种算法在不同稀疏度下的重构误差的比较

图2 不同稀疏度下算法的重构误差

由图2可以看出，各个算法的重构误差随着稀疏度的增大而增大。在同一稀疏度下，SSBGOMP算法的重构误差略低于其他3种算法。说明该算法在不同稀疏度下的重构效果好于其他3种对比算法。其中当稀疏度为40、50和60时这4种算法的重构误差如表1所示。

表1 不同稀疏度下各种算法的重构误差

实验2 各种算法在不同稀疏度下的重构成功率的比较

选择的对比算法为OMP[12]、SP[16]、BGOMP[18]。实验结果如图3示。

图3 不同稀疏度下算法的重构成功率

由图3可知，这4种算法的重构成功率与稀疏度呈负相关，稀疏度越大，算法的重构成功率越低。稀疏度K<40时，本文所提算法与SP算法、BGOMP算法的重构成功率十分接近，几乎都为100%，而OMP算法的重构成功率已经随着稀疏度的增大而不断减小，稀疏度为40时其重构成功率已降低至48%；稀疏度40

表2 不同稀疏度下各种算法的重构成功率

实验3 在不同观测数目下几种算法重构成功率的对比

实验中设稀疏度K一定，且选取K=40，观测值M的取值为70～200，每次增加10，对SSBGOMP算法分别运行100次来求重构成功率，选择的对比算法为OMP[12]、SP[16]、BGOMP[18]。实验结果如图4所示。

图4 不同观测值下算法的重构成功率

观察图4，可以看出当稀疏度一定时，M的取值越大，算法的重构误差越小，进而重构成功率越高。当M≥130时，除OMP算法之外的其他几种算法重构成功率均达到了100%；当观测值70

表3 不同观测值下各种算法的重构成功率

5 结束语

本文提出了基于二次筛选的回溯广义正交匹配追踪算法，优化了回溯广义正交匹配追踪算法中的原子选取方式。该算法首先采用内积匹配准则选取较大数目的相关原子，然后再利用广义Jaccard系数准则对已选出的原子进行二次筛选，选出其中最匹配的原子，提高了原子识别的正确率，减小了重构误差。仿真实验验证了本文提出的算法对回溯广义正交匹配追踪算法改进的可行性及有效性，且在重构成功率上优于回溯广义正交匹配追踪算法、正交匹配追踪算法和子空间追踪算法。