基于正交匹配追踪的压缩感知信号检测算法_刘冰
第31卷 第9期2010年9月
仪器仪表学报
Ch i nese Journa l o f Sc ientific Instru m ent
V ol 131N o 19Sep .2010
收稿日期:2009-12 R ece i ved D ate :2009-12 *基金项目:第四十五批博士后科学基金20090450571
基于正交匹配追踪的压缩感知信号检测算法
*
刘 冰1
,付 平1
,孟升卫
1,2
(1 哈尔滨工业大学自动化测试与控制系 哈尔滨 150080;2 中国科学院电子学研究所 北京 100190)
摘 要:在不重构信号的情况下,利用检测算法直接处理压缩感知信号获得的采样值可以完成信号检测任务。目前的检测算法中,作为判决依据的特征量仅由一次迭代过程决定。在感兴趣信号存在时,算法获得的特征量波动较大,影响检测性能。基于这种原因,本文提出一种改进算法,在每次迭代中基于正交匹配追踪思想修正特征量,降低特征量的波动,提高检测性能。实验结果表明,与原算法相比,本文算法获得的特征量波动小,相同检测阈值下,检测成功率高,相同检测成功率要求下,需要的采样点数少,允许的信噪比低。
关键词:压缩感知;信号检测;特征量;正交匹配追踪
中图分类号:TP391 文献标识码:A 国家标准学科分类代码:510.40
Co mpressive sensi ng si gnal detection al gorith m based on orthogonalmatchi ng pursuit
L i u B i n g 1
,Fu Ping 1
,M eng Sheng w ei
1,2
(1.D e p ar t m ent of A u t oma tic T est and Contro l ,H arbin Institute of T echnology,H arb i n 150080,China ;
2.Instit u te of E lectronics ,CA S ,B ei j i ng 100190,Ch i na)
Abst ract :W ithout reconstructi n g the signal itsel,f si g na l de tecti o n could be so lved by a detection a l g orithm,wh ich directly processes the sa mp li n g values obta i n ed fro m co m pressi v e sensing si g na.l I n current detecti o n a l g orit h m,as t h e judg m en t criterion ,the characteristic quantity is deter m ined i n one iterative process .W hen the si g na l of interest ex ists ,the characteristic quantity obtained fro m the detecti o n a l g orithm fluctuates ,w hich decreases the detecti o n per -f o r m ance .Therefore ,i n this paper ,w e propose an i m pr oved a l g orithm,w hich a m ends the characteristic quantity based on o rthogona lm atch i n g pursu it in each iteration ,reduces the fluctuation of the characteristic quantity and i m -proves the detection perfor m ance .Experi m ent results show that co m pared w it h o ri g i n al algorithm the proposed m eth -od greatly reduces the fluct u ation o f the characteristic quantity ,has h i g her success rate o f detection under the sa m e detection threshold ,requires fe w er sa m ples under the sa m e success rate of detection and a ll o w s l o w er SNR under the sa m e success rate o f detection .K ey w ords :co m pressive sensi n g ;si g nal detection ;characteristic quantity ;orthogonalm atching pursuit (OM P)
1 引 言
压缩感知(Co mpr ess i ve sensing),也称为/压缩传感0(以下均称为/压缩感知0),是一种非传统的采样方式,每一步观测是通过信号在观测向量上的投影获得的。该理论指出,如果信号是稀疏的或者在某个基下可压缩,那
么用少量的观测值就可以保持信号的结构和相关信
息[1-3]
。基于该理论,用于精确重构信号的采样需求数量可以远低于观测的维度
[4-6]
,这极大缓解了宽带信号处理
的压力。
目前,压缩感知的研究多数集中在信号或图像的重
构及相关问题[7-9]
。但是,很多信号处理问题并不需要精确重构信号,例如信号检测这样的任务,信号获取的目的
1960仪器仪表学报第31卷
并不是为了重构信号,而是为了从采样数据中提取检测
目标的信息,完成一个检测决定。如果重构信号后再进
行检测,显然是浪费资源的。基于这种情况,文献[10-
11]指出,压缩感知对于统计推理任务是有效的,可以不
需要重构信号,直接从随机投影获得的少量观测值中提
取特征量解决信号检测问题。
文献[12]提出了一种基于匹配追踪(matchi ng pur-
sui,t M P)的压缩感知信号检测算法(以下简称M P检测
算法),从压缩感知信号获取的采样值中直接提取特征
量,用于解决信号检测问题。与精确重构原信号相比,该
算法完成检测任务所需要的采样点数少,算法复杂度低。
但是在该算法中,作为判决依据的特征量仅由一次迭代
结果决定,在感兴趣信号存在时,算法获得的特征量波动
较大,影响检测性能,需要较多的采样点数来保证较好的
检测性能。基于这种原因,本文提出一种基于正交匹配
追踪(ort hogonal matchi ng pursui,t O M P)的压缩感知信号
检测算法(以下简称O M P检测算法),该算法基于正交匹
配追踪思想[13-14],在每次迭代中均对特征量进行修正,在
感兴趣信号存在时,能够有效地降低特征量的波动,从而
提高检测性能。实验结果证明,本文算法获得的特征量
波动较小,相同条件下,检测成功率高,相同检测成功率
下,需要的采样点数少,允许的信噪比低。
2压缩感知信号检测
2.1压缩感知理论
压缩感知是一种新的信息获取理论,是建立在信号
稀疏表示、测量矩阵的非相关性以及逼近理论上的一种
信号采集和重建的方法。该理论2004年由Donoho等人
提出,2006年发表正式论文。与基于奈奎斯特定理的传
统采样方式不同,该理论指出,只要信号是稀疏的或者在
某个基下是可压缩的,就可以通过远低于奈奎斯特采样
定理要求的采样率获取信号的结构信息,再通过重构算
法完成信号的精确重构[1-6]。该理论给数据传输、存储及
处理带来极大的便利。
压缩感知理论主要包括两个部分:将信号在观测向
量上投影得到观测值以及利用重构算法由观测值重构信
号[1]。设x是一个长度为N的信号,其稀疏度为K(K<
N),稀疏度为K是指x本身有K个非零元素,或者在某
种变换域7内的展开系数有K个非零元素。信号(假设
信号在变换域7内K稀疏)在观测向量上的投影可以表
示为:
y i =<<
i
,x>,i=1,,,M,M 其中y i 为压缩感知获取的M个采样值,{< i }M i=1 是一组 观测向量,由{< i }M i=1 组成的观测基5与变换基7不相 关[3]。重构信号的关键是找出信号x在7域中的稀疏表示,可以通过l 范数优化问题找到具有稀疏结构的解[2-15]: m i n z7T x z s.t.y=5x(2)由于式(2)的优化问题是一个难求解的NP-hard (N ondeter m i nistic Po l yno m ia-l tm i e hard)问题,所以可以用l1约束取代l0约束[1-5]: m i n z7T x z 1 s.t.y=5x(3)可以看出,压缩感知获得的采样值已经保持了原信号的结构及相关信息,因此可以不需要重构信号,利用检测算法直接从采样值中提取特征量进行判决,完成信号检测任务。 2.2基于压缩感知的检测问题描述及检测原理 本文中检测的目的是区别两种假设: H0B x=n v s.H1B x=s+n(4) 这里,s表示我们感兴趣的信号,n表示加性高斯白噪声。信号s在变换域7内稀疏度为K,即: s=7s H s z H s z0=k(5)其中7s和H s表示相应的变换基与稀疏系数。由于高斯白噪声在变换域内不稀疏,因此检测问题可以重新描述为区别式(6)中的两种假设: H0B x=n v s.H1B x=7s H s+n(6) 根据式(6),又可以通过判断H s 是否存在来区别两种假设。即: H B H s =0vs.H 1 B H s X0(7)基于压缩感知理论,对感兴趣的x通过y=5x获取,为了完成检测任务,需要利用检测算法从采样值y中提取特征量作为判决依据,用来区别两种假设。显然,如果提取的特征量可以完成式(7)判断,那么就可以区别式(4)中的两种假设,达到检测目的[12]。 2.3基于匹配追踪的压缩感知信号检测算法及检测性能分析 文献[12]从基于匹配追踪的信号重构算法中得到启发,在其基础上提出一种检测算法,与精确重构相比,算法完成检测任务需要的采样点数和迭代次数均有所减少,节省了相关资源。算法描述如下: 令V=57,迭代次数为T,T值应小于基于匹配追踪的信号精确重构算法所需要的迭代数。 1)初始化:余量r0=y,估计值^H=0,^H I R N,迭代次数t=1。 2)在V中选出与余量相关性最大的列: n t=ar g m ax i=1,,,N z v i z 3)更新所选列的系数估计值: ^H n t =^H n t + t-1 ,v n t > z v n t z2 第9期刘 冰等:基于正交匹配追踪的压缩感知信号检测算法1961 4)更新余量:r t =r t-1- > z v n t z 2 v n t 5)t =t+1。如果t 6。 6)如果z ^H z ]>C ,选择H 1;否则,选择H 0。可以看到,该算法通过处理采样值y 获得估计值^H ,由于迭代次数T 较少,并且存在加性噪声,因此,基于^H 不能精确重构信号。然而,对于检测任务,^H 中已经包含了足够的信息,可以从^H 中提取特征量z ^H z ]作为判决依据。在感兴趣信号存在时(H1情况下),该特征量为信号的一个重要分量在变换域内的系数估计值的绝对值;在感兴趣信号不存在时(H0情况下),该特征值仅表示是噪声在变换域内的一个投影系数。此外,由于加性噪声对z ^H z ]的影响,算法利用一个非零阈值C 作为判决条件,该检测阈值可以根据先验条件及检测需求通过蒙特卡罗模拟方法选择。由以上描述可以看到,该算法 能够完成检测任务。但是,在该算法中,特征量z H ^ z ]的值仅由一次迭代过程决定。当感兴趣信号存在时,由于测量矩阵5在每次信号获取的过程中是基于某种分布(例如高斯分布)随机生成的,因此,仅由一次迭代过 程决定的z H ^z ] 会有较大的波动,这就需要较准确的阈值估计及较多的采样点数来保证较高的检测成功率,显 然这需要大量的资源;当感兴趣信号不存在时,如前文所 述,算法获得的z H ^ z ]仅是噪声在相应变换基上的分量,其数值和波动都很小,并且与检测阈值差异很大,对算法的检测成功率影响很小。 从以上分析可以看出,影响算法检测性能的主要原 因是H1情况下特征量z H ^z ] 的波动,因此通过降低该情况下特征量z H ^z ] 的波动,就可以获得更好的检测性能。针对这种情况,可以基于正交匹配追踪思想对M P 检测算法进行改进,在每次迭代中,通过寻找采样值在已 选列上的最优投影,对z H ^z ] 进行修正,从而获得波动较小的特征量z H ^z ] 。 3 基于正交匹配追踪的压缩感知信号检测算法 正交匹配追踪[14] 是在匹配追踪基础上提出的一种 改进算法,与匹配追踪相比,该算法特点是在每次迭代中将选出的列用G ra m-Sch m i dt 正交化方法进行正交化处理,再将采样值在已选列张成的空间上投影,其目的是加快算法收敛速度。 文献[13]利用正交匹配追踪从采样值中重构出原信号,相同迭代次数下,重构效果优于基于匹配追踪的方法,其主要原因是OM P 检测算法在每次迭代中,追求采样值在已选列上的最优投影,在最优投影的获得的过程 中,稀疏系数得到更新。因此,针对M P 检测算法中H1 情况下特征量z H ^z ] 波动大的问题,本文基于正交匹配 追踪思想进行改进,在每次迭代中均对估计系数H ^进行更新,进而达到修正特征量z H ^z ] 、降低其波动的目的。算法描述如下: 令V =57,迭代次数为T,T 值应小于基于匹配追踪的精确信号重构算法所需要的迭代数。 1)初始化:余量r 0=y ,迭代次数t =1,V 0为空矩阵。 2)在V 中选出与余量相关性最大的列:n t =ar g m ax i =1,,,N 4)通过解决一个最小二乘问题,保证残差最小,获得在已选列向量上的最优投影,更新已选各列的稀疏系数 估计值H ^:H ^=ar g m i n H z y -V t H z 2 5)更新余量:r t =y -V t H ^6)t =t +1。如果t 7)如果z H ^z ] >C ,选择H 1 ;否则,选择H 0 。由OM P 检测算法可以看到,在每次迭代中,通过采 样值y 在已选各列上的最优投影,算法对已选各列的稀 疏系数进行了更新,特征量z H ^ z ]得到修正,与M P 检测算法相比,OM P 检测算法在H1情况下获得的特征量z H ^z ] 波动较小。图1以H1情况成立为先验条件,考察了两种算法对信噪比S NR (signal to no i se rati o)为20 的相同信号分别进行1000次检测所获得的特征量z H ^z ] 的波动情况。其中,纵坐标为考察指标,是1000次检测实验中获得的1000个特征量的方差,横坐标为压缩感知系统的采样点数。 图1 OM P 检测算法与M P 检测算法特征量波动比较F i g .1T he compar i son of character i sti c quantit y fl uctuati on bet w een OM P andM P a l go rith m s 从图1可以看到,在H 1情况下,与M P 检测算法相 1962 仪 器 仪 表 学 报第31卷 比,本文提出的O M P 检测算法在各个采样点数下获得的特征量的波动均较小。 4 实验结果及分析 设我们关心的感兴趣信号s 长度N =256,由三个正弦分量叠加而成,信号时域波形如图2所示。该信号在频域是稀疏的,满足基于压缩感知信号检测问题对待检测信号的要求。噪声n 为加性白高斯噪声。压缩感知过程通过一个M @N 的观测矩阵5实现,在每次检测实验中,5是一个随机产生的元素满足高斯分布的矩阵,M 为压缩感知采样点数。实验中,先验概率P r (H 0)=P r (H 1)=1/2,检测成功率为2000次检测实验的统计结果。同时规定,检测成功率高于95%时,检测有意义,对应的检测阈值区间有效阈值区间;检测成功率低于95%时,检测无意义,对应的检测阈值区间为无效阈值区间,即检测成功率低于95% 的情况本文不予考虑。 图2 感兴趣信号s 的时域波形F ig .2The ti m e do m a i n w avefor m o f the si gna l 第一,考察在相同采样点数下,OM P 检测算法和M P 检测算法在各个检测阈值下的检测成功率情况。令采样点数M =50,信噪比SNR=20,算法迭代次数T =6,依据先验条件检测阈值选择范围为[2,4.5],阈值步进为0.1。图3给出了实验结果,由图可以看出在有效阈值区间内,O M P 检测算法的成功率大于等于M P 检测算法的成功率。同时还可以看到,O M P 检测算法有效阈值区间范围比M P 检测算法广阔,有利于检测阈值的估计。 第二,考察在相同检测阈值下,OM P 检测算法和M P 检测算法获得高检测成功率所需要的采样点数情况。令检测阈值为3.5,信噪比SNR =20,算法迭代次数T =6,采样点数M 变化范围为[30,100],步进为1。实验结果如图4所示,由图可以看出,在相同阈值下,与M P 检测算法相比,O M P 检测算法用较少的采样点数就可以获得较高的检测成功率,减少了采样系统的成本,降低了系统复杂性。此外,在相同实验条件下,表1给出了在其他一些有效阈值下,两种检测算法稳定获得高检测成功率所 需要的最少采样点数。由表1可以看到,在其他有效阈 值内,与M P 检测算法相比,O M P 检测算法同样具有较好的检测性能。同时还可以看到,OM P 检测算法使用较少的采样点就可以获得较广阔的有效阈值空间。 表1 其他阈值下两种算法稳定获得高检测成功率 需要的最少采样点数 T ab le 1 Under other thresholds ,th e sa mp li ng numb ers requ ired to get h i gh s uccess rate of detecti on for t wo algorit hm s 检测阈值 检测成功率(%) 稳定获得高检测成功率所需要的最少采样点数 M P OM P M P OM P 2.110010042392.310010055472.610010066453.199.910090463.69710094463.8<9599.9100603.9 <95 97 100 67 第三,考察在相同采样点数、相同检测阈值下,O M P 检测算法和M P 检测算法获得高检测成功率所允许的噪 第9期刘 冰等:基于正交匹配追踪的压缩感知信号检测算法1963 声强度情况。令采样点数M =50,检测阈值为3.5,算法迭代次数T =6,信噪比(S NR )变化范围为[5,30],步进为1。实验结果如图5所示,由图可以看出,与M P 检测算法相比,相同检测成功率下,OM P 检测算法允许的信噪比低,抗噪声能力强;对于某一确定信噪比的信号,OM P 检测算法获得的检测成功率高。 图5 检测成功率随信噪比的变化F i g .5T he success rate o f de tecti on v s .SNR 为了进一步证明算法的有效性,下面针对雷达系统中 的实际问题进行实验。在雷达系统中,线性调频信号是一种非常重要的信号形式,信号瞬时频带宽的特性虽然提高了雷达系统的目标检测及识别能力,却给信号采集及数据处理带来极大压力,如何使用较少的采集数据完成检测是一个关键技术。本实验分别应用MP 算法和O M P 算法检测某雷达信号,考察在相同检测成功率下两种算法需要的采样点数。该信号具有三个线性调频分量,混频后载波频率均为0,带宽分别为300MHz 、200MH z 、150MH z ,幅度分别为0.5、0.2、0.3,时宽为10L s ,所处环境信噪比为10。实验结果如图6所示,由图可以看出,相同检测成功率下,O M P 检测算法所需要的采样点数要少于M P 检测算法,因此,使用O M P 检测算法进行检测可以减轻接收系 统在采样及数据处理方面的压力。 图6 OM P 算法和M P 算法的采样点数比较F i g .6T he compar i son of sa m pli ng nu m bers bet w een OM P and M P a l go rith m s 从以上实验结果可以看出,由于O M P 检测算法在H 1情况下能够获得波动较小的特征量,因此在相同检测条件下的检测成功率、相同检测成功率下需要的采样点数、相同检测成功率下允许的噪声强度等方面要优于M P 检测算法。 5 结 论 本文提出一种基于正交匹配追踪的压缩感知信号检测算法。与基于匹配追踪的检测算法相比,本文算法基于正交匹配追踪思想在每次迭代中对作为判决依据的特征量进行修正,在感兴趣信号存在时,得到了波动较小的特征量,进而获得了更好的检测效果。实验结果表明,与M P 检测算法相比,本文提出的OM P 检测算法在提高检测成功率,所需采样点数、抑制噪声等方面有更好的性能。同时笔者认为,本课题还有很多内容值得继续研究, 例如最佳检测阈值预测、检测算法优化等。 参考文献 [1] DONOHO D L .Compressed sensi ng[J]. I EEE T ransac -tion on Info r ma ti on Theory ,2006,52(4):1289-1306. [2] CANDES E ,ROM BERG J ,TERENCE T.R obust uncer -ta i n t y pr i nciples :Exac t s i gna l reconstructi on from h i ghly i nco m plete frequency i nfor m a tion [J]. IEEE T ransacti on on Informa ti on T heo ry ,2006,52(2):489-509. [3] BARAN I UK R.A l ecture Compressi ve sensi ng[J].I EEE S i gnal P rocessi ng M agazi ne ,2007,24(4):118-121. [4] CANDES E ,TER E N CE T.N ear opti m a l si gnal recovery from rando m pro jecti ons :U n i versa l encodi ng strateg ies [J].IEEE T ransac tion on Infor m a ti on T heo ry ,2006,52(12):5406-5425. [5] C ANDES E ,ROM BERG J ,TERENCE T.Stable si gnal recovery from i ncom plete and i naccura te m easure m ents [J ]. Comm. Pure . A pp.l M at h , 2006, 59(8): 1207-1223. [6] HA PPUT J ,NOW AK R.S i gnal reconstructi on fro m no isy rando m pro jecti ons[J].IEEE T ransac tion on Infor m ati on T heory ,2006,52(9):4306-4048. [7] 李林,孔令富,练秋生.基于轮廓波维纳滤波的图像 压缩传感重构[J].仪器仪表学报,2009,30(10):2051-2056. L I L,KONG L F,L I AN Q S H.I mage co m pressed sens -i ng reconstruc tion based on contour l e t W i ener filte ri ng [J].Chinese Journal o f Sc ientific Instrument ,2009,30(10):2051-2056. [8] NEEDELL D ,TRO PP J A.CoSa M P:Iterati ve s i gna l re -covery fro m inco m plete and i naccurate sa m ples[J].A p - 1964仪器仪表学报第31卷 p.l Com PH ar m on ic A a,l2009,76(3):301-321. [9]练秋生,高彦彦,陈书贞.基于两步迭代收缩法和复 数小波的压缩传感图像重构[J].仪器仪表学报, 2009,30(7):1426-1431. L I AN Q S,GAO Y Y,CHEN S H https://www.wendangku.net/doc/3d13636755.html,pressed sens i ng i m age reconstruction based on t wo-ste P iterati ve shrinkag e and comp l ex w avelet[J].Ch i nese Journa l of Sc ientific Instru m ent,2009,30(7):1426-1431. [10]DAV ENPORT M,W AK I N M,BARAN I UK R.D etecti on and Esti m a ti on w ith Compress i ve M easure m ents[R]. H ouston TX U SA:R ice ECE D epart ment,2006:3-13. [11]HAU PT J,NOWAK https://www.wendangku.net/doc/3d13636755.html,pressed sa m pli ng f o r signa l detection[C].I EEE Int.Con.f on A coustics,Speech, and Signa l P rocessi ng(ICASSP),H ono lul u,H a w a i,i A pril2007,1509-1512. [12]DUARTE M,DAV E N PORT M,WAK I N M,et a.l Sparse si gnal de tection fro m i ncoherent pro jecti on[C].IEEE Int. Con.f on A coustics,Speech,and S i gnal P rocessi ng(IC- ASSP),T oulouse,France,M ay2006,305-308. [13]TRO PP J A,G ILBERT A C.S i gna l recovery fro m ran- dom m easurem ents via orthogonal m a tch i ng pursu it[J]. IEEE T ransac tion on In f o r m ati on T heo ry,2007,53 (12):4655-4666. [14]PAT I C,REZA IFAR R,KR IS HNA PRASED S.O rthogo- na l m atchi ng pursuit:recursive function approx i m a ti on w ith appli cations t o w ave let deco m po siti on[C].In27th Annua lA sil om ar Con.f on Signa l System s and Co m puter, 1993.[15]C ANDES E,W AK I N M.A n i ntroducti on to compress i ve sa m pli ng[J].I EEE Signa l P rocessing M agazi ne,2008, 25(2):21-30. 作者简介 刘冰,2005年于哈尔滨工业大学获得 学士学位,2007年于哈尔滨工业大学获得 硕士学位,现为哈尔滨工业大学自动化测 试与控制系博士研究生,主要研究方向为 压缩感知信号处理、自动测试技术等。 E-ma i:l li ubi ng6410@163.co m L iu B ing received bache l o r degree i n2005 and m aster degree i n2007bo t h from H arb i n Institute o f T echno-l ogy.H e i s currently a Ph. D.candidate i n H arbi n Insti tute o f T echno l ogy,H arbi n,China.H is m a i n research interests i nc l ude co m pressi ve sensi ng signa l processing and auto m atic test techno-l ogy,and etc . 付平,1999年于哈尔滨工业大学获得 博士学位,现为哈尔滨工业大学自动化测 试与控制系教授、博士生导师,主要研究方 向为图像处理,压缩感知,自动测试技术等。 E-ma i:l fup i ng@h https://www.wendangku.net/doc/3d13636755.html, Fu P ing received P h.D.from H arbi n Inst-i tute o fT echno l ogy i n1999.H e i s no w a professor and Ph.D.su-perv i sor i n A utom ati c T est and Contro lD epa rt m en t,H arbi n Inst-i tute of T echno l ogy.H i s m ain research i nterests i nclude i m age process i ng,compressive sensi ng and auto m atic test techno logy, and etc. 第10卷 第5期 信 息 与 电 子 工 程 Vo1．10，No．5 2012年10月 INFORMATION AND ELECTRONIC ENGINEERING Oct．，2012 文章编号：1672-2892(2012)05-0579-05 一种改进的用于稀疏表示的正交匹配追踪算法 王燕霞，张 弓 (南京航空航天大学 电子信息工程学院，江苏 南京 210016) 摘 要：稀疏表示理论在军事目标识别、雷达目标参数估计等领域应用越来越广，而目标信号的稀疏表示通常不唯一，因此产生了大量的稀疏表示算法。本文基于现有稀疏表示算法的研究，提出一种改进的正交匹配追踪(OMP)算法。首先采用非线性下降的阈值更快速地选择原子，确定备选原子集，提高了算法速度；其次用正则化的二次筛选剔除备选原子集中能量较低的原子，保证了算法精确度；并设置迭代停止条件实现算法的稀疏度自适应。实验结果表明，本文算法可以实现稀疏表示求解精确度和速度上的平衡，求解速度比基追踪(BP)算法快，精确度比OMP 、正则化OMP(ROMP)、基于自适应OMP 回溯(BAOMP)算法高。 关键词：过完备字典；稀疏表示；正交匹配追踪；正则化 中图分类号：TN850.6；TP753 文献标识码：A An improved orthogonal matching pursuit algorithm for sparse representation WANG Yan -xia，ZHANG Gong (College of Electronics and Information Engineering，Nanjing University of Aeronautics and Astronautics，Nanjing Jiangsu 210016，China) Abstract：Usually sparse representation of signal is not unique, which results in a large number of sparse representation algorithms. An improved Orthogonal Matching Pursuit(OMP) algorithm is proposed. The atoms are selected more quickly with nonlinear decline threshold and the set of alternative atoms is determined, which improves the algorithm speed. Regularized secondary screening can remove lower -energy atoms from the alternative atoms set to ensure the accuracy. A stop condition for iteration is preset to realize the adaptive sparsity of new algorithm. Simulation results show that, the improved algorithm can keep a balance between accuracy and speed for sparse solving with a faster speed than Basis Pursuit(BP) algorithm and a higher accuracy than OMP, Regularized OMP(ROMP) and Backtracking -based Adaptive OMP(BAOMP) algorithms. Key words：over -complete dictionary；sparse representation；orthogonal matching pursuit；regularized 稀疏表示理论在军事目标识别[1]、雷达目标参数估计[2]等领域的应用越来越广，2010年Vishal 和Nasser 等人基于科曼奇族前视红外数据库将稀疏表示用于军事目标的识别，稀疏求解的结果表明算法取得了较好的识别效果[1]。对于稀疏表示理论应用于各种目标信号处理来说，信号的表示应该能对自身不同性质，以及各性质间的差异提供明确信息，这就促进了信号在基于大量波形的过完备字典上的分解[1]。然而过完备库中的波形数远远超过信号的维数，因此它对给定信号的表示不是唯一的，由此产生了信号处理工作中大量的稀疏表示算法。 基于过完备字典的稀疏表示起源于20世纪90年代，Mallat 和Zhang 首次提出了匹配追踪(Matching Pursuit ，MP)算法来解决该稀疏分解问题[3?4]，通常这些算法可以分为3类：基于p l 范数正则化的方法、迭代收缩算法和贪婪追踪算法。基于p l 范数正则化的方法通过求解在重构条件下系数的p l 范数最小化来寻找稀疏解，此类比较典型的算法有基追踪(BP)[5]；迭代收缩算法首先要获得系数的初始集，然后迭代修正获得稀疏表示，早期的这类方法有噪声整形(Noise Shaping ，NS)[6]等；贪婪追踪算法力求从字典中选取与余量最匹配的原子作为信号的近似表示，并通过减去与该原子相关的分量来更新余量，此类算法研究的成果较多，典型的有MP [5],OMP [7],ROMP [8]及BAOMP [9]等。 收稿日期：2011-12-14；修回日期：2012-02-09 压缩感知重构算法之分段正交匹配追踪(StOMP) 分段正交匹配追踪(StagewiseOMP)或者翻译为逐步正交匹配追踪，它是OMP另一种改进算法，每次迭代可以选择多个原子。此算法的输入参数中没有信号稀疏度K，因此相比于ROMP及CoSaMP有独到的优势。 0、符号说明如下： 压缩观测y=Φx，其中y为观测所得向量M×1，x为原信号N×1（M< 2、分段正交匹配追踪(StOMP)Matlab代码(CS_StOMP.m) 代码参考了文献[4]中的SolveStOMP.m，也可参考文献[5]中的StOMP.m。其实文献[4]是斯坦福的SparseLab 中的一个函数而已，链接为https://www.wendangku.net/doc/3d13636755.html,/，最新版本为2.1，SolveStOMP.m在目录 SparseLab21-Core\SparseLab2.1-Core\Solvers里面。 1.function[theta]=CS_StOMP(y,A,S,ts) 2.%CS_StOMP Summary ofthisfunctiongoes here 3.%Version:1.0 writtenbyjbb0523@2015-04-29 4.%Detailedexplanationgoeshere 5.%y =Phi*x 压缩感知理论综述 摘要：信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来，指导信号采样的理论基础一直是著名的Nyquist采样定理，但其产生的大量数据造成了存储空间的浪费。压缩感知（Compressed Sensing）提出一种新的采样理论，它能够以远低于Nyquist采样速率采样信号。本文详述了压缩感知的基本理论，着重介绍了信号稀疏变换、观测矩阵设计和重构算法三个方面的最新进展，并介绍了压缩感知的应用及仿真，举例说明基于压缩感知理论的编解码理论在一维信号、二维图像处理上的应用。 关键词：压缩感知；稀疏表示；观测矩阵；编码；解码 一、引言 Nyquist采样定理指出，采样速率达到信号带宽的两倍以上时，才能由采样信号精确重建原始信号。可见，带宽是Nyquist采样定理对采样的本质要求。然而随着人们对信息需求量的增加，携带信息的信号带宽越来越宽，以此为基础的信号处理框架要求的采样速率和处理速度也越来越高。解决这些压力常见的方案是信号压缩。但是，信号压缩实际上是一种资源浪费，因为大量的不重要的或者只是冗余信息在压缩过程中被丢弃。从这个意义而言，我们得到以下结论：带宽不能本质地表达信号的信息，基于信号带宽的Nyquist采样机制是冗余的或者说是非信息的。 于是很自然地引出一个问题：能否利用其它变换空间描述信号，建立新的信号描述和处理的理论框架，使得在保证信息不损失的情况下，用远低于Nyquist 采样定理要求的速率采样信号，同时又可以完全恢复信号。与信号带宽相比，稀疏性能够直观地而且相对本质地表达信号的信息。事实上，稀疏性在现代信号处理领域起着至关重要的作用。近年来基于信号稀疏性提出一种称为压缩感知或压缩采样的新兴采样理论，成功实现了信号的同时采样与压缩。 简单地说，压缩感知理论指出：只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。在该理论框架 压缩感知重构算法之正则化正交匹配追踪(ROMP) 正交匹配追踪算法每次迭代均只选择与残差最相关的一列，自然人们会想：“每次迭代是否可以多选几列呢?”，正则化正交匹配追踪(RegularizedOMP)就是其中一种改进方法。本篇将在上一篇《压缩感知重构算法之正交匹配追踪(OMP)》的基础上给出正则化正交匹配追踪(ROMP)算法的MATLAB函数代码，并且给出单次测试例程代码、测量数M与重构成功概率关系曲线绘制例程代码。 0、符号说明如下： 压缩观测y=Φx，其中y为观测所得向量M×1，x为原信号N×1（M< 我将原子选择过程封装成了一个MATLAB函数，代码如下(Regularize.m)： 1.function [val,pos] = Regularize(product,Kin) 2.%Regularize Summary of this function goes here 3.% Detailed explanation goes here 4.% product = A'*r_n;%传感矩阵A各列与残差的内积 5.% K为稀疏度 6.% pos为选出的各列序号 7.% val为选出的各列与残差的内积值 8.% Reference:Needell D，Vershynin R. Uniform uncertainty principle and 9.% signal recovery via regularized orthogonal matching pursuit. 10.% Foundations of Computational Mathematics, 2009,9(3): 317-334. 11. productabs = abs(product);%取绝对值 12. [productdes,indexproductdes] = sort(productabs,'descend');%降序排列 13. for ii = length(productdes):-1:1 14. if productdes(ii)>1e-6%判断productdes中非零值个数 15. break; 16. end 17. end 18. %Identify:Choose a set J of the K biggest coordinates 19. if ii>=Kin 20. J = indexproductdes(1:Kin);%集合J 21. Jval = productdes(1:Kin);%集合J对应的序列值 22. K = Kin; 23. else%or all of its nonzero coordinates,whichever is smaller 24. J = indexproductdes(1:ii);%集合J 25. Jval = productdes(1:ii);%集合J对应的序列值 26. K = ii; 27. end 28. %Regularize:Among all subsets J0∈J with comparable coordinates 29. MaxE = -1;%循环过程中存储最大能量值 30. for kk = 1:K 31. J0_tmp = zeros(1,K);iJ0 = 1; 32. J0_tmp(iJ0) = J(kk);%以J(kk)为本次寻找J0的基准(最大值) 33. Energy = Jval(kk)^2;%本次寻找J0的能量 34. for mm = kk+1:K 35. if Jval(kk)<2*Jval(mm)%找到符合|u(i)|<=2|u(j)|的 36. iJ0 = iJ0 + 1;%J0自变量增1 37. J0_tmp(iJ0) = J(mm);%更新J0 38. Energy = Energy + Jval(mm)^2;%更新能量 39. else%不符合|u(i)|<=2|u(j)|的 40. break;%跳出本轮寻找，因为后面更小的值也不会符合要求 41. end 42. end 43. if Energy>MaxE%本次所得J0的能量大于前一组 44. J0 = J0_tmp(1:iJ0);%更新J0 45. MaxE = Energy;%更新MaxE，为下次循环做准备 46. end 47. end 48. pos = J0; 49. val = productabs(J0); 压缩感知重构算法之正交匹配追踪(OMP) 前面经过几篇的基础铺垫，本篇给出正交匹配追踪(OMP)算法的MATLAB函数代码，并且给出单次测试例程代码、测量数M与重构成功概率关系曲线绘制例程代码、信号稀疏度K与重构成功概率关系曲线绘制例程代码。 0、符号说明如下： 压缩观测y=Φx，其中y为观测所得向量M×1，x为原信号N×1（M< 2、正交匹配追踪(OMP)MATLAB代码(CS_OMP.m) [plain]view plaincopy 1.function [ theta ] = CS_OMP( y,A,t ) 2.%CS_OMP Summary of this function goes here 3.%Version: 1.0 written by jbb0523 @2015-04-18 4.% Detailed explanation goes here 5.% y = Phi * x 6.% x = Psi * theta 7.% y = Phi*Psi * theta 8.% 令 A = Phi*Psi, 则y=A*theta 9.% 现在已知y和A，求theta 10. [y_rows,y_columns] = size(y); 11. if y_rows 1. 信号的稀疏表示(sparse representation of signals) 给定一个过完备字典矩阵，其中它的每列表示一种原型信号的原子。给定一个信号y，它可以被表示成这些原子的稀疏线性组合。信号y 可以被表达为y = Dx ，或者 。字典矩阵中所谓过完备性，指的是原子的个数远远大于信号y的长度(其长度很显然是n)，即n< 压缩感知原理(附程序) 1压缩感知引论 传统方式下的信号处理，是按照奈奎斯特采样定理对信号进行采样，得到大量的采样数据，需要先获取整个信号再进行压缩，其压缩过程如图2.1。 图2.1 传统的信号压缩过程 在此过程中，大部分采样数据将会被抛弃，即高速采样后再压缩的过程浪费了大量的采样资源，这就极大地增加了存储和传输的代价。 由于带宽的限制，许多信号只包含少量的重要频率的信息。所以大部分信号是稀疏的或是可压缩的，对于这种类型的信号，既然传统方法采样的多数数据会被抛弃，那么，为什么还要获取全部数据而不直接获取需要保留的数据呢？Candes和Donoho等人于2004年提出了压缩感知理论。该理论可以理解为将模拟数据节约地转换成压缩数字形式，避免了资源的浪费。即，在采样信号的同时就对数据进行适当的压缩，相当于在采样过程中寻找最少的系数来表示信号，并能用适当的重构算法从压缩数据中恢复出原始信号。压缩感知的主要目标是从少量的非适应线性测量中精确有效地重构信号。核心概念在于试图从原理上降低对一个信号进行测量的成本。压缩感知包含了许多重要的数学理论，具有广泛的应用前景，最近几年引起广泛的关注，得到了蓬勃的发展。 2压缩感知原理 压缩感知，也被称为压缩传感或压缩采样，是一种利用稀疏的或可压缩的信号 进行信号重构的技术。或者可以说是信号在采样的同时被压缩，从而在很大程度上降低了采样率。压缩感知跳过了采集N 个样本这一步骤，直接获得压缩的信号的表示。CS 理论利用到了许多自然信号在特定的基ψ上具有紧凑的表示。即这些信号是“稀疏”的或“可压缩”的。由于这一特性，压缩感知理论的信号编解码框架和传统的压缩过程大不一样，主要包括信号的稀疏表示、编码测量和重构算法等三个方面。 对于一个实值的有限长一维离散时间信号X ，可以看作为一个N R 空间N ×1的维的列向量，元素为[]n ，n ,=1，2，…N 。N R 空间的任何信号都可以用N ×1维的基向量{}1 i N i =ψ的线性组合表示。为简化问题，假定这些基是规范正交的。把向量{}1i N i =ψ作为列向量形成N N ?的基矩阵ψ： =[12,,ψψ ? ,N ψ]，于是任意信号X 都可以表示为： X =ψΘ (2.1) 其中Θ是投影系数Θ=[],i i X θ=?ψ???构成的N ×1的列向量。显然，X 和Θ是同一个信号的等价表示，X 是信号在时域的表示，Θ则是信号在ψ域的表示。如果Θ的非零个数比N 小很多，则表明该信号是可压缩的。一般而言，可压缩信号是指可以用K 个大系数很好地逼近的信号，即它在某个正交基下的展开的系数按一定量级呈现指数衰减，具有非常少的大系数和许多小系数。这种通过变换实现压缩的方法称为变换编码。在数据采样系统中，采样速率高但信号是可压缩的，采样得到N 点采样信号X ；通过T X Θ=ψ变换后计算出完整的变换系数集合{}i θ；确定K 个大系数的位置，然后扔掉N K -个小系数；对K 个大系数的值和位置进行编码，从而达到压缩的目的。 由Candes 、Romberg 、Tao 和Donoho 等人在2004年提出的压缩感知理论表 压缩感知理论综述摘要：信号采样是模拟的物理世界通向数字的信息世界之必备手段。多年来，指导信号采样的理论基础一直是著名的Nyquist采样定理，但其产生的大量数据造成了存储空间的浪费。压缩感知(Compressed Sen si ng)提出一种新的采样理论，它能够以远低于Nyquist采样速率采样信号。本文详述了压缩感知的基本理论，着重介绍了信号稀疏变换、观测矩阵设计和重构算法三个方面的最新进展，并介绍了压缩感知的应用及仿真，举例说明基于压缩感知理论的编解码理论在一维信号、二维图像处理上的应用。 关键词：压缩感知；稀疏表示；观测矩阵；编码；解码 一、引言 Nyquist采样定理指出，采样速率达到信号带宽的两倍以上时，才能由采样信号精确重建原始信号。可见，带宽是Nyquist采样定理对采样的本质要求。然而随着人们对信息需求量的增加，携带信息的信号带宽越来越宽，以此为基础的信号处理框架要求的采样速率和处理速度也越来越高。解决这些压力常见的方案是信号压缩。但是，信号压缩实际上是一种资源浪费，因为大量的不重要的或者只是冗余信息在压缩过程中被丢弃。从这个意义而言，我们得到以下结论：带宽不能本质地表达信号的信息，基于信号带宽的Nyquist采样机制是冗余的或者说 是非信息的。 于是很自然地引出一个问题：能否利用其它变换空间描述信号，建立新的信号描述和处理的理论框架，使得在保证信息不损失的情况下，用远低于Nyquist 采样定理要求的速率采样信号，同时又可以完全恢复信号。与信号带宽相比，稀疏性能够直观地而且相对本质地表达信号的信息。事实上，稀疏性在现代信号处理领域起着至关重要的作用。近年来基于信号稀疏性提出一种称为压缩感知或压缩采样的新兴采样理论，成功实现了信号的同时采样与压缩。 简单地说，压缩感知理论指出：只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。在该理论框架 下，采样速率不再取决于信号的带宽，而在很大程度上取决于两个基本准则：稀疏性 压缩感知技术研究进展 摘要：信号采样是联系模拟信源和数字信息的桥梁.人们对信息的巨量需求 造成了信号采样、传输和存储的巨大压力. 如何缓解这种压力又能有效提取承载在信号中的有用信息是信号与信息处理中急需解决的问题之一. 近年国际上出现的压缩感知理论(Compressed Sensing,CS)为缓解这些压力提供了解决方法. 本文综述了CS 理论框架及关键技术问题, 并介绍了仿真实例、应用前景, 评述了其中的公开问题,对研究中现存的难点问题进行了探讨,最后对CS技术做了一下总结和展望. 关键词：压缩感知；稀疏表示；观测矩阵；编码；解码 Advances in Theory and Application of Compressed Sensing Abstract：Sampling is the bridge between analog source signal and digital signal. With the rapid progress of information technologies, the demands for information are increasing dramatically. So the existing systems are very difficult to meet the challenges of high speed sampling, large volume data transmission and storage. How to acquire information in signal efficiently is an urgent problem in electronic information fields. In recent year s, an emerging theory of signal acquirement. compressed sensing(CS) provides a golden opportunity for solving this problem. This paper reviews the theoretical framework and the key technical problems of compressed sensing and introduces the latest developments of signal sparse representation, design of measurement matrix and reconstruction algorithm. Then this paper also reviews several open problems in CS theory and discusses the existing difficult problems. In the end, the application fields of compressed sensing are introduced. Key words:compressed sensing;sparse representation; the observation matrix; coding;decoding 一、引言 在过去的半个世纪里，奈奎斯特采样定理几乎支配着所有的信号或图像等一种改进的用于稀疏表示的正交匹配追踪算法
分段正交匹配追踪算法StOMP
压缩感知理论综述(原创)
贪婪算法中ROMP算法的原理介绍及MATLAB仿真
贪婪算法中正交匹配追踪算法OMP的原理及仿真
mp&omp 匹配追踪 正交匹配追踪
压缩感知原理
压缩感知理论综述
压缩感知技术研究进展分析