基于正交匹配追踪的特征量检测算法研究

基于正交匹配追踪的特征量检测算法研究

1基于匹配追踪的压缩感知信号检测算法压缩感知，又称“压缩感知”（以下简称“压缩感知”），是一种传统的采样方法，通过在观察向量中投影信号来获得的观测变量。该理论指出,如果信号是稀疏的或者在某个基下可压缩,那么用少量的观测值就可以保持信号的结构和相关信息。基于该理论,用于精确重构信号的采样需求数量可以远低于观测的维度,这极大缓解了宽带信号处理的压力。目前,压缩感知的研究多数集中在信号或图像的重构及相关问题。但是,很多信号处理问题并不需要精确重构信号,例如信号检测这样的任务,信号获取的目的并不是为了重构信号,而是为了从采样数据中提取检测目标的信息,完成一个检测决定。如果重构信号后再进行检测,显然是浪费资源的。基于这种情况,文献指出,压缩感知对于统计推理任务是有效的,可以不需要重构信号,直接从随机投影获得的少量观测值中提取特征量解决信号检测问题。文献提出了一种基于匹配追踪(matchingpursuit,MP)的压缩感知信号检测算法(以下简称MP检测算法),从压缩感知信号获取的采样值中直接提取特征量,用于解决信号检测问题。与精确重构原信号相比,该算法完成检测任务所需要的采样点数少,算法复杂度低。但是在该算法中,作为判决依据的特征量仅由一次迭代结果决定,在感兴趣信号存在时,算法获得的特征量波动较大,影响检测性能,需要较多的采样点数来保证较好的检测性能。基于这种原因,本文提出一种基于正交匹配追踪(orthogonalmatchingpursuit,OMP)的压缩感知信号检测算法(以下简称OMP检测算法),该算法基于正交匹配追踪思想,在每次迭代中均对特征量进行修正,在感兴趣信号存在时,能够有效地降低特征量的波动,从而提高检测性能。实验结果证明,本文算法获得的特征量波动较小,相同条件下,检测成功率高,相同检测成功率下,需要的采样点数少,允许的信噪比低。2压缩传感器信号的检测2.1数据安全及存储压缩感知是一种新的信息获取理论,是建立在信号稀疏表示、测量矩阵的非相关性以及逼近理论上的一种信号采集和重建的方法。该理论2004年由Donoho等人提出,2006年发表正式论文。与基于奈奎斯特定理的传统采样方式不同,该理论指出,只要信号是稀疏的或者在某个基下是可压缩的,就可以通过远低于奈奎斯特采样定理要求的采样率获取信号的结构信息,再通过重构算法完成信号的精确重构。该理论给数据传输、存储及处理带来极大的便利。压缩感知理论主要包括两个部分:将信号在观测向量上投影得到观测值以及利用重构算法由观测值重构信号。设x是一个长度为N的信号,其稀疏度为K(K<N),稀疏度为K是指x本身有K个非零元素,或者在某种变换域Ψ内的展开系数有K个非零元素。信号(假设信号在变换域Ψ内K稀疏)在观测向量上的投影可以表示为:yi=<ϕi,x>,i=1,…,M,M<N(1)其中yi为压缩感知获取的M个采样值,{ϕi}Μi=1Mi=1是一组观测向量,由{ϕi}Μi=1Mi=1组成的观测基Φ与变换基Ψ不相关。重构信号的关键是找出信号x在Ψ域中的稀疏表示,可以通过l0范数优化问题找到具有稀疏结构的解[2,3,4,5,6,7,8,9,10,11,12,13,14,15]:min‖ΨTx‖0s.t.y=Φx(2)由于式(2)的优化问题是一个难求解的NP-hard(NondeterministicPolynomial-timehard)问题,所以可以用l1约束取代l0约束:min‖ΨTx‖1s.t.y=Φx(3)可以看出,压缩感知获得的采样值已经保持了原信号的结构及相关信息,因此可以不需要重构信号,利用检测算法直接从采样值中提取特征量进行判决,完成信号检测任务。2.2高斯白噪声的检测算法本文中检测的目的是区别两种假设:H0∶x=nvs.H1∶x=s+n(4)这里,s表示我们感兴趣的信号,n表示加性高斯白噪声。信号s在变换域Ψ内稀疏度为K,即:s=Ψsθs‖θs‖0=k(5)其中Ψs和θs表示相应的变换基与稀疏系数。由于高斯白噪声在变换域内不稀疏,因此检测问题可以重新描述为区别式(6)中的两种假设:H0∶x=nvs.H1∶x=Ψsθs+n(6)根据式(6),又可以通过判断θs是否存在来区别两种假设。即:H0∶θs=0vs.H1∶θs≠0(7)基于压缩感知理论,对感兴趣的x通过y=Φx获取,为了完成检测任务,需要利用检测算法从采样值y中提取特征量作为判决依据,用来区别两种假设。显然,如果提取的特征量可以完成式(7)判断,那么就可以区别式(4)中的两种假设,达到检测目的。2.3检测结果及分析文献从基于匹配追踪的信号重构算法中得到启发,在其基础上提出一种检测算法,与精确重构相比,算法完成检测任务需要的采样点数和迭代次数均有所减少,节省了相关资源。算法描述如下:令V=ΦΨ,迭代次数为T,T值应小于基于匹配追踪的信号精确重构算法所需要的迭代数。1)初始化:余量r0=y,估计值=0,∈RN,迭代次数t=1。2)在V中选出与余量相关性最大的列:nt=argmaxi=1,⋯,Ν<rt-1,vi>‖vi‖nt=argmaxi=1,⋯,N<rt−1,vi>∥vi∥3)更新所选列的系数估计值:ˆθnt=ˆθnt+<rt-1,vnt>‖vnt‖24)更新余量:rt=rt-1-<rt-1,vnt>‖vnt‖2vnt5)t=t+1。如果t<T,回到步骤2;否则,到步骤6。6)如果‖‖∞>γ,选择H1;否则,选择H0。可以看到,该算法通过处理采样值y获得估计值,由于迭代次数T较少,并且存在加性噪声,因此,基于不能精确重构信号。然而,对于检测任务,中已经包含了足够的信息,可以从中提取特征量‖‖∞作为判决依据。在感兴趣信号存在时(H1情况下),该特征量为信号的一个重要分量在变换域内的系数估计值的绝对值;在感兴趣信号不存在时(H0情况下),该特征值仅表示是噪声在变换域内的一个投影系数。此外,由于加性噪声对‖‖∞的影响,算法利用一个非零阈值γ作为判决条件,该检测阈值可以根据先验条件及检测需求通过蒙特卡罗模拟方法选择。由以上描述可以看到,该算法能够完成检测任务。但是,在该算法中,特征量‖ˆθ‖∞的值仅由一次迭代过程决定。当感兴趣信号存在时,由于测量矩阵Φ在每次信号获取的过程中是基于某种分布(例如高斯分布)随机生成的,因此,仅由一次迭代过程决定的‖ˆθ‖∞会有较大的波动,这就需要较准确的阈值估计及较多的采样点数来保证较高的检测成功率,显然这需要大量的资源;当感兴趣信号不存在时,如前文所述,算法获得的‖ˆθ‖∞仅是噪声在相应变换基上的分量,其数值和波动都很小,并且与检测阈值差异很大,对算法的检测成功率影响很小。从以上分析可以看出,影响算法检测性能的主要原因是H1情况下特征量‖ˆθ‖∞的波动,因此通过降低该情况下特征量‖ˆθ‖∞的波动,就可以获得更好的检测性能。针对这种情况,可以基于正交匹配追踪思想对MP检测算法进行改进,在每次迭代中,通过寻找采样值在已选列上的最优投影,对‖ˆθ‖∞进行修正,从而获得波动较小的特征量‖ˆθ‖∞。3基于匹配追踪的特征量正交匹配追踪是在匹配追踪基础上提出的一种改进算法,与匹配追踪相比,该算法特点是在每次迭代中将选出的列用Gram-Schmidt正交化方法进行正交化处理,再将采样值在已选列张成的空间上投影,其目的是加快算法收敛速度。文献利用正交匹配追踪从采样值中重构出原信号,相同迭代次数下,重构效果优于基于匹配追踪的方法,其主要原因是OMP检测算法在每次迭代中,追求采样值在已选列上的最优投影,在最优投影的获得的过程中,稀疏系数得到更新。因此,针对MP检测算法中H1情况下特征量‖ˆθ‖∞波动大的问题,本文基于正交匹配追踪思想进行改进,在每次迭代中均对估计系数ˆθ进行更新,进而达到修正特征量‖ˆθ‖∞、降低其波动的目的。算法描述如下:令V=ΦΨ,迭代次数为T,T值应小于基于匹配追踪的精确信号重构算法所需要的迭代数。1)初始化:余量r0=y,迭代次数t=1,V0为空矩阵。2)在V中选出与余量相关性最大的列:nt=argmaxi=1,⋯,Ν<rt-1,vi>3)更新已选列空间:Vt=[Vt-1vnt]4)通过解决一个最小二乘问题,保证残差最小,获得在已选列向量上的最优投影,更新已选各列的稀疏系数估计值ˆθ:ˆθ=argminθ‖y-Vtθ‖25)更新余量:rt=y-Vtˆθ6)t=t+1。如果t<T,回到步骤2。否则,到步骤7。7)如果‖ˆθ‖∞>γ,选择H1;否则,选择H0。由OMP检测算法可以看到,在每次迭代中,通过采样值y在已选各列上的最优投影,算法对已选各列的稀疏系数进行了更新,特征量‖ˆθ‖∞得到修正,与MP检测算法相比,OMP检测算法在H1情况下获得的特征量‖ˆθ‖∞波动较小。图1以H1情况成立为先验条件,考察了两种算法对信噪比SNR(signaltonoiseratio)为20的相同信号分别进行1000次检测所获得的特征量‖ˆθ‖∞的波动情况。其中,纵坐标为考察指标,是1000次检测实验中获得的1000个特征量的方差,横坐标为压缩感知系统的采样点数。从图1可以看到,在H1情况下,与MP检测算法相比,本文提出的OMP检测算法在各个采样点数下获得的特征量的波动均较小。4有效阈值区间范围设我们关心的感兴趣信号s长度N=256,由三个正弦分量叠加而成,信号时域波形如图2所示。该信号在频域是稀疏的,满足基于压缩感知信号检测问题对待检测信号的要求。噪声n为加性白高斯噪声。压缩感知过程通过一个M×N的观测矩阵Φ实现,在每次检测实验中,Φ是一个随机产生的元素满足高斯分布的矩阵,M为压缩感知采样点数。实验中,先验概率Pr(H0)=Pr(H1)=1/2,检测成功率为2000次检测实验的统计结果。同时规定,检测成功率高于95%时,检测有意义,对应的检测阈值区间有效阈值区间;检测成功率低于95%时,检测无意义,对应的检测阈值区间为无效阈值区间,即检测成功率低于95%的情况本文不予考虑。第一,考察在相同采样点数下,OMP检测算法和MP检测算法在各个检测阈值下的检测成功率情况。令采样点数M=50,信噪比SNR=20,算法迭代次数T=6,依据先验条件检测阈值选择范围为[2,4.5],阈值步进为0.1。图3给出了实验结果,由图可以看出在有效阈值区间内,OMP检测算法的成功率大于等于MP检测算法的成功率。同时还可以看到,OMP检测算法有效阈值区间范围比MP检测算法广阔,有利于检测阈值的估计。第二,考察在相同检测阈值下,OMP检测算法和MP检测算法获得高检测成功率所需要的采样点数情况。令检测阈值为3.5,信噪比SNR=20,算法迭代次数T=6,采样点数M变化范围为,步进为1。实验结果如图4所示,由图可以看出,在相同阈值下,与MP检测算法相比,OMP检测算法用较少的采样点数就可以获得较高的检测成功率,减少了采样系统的成本,降低了系统复杂性。此外,在相同实验条件下,表1给出了在其他一些有效阈值下,两种检测算法稳定获得高检测成功率所需要的最少采样点数。由表1可以看到,在其他有效阈值内,与MP检测算法相比,OMP检测算法同样具有较好的检测性能。同时还可以看到,OMP检测算法使用较少的采样点就可以获得较广阔的有效阈值空间。第三,考察在相同采样点数、相同检测阈值下,OMP检测算法和MP检测算法获得高检测成功率所允许的噪声强度情况。令采样点数M=50,检测阈值为3.5,算法迭代次数T=6,信噪比(SNR)变化范围为,步进为1。实验结果如图5所示,由图可以看出,与MP检测算法相比,相同检测成功率下,OMP检测算法允许的信噪比低,抗噪声能力强;对于某一确定信噪比的信号,OMP检测算法获得的检测成功率高。为了进一步证明算法的有效性,下面针对雷达系统中的实际问题进行实验。在雷达系统中,线性调频信号是一种非常重要的信号形式,信号瞬时频带宽的特性虽然提高了雷达系统的目标检测及识别能力,却给信号采集及数据处理带来极大压力,如何使用较少的采集数据完成检测是一个关键技术。本实验分别应用MP算法和OMP算法检测某雷达信号,考察在相同检测成功率下两种算法需要的采样点数。该信号具有三个线性调频分量,混频后载波频率均为0,带宽分别为300MHz、200MHz、150MHz,幅度分别为0.5、0.2、0.3,时宽为10μs,所处环境信噪比为10。实验结果如图6所示,由图可以看出,相同检测成功率下,OMP检测算法所需要的采样点数要少于MP检测算法,因此,使用OMP检测算法进行检测可以减轻接收系统在采样及数据处理方面的压力。从以上实验结果可以看出,由于OMP检测算法在H1情况下能够获得波动较小的特征量,因此在相同