资源描述：
《压缩感知重建算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
电子科技大学UNIVERSITYOFELECTRONICSCIENCEANDTECHNOLOGYOFCHINA专业学位硕士学位论文MASTERTHESISFORPROFESSIONALDEGREE论文题目压缩感知重建算法研究专业学位类别工程硕士学号201522040896作者姓名何明耀指导教师马凯学教授 分类号密级注1UDC学位论文压缩感知重建算法研究（题名和副题名）何明耀（作者姓名）指导教师马凯学教授电子科技大学成都林川副教授西南交通大学成都（姓名、职称、单位名称）申请学位级别硕士专业学位类别工程硕士工程领域名称电子与通信工程提交论文日期2018.04论文答辩日期2018.05学位授予单位和日期电子科技大学2018年6月答辩委员会主席赵青教授评阅人赵青教授吴明和副教授注1：注明《国际十进分类法UDC》的类号。 ResearchoncompressedsensingreconstructionalgorithmAMasterThesisSubmittedtoUniversityofElectronicScienceandTechnologyofChinaDiscipline:MasterofEngineeringAuthor:MingyaoHeSupervisor:Prof.KaixueMaSchool:SchoolofElectronicEngineering 摘要摘要压缩感知理论突破了传统香农定理的限制，压缩感知理论框架下的信号处理方法通过直接感知信号的关键信息的方式大大降低信号采样和恢复成本。压缩感知理论在很大程度上丰富了信号采样理论，为信号处理相关领域的研究拓宽了视野。该理论研究的核心内容主要包括信号的稀疏变换矩阵的设计、信号测量矩阵的构造以及压缩感知重建算法，其中高效稳定的重构算法是将压缩感知理论推向实践的关键环节，因此，对压缩感知重构算法的研究非常具有实际意义。本论文的研究正是基于此展开的，主要研究内容及创新工作如下：（1）对现有的常见的压缩感知重构算法进行了梳理，对贪婪类压缩感知重构算法进行了深入研究，从算法的计算复杂度和重构概率的角度，通过大量的仿真实验对各算法进行了定性分析。（2）摒弃确定性原子选择方式，在原子选择过程中引入了适度的随机性，提出了随机策略匹配追踪算法（RSMP）。该算法相较于多路径匹配追踪算法（MMP），不仅在数学上更加简单、编程方便，而且RSMP算法以单路径随机搜索的方式达到了与MMP算法多路径方式来扩大搜索范围的同样的目的。RSMP算法具有很强的“灵活”性，能够在每次迭代过程中，自适应的选择合适个数的原子，相较于gOMP算法，RSMP算法的输入参数更少、噪声鲁棒性更强且重建性能优势明显。（3）进一步RSMP算法适度的随机原子选择策略进行研究，结合遗传算法中选择算子的“择优”思想，提出了多种随机原子选择策略，并详述了原子选择步骤。大量的仿真实验表明这些随机的原子选择策略较传统的确定性原子选择策略对正确原子支撑集的检索能力更强。这种随机原子选择策略在一定程度上丰富了贪婪算法原子拓充的方式，为贪婪类算法原子选择策略提供了新思路。关键词：压缩感知，重构算法，自适应，随机原子选择I ABSTRACTABSTRACTCompressedsensing(CS)theorybreaksthroughthelimitationofthetraditionalShannonSamplingtheorem.,thesignalprocessingmethodundertheframeworkofcompressedsensingtheorygreatlyreducesthecostofsignalsamplingandrecoverybydirectlyperceivingthekeyinformationofthesignal.Thetheoryhasenrichedthesignalsamplingtheorytoalargeextentandbroadenedthehorizonofresearchinrelatedfields,whichhasgreatresearchvalueandapplicationprospect.ThecorecontentofCStheoryincludesthedesignofsparsetransformationmatrixofsignal,theconstructionofsignalmeasurementmatrixandcompressivesensingreconstructionalgorithm.Amongthem,thehighefficiencyandstabilityreconstructionalgorithmisthejointlinkwhichbringstheCStheoryintopractice.Therefore,theresearchontheCSreconstructionalgorithmhasabrightapplicationprospectandgreatscientificresearchvalue.Theresearchofthispaperisbasedonthis,andthefollowingshowsthecorecontentofmyresearchandinnovationwork:(1)Inthispaper,theexistingcommonCSreconstructionalgorithmhasbeencombed,thegreedyreconstructionalgorithmsweredeeplystudied,throughalargenumberofsimulationexperiments,thecomputationalcomplexityandreconstructionprobabilityofthosealgorithmhavebeenanalyzed.(2)Intheprocessofatomselection,astochasticstrategymatchingpursuitalgorithm(RSMP)isproposedbyabandoningthedeterministicatomicselectionmodeandintroducingappropriaterandomnessintheprocessofatomselection.ComparedtotheMultipathMatchingPursuit(MMP),thealgorithmisnotonlysimplerinmathematicsandconvenientinprogramming,butalsotheRSMPalgorithmachievesthepurposeofexpandingthesearchrangebyusingthesingle-pathrandomsearchmethod.RSMPalgorithmisflexibleandcanselecttherightnumberofatomsineachiteration.ComparedwiththegOMPalgorithm,RSMPalgorithmhaslessinputparameters,strongernoiserobustnessandbetterreconstructionperformance.(3)FurtherresearchontheappropriaterandomatomselectionstrategyinRSMPalgorithm,combinedwiththe‘preferred’ideaoftheselectionoperatorinthegeneticalgorithm,proposedavarietyofrandomatomselectionstrategies,anddetailedtheatomicselectionsteps.AlargenumberofsimulationexperimentsshowthattheserandomatomII ABSTRACTselectionstrategiesaremorepowerfulthantraditionaldeterministicatomicselectionstrategiesforcorrectatomsupportset.Tosomeextent,thisrandomatomicselectionenrichesthewayofatomicexpansionofgreedyalgorithmsandprovidesanewwayfortheatomicselectionstrategyofgreedyalgorithms.Keywords:compressivesensing,reconstructionalgorithm,adaptive,randomatomselectionIII 目录目录第一章绪论..........................................................................................................11.1研究背景及意义.......................................................................................11.2国内外研究现状.......................................................................................41.3本文的主要贡献与创新...........................................................................61.4本文研究内容及结构...............................................................................7第二章压缩感知重建算法....................................................................................82.1压缩感知理论基础...................................................................................82.1.1信号的稀疏表示............................................................................82.1.2信号观测........................................................................................92.1.3信号重构......................................................................................102.2贪婪类压缩感知重构算法......................................................................112.2.1正交匹配追踪算法.......................................................................112.2.2逐步正交匹配追踪算法..............................................................122.2.3正则化正交匹配追踪..................................................................132.2.4压缩采样匹配追踪算法..............................................................142.2.5子空间追踪算法..........................................................................152.2.6稀疏度自适应匹配追踪算法......................................................162.3仿真结果与分析.....................................................................................172.4本章小结.................................................................................................25第三章基于随机原子选择的匹配追踪算法研究..............................................263.1研究的出发点.........................................................................................263.1.1多路径匹配追踪..........................................................................263.1.2广义正交匹配追踪......................................................................303.2随机原子选择匹配追踪算法..................................................................323.2.1随机优化的优点..........................................................................323.2.2随机策略匹配追踪算法..............................................................32IV 目录3.3仿真结果与分析......................................................................................343.4本章小结.................................................................................................42第四章随机原子选择策略研究..........................................................................434.1随机原子选择策略.................................................................................434.1.1轮盘赌式原子选择策略..............................................................434.1.2具有排名的转盘式原子选择策略...............................................444.1.3锦标赛式原子选择策略..............................................................454.2仿真结果与分析.....................................................................................454.3本章小结.................................................................................................52第五章总结与展望..............................................................................................535.1全文总结.................................................................................................535.2未来工作的展望.....................................................................................53致谢........................................................................................................................55参考文献................................................................................................................56攻读硕士学位期间取得的成果............................................................................60V 第一章绪论第一章绪论1.1研究背景及意义在实际应用中，模拟信号通过采样技术转化为计算机可识别的数字信号进行处理。长期以来，香农（Shannon）采样[1]定理作为信号数字化的指导准则。香农采样定理指出：假设连续时间带限信号xt()的频谱范围为(−ff,)，那么信号xt()mm可以唯一由采样值xk[]=xkT()恢复，条件是采样率fT=1/，其中ff2。通常，ssssm最低采样频率ff=2称为“奈奎斯特频率(Nyquistrate)”。在香农采样理论指导下，sm信号获取及处理过程，一般都遵照图1-1进行：采样压缩传输解压原始信号采样信号压缩数据压缩数据重构信号存储重构图1-1传统信号获取与处理过程近些年来，随着现代科技快速发展，人类社会已经步入信息爆炸的大数据时代，通信、合成孔径雷达成像等领域对信号的采样的带宽要求不断提高，生物医学成像、微波遥感、智能遥控等领域对图像及视频的精度要求也越来越高，致使所需的数据存储空间也越来越大。无疑给数据的采集、存储和传输带来了巨大压力。香农采样[2]定理为模拟信号数字化奠定了基础，然而，香农采样定理存在如下不足：1.数据获取方面。香农采样定理指出采样频率必须大于或等于两倍的信号带宽才能保证准确恢复，随着模拟信号带宽越来越宽，需要更高的采样速率，将会直接导致硬件成本大幅度增加，甚至在技术上无法实现。2.数据存储和传输方面。传统信号获取和传输方法都是先按照香农采样定理采集数字信息，再把采集的数字信息压缩，最后按实际需要对压缩信息进行存储或传输。然而上述过程需要大量的时间压缩和空间储存数据，无疑增加了时间和存储空间的成本。面对现代社会的需要，基于香农采样定理获取数据的方式，宽带模拟信号的采集就需要很高的采样频率，对硬件设备的要求是一个极大挑战，在很大程度上制约了高速处理宽带信号的发展。所以人们就迫切的想要找到一种新的信号采集、数据处理的方法。一方面要求降低以香农采样为指导的数字信号处理所要求的采样频率；另一方面，采集到的信息没有信息丢失，能够精确重建原始信号。1 电子科技大学硕士学位论文2006年，D.Donoho、E.Candes及T.Tao等人提出并阐明了压缩感知[3-5]（CompressiveSensing，简记为CS）理论，该理论采用了全新的信号采样方式，缓解了高速处理可压缩信号的压力。CS理论指出，如果信号本身具有稀疏性或者可以通过某个稀疏基稀疏表示，再通过一个与稀疏基不相关的观测矩阵对变换所得的稀疏信号进行非线性观测，我们可以利用这些少量的观测信息对原始信号以较高的概率进行重建。以CS理论为指导的信号处理方式和传统的香农采样定理指导下的信号处理的方式有所不同，该理论下的信号处理流程如图1-2所示：第一步第二步第三步稀疏变换观测得到M维向量重构信号传输可压缩信号存储压缩采样图1-2CS框架下信号获取与处理可压缩信号首先在一组标准正交基下（如果信号本身具有稀疏性，这里的正交基取单位阵）得到原始信号的稀疏表示向量，再对稀疏表示向量进行非线性测量得到观测向量，最后通过重建算法利用这些少量的观测向量高概率的恢复原始信号。CS理论框架下的信号采集并不是针对原始信号的无损采样，该理论充分利用了信号的稀疏性，使得它对投影观测的数据的需求量远小于传统香农采样方法，满足了人们对庞大信息量的获取需求且消除了采样速率的高要求。信号的稀疏性是CS的前提条件，一个信号在一个域中的表示不稀疏，但是当其在另一个域中表示时就很可能是稀疏的。下面通过例1来说明信号通过合适的基来表示可以变为稀疏的，且通过这些少量的稀疏信息可以重构原始信号。例1本例给出点击数字“2”时产生的时域信号[6]，是为了说明仅仅利用少量的非零信息可以还原原始信号：xt()sin(1394)sin(3266)=+tt用3500Hz的频率对信号进行采样，图1-3(a)是信号本身各元素值，信号杂乱且不稀疏。图1-3(b)是信号在频域中的表示系数，系数仅在个别地方有少量的幅值较大的元素，其他元素都接近于0，显然在频域中，它具有稀疏性。利用频域中幅值最大的前5%的系数恢复原信号，其他元素置0，所得的重建信号如1-3(c)所示，重建恢复的信号与原始信号非常接近。重建信号和原始信号在幅度上的差值如图1-3(d)。2 第一章绪论(a)(b)(c)(d)图1-3信号重构及误差。(a)原始信号；(b)信号在频域下的系数；(c)恢复信号；(d)误差由图1-3可以看出，对于可压缩信号，仅利用少量“关键”信息就可以准确的重建原始信号。CS框架下的信号获取与处理方式利用了上述特性，直接感知信号的主要信息，从而大大降低信号采样和恢复成本。该理论在很大程度上丰富了信号采样理论，拓宽了相关领域研究的视野，具有广阔的研究前景。自从CS理论于2006年由Candes，Tao和Donoho等提出以来，基于该理论的应用便层出不穷，在很多领域产生了举足轻重的作用。Gurbuz等[7]充分利用了目标空间的稀疏性，将CS理论应用于探地雷达的信息采集和成像中；莱斯大学通过光域压缩方式构造了具有更宽的光谱范围适用性的单像素成像相机，该相机相较于传统数码相机具有价格低廉、结构简单、体积小的优势[8]；JohnWright[9]等人将压缩感知理论成功的运用到目标跟踪领域，通过人脸样本数据库训练得到样本字典，进行人脸识别；2010年，压缩感知被运用在步进频连续波（SFCW）探地雷达3 电子科技大学硕士学位论文（GPR）中[10]，保证恢复效果相同的同时，增加了SFCW-GPR的采集速度，解决因雷达宽带扫描造成SFCW系统在采集时间上产生的缺陷；MasoumA等人利用信号之间的空间相关性，将压缩感知运用到无线传感器网络中[11]；Kurniawan等人建立了CS_SFCW雷达样机，实现了2cm的范围分辨率[12]；Mechery针对水下信道的稀疏多径的特点，将压缩感知框架应用于水下信道系数估计[13]。在国内，国家自然基金对以压缩感知为主题的资助逐年递增，众多优秀学者纷纷参与对压缩感知的研究工作之中。石光明等人针对压缩感知的理论模型进行了深入研究，并对应用前景进行了展望[14]；余慧敏等人利用压缩感知理论进行探地雷达的单道数据获取，并提出了随机孔径压缩感知三维成像方法，以少量的测量孔径和少量的测量数据获得了理想的成像效果[15]；XiaoyeJiang[16]等人通过设计超完备基和稀疏表示的组合结构，对属性的不确定性进行建模，并将该模型应用于视频传感器网络进行目标跟踪；JianfeiChen等人将压缩感知理论应用于近场被动毫米波合成孔径成像系统中，减少了接收天线的个数同时降低了系统复杂性[17]；KexinTian等人将压缩理论应用于超宽带信道估计中，通过超宽带信号的先验知识改变测量矩阵消除噪声折叠现象[18]。1.2国内外研究现状重构算法是将压缩感知理论应用到实践中的重要一环，然而为保证信号的准确重建需要考虑多种因素，如怎样设计观测矩阵使得信号的表示最为稀疏、如何降低噪声干扰对信号重构影响以及如何提高算法的运算速度和求解精度等。针对各种实际应用的需要，不同的重建算法不断的被改进和优化。目前，压缩感知重构算法按照求解方式可以分为三类：（1）组合算法；（2）基于l范数的凸优化；（3）基于l范数的贪婪算法。10组合算法是由统计学、计算机科学领域的研究者提出的用于解决稀疏信号重构问题[19]。组合算法的特点是其本质思想是针对信号进行高度结构化采样，由群测试的方式快速获得信号的支撑集。组合算法中具有代表性的算法有傅里叶采样算法[20]和链式追踪算法[21]等。凸优化算法用于解决凸优化问题[22]，基追踪（BP）[23]算法是解决凸优化问题的经典算法。基追踪算法将优化问题中的l范数最小化的求解问题变为了l范数的01最小化问题，使得求解问题从非凸问题转变为了凸问题，这样就可以使用线性规划的方法对问题进行求解。基追踪去噪算法（BPDN）源于BP思想，主要用于解决含噪目标信号的重建问题,在部分支撑集的先验信息已知的情况下，BPDN算法可以进一步被修正，ModifiedBPDN[24]算法对重建误差进行约束，并且可以计算重建4 第一章绪论误差，当支撑集的未知部分比较小的时候，ModifiedBPDN算法的误差界远小于BPDN算法。梯度投影法（GP）[25]适用于极大规模的数据采集逆问题，当处理对象为平滑凸函数且满足Lipschitz梯度连续时，GP以函数中某点导数的正负指引方向，以梯度大小为标准自适应变步长地收敛到最优点。而后为了加快收敛速度，在[26]GP的基础上又相继出现了迭代收缩阈值算法（ISTA）和快速迭代收缩阈值算法（FISTA）[27]。贪婪算法采用迭代的方式逐步搜索获得原子的支撑集。贪婪算法中最典型算法是正交匹配追踪（OMP）[28]算法，该算法相较于BP类算法重建速度优势明显且实施成本低。OMP算法每次迭代均只选择与残差最相关的一列，依次迭代添加原子来拓充估计值支撑集，然而OMP算法随着信号稀疏度的增加，信号重构重构过程缓慢。分段正交匹配追踪（StOMP）[29]和正则化正交匹配追踪（ROMP）[30]通过每次迭代选择多个原子，相较于OMP大大减小了迭代次数。他们拥有远低于BP算法的计算复杂度，然而他们准确重建需要更多的测量次数且缺少准确重建的证明。压缩采样匹配追踪（CoSaMP）[31]和子空间追踪（SP）[32]结合了回溯的思想寻找原子的支撑集。他们的理论重建质量与线性规划相当且具有低的重建复杂性，然而SP和CoSaMP对信号进行重建时都假设稀疏度K已知，然而在实际应用中稀疏度信息常常是很难获取的。在OMP算法和SP算法的基础上产生了稀疏度自适应匹配追踪（SAMP）算法[33]，该算法在不知道信号稀疏度的情况下，可以准确重建原始信号。ThongT.Do[33]等人在数学上证明了SAMP具有噪声鲁棒性和高重建精度，在稀疏度相同情况下，文献[33]对多个贪婪算法对不同类型信号重建概率和采样次数关系进行仿真实验，结果表明SAMP算法具有良好的恢复性能，尤其是在高斯稀疏信号的重建上，在多个重构算法中SAMP算法性能最优。然而SAMP算法的初始原子集大小s一旦设定，第j代所选择的原子集大小就为js，当js接近稀疏度K时，算法就会有很好的重建效果。然而s有可能远小于稀疏度K，这样会增加迭代次数，步长设置的太大则会影响重建准确率。广义正交匹配追踪（gOMP）[34]算法是OMP的改进算法的一种，该算法思想简单，只是通过在每次迭代多选几个原子的方式来改善OMP算法的性能，仿真结果表明该算法较其他改进型算法有着良好的重建效果。多路径匹配追踪（MMP）算法[35]通过保留多个较可靠的原子支撑集的方式来增加获取正确原子支撑集的概率。该算法结合树形结构方式完成组合方法和贪婪算法巧妙的嫁接。树形结构的每条支路表示一种候选原子集合，树形结构的每一层原子根据测量矩阵和残差之间的相关度进行排序，以最小化残差为指导，不断的构建树形结构的子节点，直到所构建的树形结构的深度和信号稀疏度相同时，不再延展树形结构；计算每个支路的残差，选择残差最小的5 电子科技大学硕士学位论文支路对应的原子集合重建原始信号。稀疏度与步长自适应的正则化匹配追踪（SSARMP）算法[36]在迭代前对信号稀疏度进行了预估计，大大减少了算法的迭代次数；同时加入了变步长条件使得算法可以在迭代过程中自适应变换步长，最后在原子筛选过程正则化使得算法可以更精确找到目标原子。1.3本文的主要贡献与创新CS理论将采集信息的技术负担从传感器转移到处理器上，因此稳定、快速且鲁棒的重建算法是将CS理论从理论推进到实践的关键。本文的相关研究就是在此背景下展开的，首先，对现有经典的贪婪类算法进行梳理，列出了详细的算法流程，同时通过大量的仿真实验对算法重建性能进行了定性分析；其次，对多路径匹配追踪算法和广义正交匹配追踪算法的原子选择进行深入剖析，总结了原子选择方法对算法重建性能的影响，从中得到启发，将适度的随机性引入原子选择过程中，提出了随机策略匹配追踪算法，并在此基础上提出了多种随机原子选择策略，大量仿真实验表明这种适度的随机原子选择有着明显的效果。本文的主要贡献及创新如下：1.对压缩感知现有的常见重建算法进行了梳理，着重介绍了贪婪类算法的原理和流程，并总结了各贪婪类算法的优缺点。2.提出了随机策略匹配追踪算法（RSMP）。RSMP算法最大的创新在于该算法在进行原子选择时采用随机原子选择策略，使得RSMP算法优势明显。一方面，该算法的随机策略，增大了支撑集中原子的多样性，使得RSMP算法以单路径方式可以达到多路径匹配追踪（MMP）的目的；另一方面，使得该算法更加“灵活”，能够在每次迭代过程中，自适应的选择合适个数的原子，消除了广义正交匹配追踪算法（gOMP）对预定义值L的依赖。大量仿真实验表明本文所提出的RSMP算法对高斯信号在不同环境下的重建（有噪和无噪环境）有着和MMP算法相比拟的重建性能，对于0-1信号在不同环境下的重建比MMP算法更优；相较于gOMP算法，RSMP算法的输入参数更少、噪声鲁棒性更强且重建性能优势明显。3.对随机原子选择策略进行研究，结合遗传算法中三类选择算子“择优”思想，将该思想成功的引入了随机原子选择方法中。将随机原子选择策略用于RSMP算法的选择原子过程中，大量仿真对比实验表明这几种随机原子选择方式相较于确定性原子选择方式（gOMP算法）对于正确原子支撑集的搜索能力更强，且不需要设定任何阈值参数或增加控制参量。该工作丰富了贪婪算法原子拓充的方式，为贪婪类算法的原子选择方式提供了新思路。6 第一章绪论1.4本文研究内容及结构本文结构安排如下：第一章：绪论。简要的介绍了压缩感知理论的发展和基于压缩感知理论的信号处理的框架流程；同时对压缩感知算法研究现状进行了梳理。第二章：压缩感知重建算法。介绍了压缩感知理论的理论基础，对贪婪类重建算法进行研究，给出了OMP算法、StOMP算法、ROMP算法、CoSaMP算法、SP算法和SAMP算法的算法流程，通过仿真实验对这些算法进行了对比和分析。第三章：基于随机原子选择的匹配追踪算法研究。首先对多路径匹配追踪算法（MMP）和广义正交匹配追踪（gOMP）的原子选择进行深入剖析，分析了它们的优点与不足，总结了原子选择方法对算法重建性能的影响，摒弃了确定性原子选择的方式，将适度的随机选择引入原子支撑集扩充的过程中，提出了一种随机策略匹配追踪算法（RSMP），通过仿真实验比较了OMP算法，MMP算法，gOMP算法和RSMP算法的重构性能及噪声鲁棒性。第四章：随机原子选择策略研究。结合遗传算法中三类选择算子“择优”思想，提出了三种随机原子选择策略。最后通过大量仿真实验比较了它们对不同信号的重建性能及鲁棒性。第五章：总结和展望。简要的总结了本文研究内容，并对压缩感知重建算法可能的改进方式进行了展望。7 电子科技大学硕士学位论文第二章压缩感知重建算法2.1压缩感知理论基础由Donoho和Candes[3]提出的CS理论表明，在不满足香农采样定理的要求下，利用极少量的采样数据来逼近原始完整信号是可能的。信号的稀疏表示就是将原始信号用“简洁的语言”表达，它是CS理论的必备条件。首先，利用欠定（扁）的观测矩阵获取原始信号信息，这里每个观测值并不是信号本身，在数学上这些观测值可以解释为是被测信号的组合函数；然后再采用CS重建算法在概率层面上对信号进行重建[37]。传统香农采样和CS的关系如表2-1所示。表2-1香农采样与压缩感知的对应关系[37]考察标准香农采样CS压缩采样必备条件信号带宽信号可压缩/稀疏采样方式均匀等间隔全局、随机采样规则香农采样规则非相关测量矩阵重建信号方法傅里叶变换非线性优化利用CS进行目标信号的重建必须满足以下3个条件：（1）信号x本身稀疏或者可被压缩；（2）感知矩阵和信号不相干；（3）选择合适重建算法，实现问题的求解。研究CS理论的主要工作可被归纳为：信号的稀疏表示、观测矩阵的构造以及重建算法的设计三个方面[38]。2.1.1信号的稀疏表示N对任意无噪信号x，可以用一组标准正交基=|iN=1,2,...,的线性i组合来表示：Nx=ii=(2-1)i=1=xT其中，ii,为稀疏表示系数，=x表示稀疏表示系数矢量，=i|iN=1,2,...,是稀疏表示正交基。x代表了信号的时域表示，代表了信号在域中的表示。表示向量0中不为0的元素的个数，当=KK()N时，称信号x是K-稀疏的，K表示信08 第二章压缩感知重建算法号x的稀疏度。式(2-1)代表了信号x的稀疏表示。按照上述传统方式将一个信号用一组正交基的线性组合表示或者逼近，这种表示在数学中看似优雅，但是在实际应用中却并不高效。通常，通过增加基向量的个数把完备基变成过完备基，增加“词汇量”使得原始信号的表示更为稀疏。这种过完备的基就是“稀疏字典”。利用稀疏字典中的原子的线性组合估计原始信号，稀疏表示的问题实际上就是稀疏约束下测量信号与估计信号间的拟合问题。2.1.2信号观测如果信号x在域中K-稀疏，由CS理论，可以用一个与不相关的矩阵MNN(MN)将信号线性表示，观测向量y由下式表示：yx==(2-2)其中称为观测矩阵，定义MN维矩阵=为CS感知矩阵，CS线性测量过程如图2-1所示yxxM1MN图2-1CS线性测量过程向量y表示稀疏系数在传感矩阵A的观测下的测量值。当A满足约束等距条件，则可以通过最优l范数式(2-3)来求解，再代入式(2-1)中就可获得原始信0号。稀疏系数的求解式为=ˆargmins.t=y(2-3)0式中为向量的l范数，表示向量的非零项个数。Candes、Tao和Donoho00等指出，如果要准确恢复K-稀疏的信号x，测量次数必须满足M=OK(lg())N，且传感矩阵满足约束等距性质（RestrictedIsometryProperty，RIP）[39]。RIP的描述如下，如果存在01，使得k222(1−)||||||xx||(1+)||||x(2-4)kk222其中xx:||||xK，对任意的K-稀疏信号x均满足(2-4)式，则矩阵满k09 电子科技大学硕士学位论文足K阶约束等距性质，表示矩阵的约束等距常数。k如果矩阵满足2K阶约束等距特性，则式(2-4)可以解释为：任何一对K阶稀疏向量经过矩阵的线性变换后，它们的欧几里得距离几乎保持不变。也就是说，对具有稀疏度K的信号S和S，有如下描述：12222(1−kk)||S1−S2||||2(S1−S2)||2(1+)||S1−S2||2(2-5)因而，经过矩阵的变换后，具有相同稀疏度的信号S和S可以被稳健的区12分开。满足上述关系的向量x的选取是任意的，因此验证矩阵的RIP特性非常困难。有研究表明感知矩阵=满足约束等距性的充分条件是测量矩阵的行与稀疏矩阵的列相互之间不能互相线性表出[40]，并且当测量矩阵为高斯随机矩阵[41]、托普利兹矩阵[42]、局部哈达玛矩阵[42]或贝努利随机矩阵[43]的时候，感知矩阵能以较大概率满足RIP条件。2.1.3信号重构重构算法是压缩感知的核心内容，高效稳定的重构算法更是将压缩感知理论推向实践的关节环节。信号的重构是通过求解问题(2-2)的逆问题获得稀疏表示系数，再通过(2-1)式重建原始信号x。MN由于传感矩阵是一个扁阵，因此由观测向量y重建原始信号x是求解一个病态方程的过程，该方程的解的个数有无数多个，很难重建原始信号。但是正是由于x具有稀疏性使得上述病态问题的求解成为可能，Donoho等人[39]通过理论推导证明了解的唯一性。测量信号y可以看成是传感矩阵的原子的线性组合，是线性组合的系数。恢复稀疏系数可以通过l范数优化的数学方法求解，信0号重构就是解决如下的最优化问题min，s.t=y(2-6)0因求解式(2-6)的数值计算不稳定，且上述问题是一个NP-hard的问题，通常将上述问题转化为基追踪(BasisPursuit，简称为BP)问题求解min，s.t=y(2-7)1N其中，=，代表向量的l范数。Candes和TerenceTao在文献[44]1i1i=1中证明了当观测矩阵满足RIP条件时，(2-6)式和(2-7)式是等价的。式(2-6)是一个常见的凸优化问题，可以转化为线性规划问题进行求解，也可采用内点法，同伦算10 第二章压缩感知重建算法法以及梯度投影方法求解。压缩感知（CS）技术是一种新兴的信号处理技术，在该理论框架下获得的原始信号采样率远远低于基于传统的奈奎斯特抽样准则的采样率，且CS技术采用边采样边压缩的方式相较于传统算法很大程度上节约了存储空间且降低了计算复杂度。因此，该算法一经提出便受到人们的广泛关注，其中重建算法的设计是CS的研究重点，它决定了能否把CS理论成功的应用到实际中去。贪婪算法是CS重构算法中的一大类，该算法具有结构简单、计算复杂度低的优点，使得该算法受到广大研究人员的重视。2.2贪婪类压缩感知重构算法贪婪算法主要分为自上而下与自下而上两大类[33]。自下而上类方法通过迭代的方式逐步拓充原子支撑集，如正交匹配追踪（OMP）算法、正则化正交匹配追踪（ROMP）算法和分段正交匹配追踪（StOMP）算法；自上而下的方法在迭代求解之前假定一个初始解，并结合回溯的思想剔除不可靠原子以保证支撑集的正确性，最后通过最小二乘法得到最终解，如子空间追踪(SP)算法、压缩采样匹配追踪（CoSaMP）算法。贪婪类算法包含两个基本步骤：原子的选择和支撑集的更新。通过余量r与观测矩阵的列的内积计算相关系数u=uuj|j=rk−1,j=1,2,...(2-8)初始余量ry=。选择原子集J，更新支撑集SSJ=，采用最小二乘法得0kk到近似解†=y(2-9)kSk††代表的伪逆，其中=()。最后更新余量SkSkSkSkSkSkry=−(2-10)kSkk2.2.1正交匹配追踪算法正交匹配追踪（OrthogonalMatchingPursuit，简称为OMP）算法[28]，在每次迭代中，OMP算法只选择与残差最相关的原子拓充原子支撑集，正交化选中原子并计算信号在这些正交原子张成空间内的分量和残差，不断重复上述过程直到满足停止条件时结束迭代。正交匹配追踪算法将每次选中的原子都作了正交化处理，所以同一个原子不11 电子科技大学硕士学位论文会被选中两次。OMP算法最多需要K次迭代就可以收敛，其中K是原始目标信号的稀疏度，然而该算法在每次循环中需要进行额外的正则化运算。OMP的运算复杂度为OMNK()，OMP算法流程如表2-2所示。表2-2OMP算法流程表输入感知矩阵：MNM观测值：y稀疏度：K迭代1.初始化：初始迭代次数t=1；残差ry0=；信号估计初值ˆ=0；索引集=0；0匹配矩阵=；02.拓充原子支撑集t：满足t=argmaxrat−1,j，aj表示的第j列jN=1,2,...3.支撑集集合更新：=tt−1t；对匹配矩阵更新：=tt−1at−14.信号稀疏表示系数估计值更新：ˆ=argminyy−=(TT)tttttt−15.残差更新：r=−yˆ=−y(TT)yttttttt6.更新迭代次数，检验是否迭代停止：tt=+1，若tK，则返回第2步；否则进入第7步7.估计ˆ：集合t中存放非零项位置，ˆ中对应的非零值为最终迭代求得的ˆt输出信号稀疏表示系数估计ˆOMP算法为达到减少了迭代次数的目的，在求解过程中将选择的所有的原子作正交化处理来保证迭代的最优性。但是，在原子的选择过程中OMP算法每次的迭代只选取一个最相关的原子来拓充索引集合，这种逐个搜寻原子支撑集的方式会导致重构时间代价很大。特别是在K和M不断增加的情况下，运算时间会大幅度增加。2.2.2逐步正交匹配追踪算法为克服OMP在重建信号规模大且不是特别稀疏的情况下，运算量大的弊端。Donoho等改进了OMP算法，并在此基础上提出了逐步正交匹配追踪算法（StagewiseOrthogonalMatchingPursuit，简称为StOMP）[29]，基本思想与OMP非常类似，每次迭代过程中StOMP算法进行原子选择采用如下标准，在每次迭代过程中直接从冗余字典中选取一个原子集合u=uuj|j=rt−10,aj,1jN,J=ju|jTh(2-11)其中Th=t，=r/M,2t3。在此集合中的原子均属于残差与nnnn−12n12 第二章压缩感知重建算法冗余字典的列相关性大于一定阀值的集合，再基于上述原子集合进行残差更新。OMN(ln)NStOMP的计算复杂度为，该算法流程表如表2-3所示。表2-3StOMP算法流程表输入传感矩阵：MNM观测值：y迭代次数：S阈值：ts迭代1.初始化：初始迭代次数t=1；残差ry0=；信号稀疏表示系数初值ˆ=0；索引集0合=；匹配矩阵=；002.拓充原子支撑集：u=uuj|j=rt−1,aj,1jN，满足J0=ju|jTh；3.支撑集集合更新：=tt−10J；匹配矩阵更新：=tt−1at；若=tt−1，迭代停止直接进入第7步；−14.信号稀疏表示系数估计值更新：ˆ=argminyy−=(TT)；tttttt−15.残差更新：r=−yˆ=−y(TT)y；ttttttt6.更新迭代次数，检验是否迭代停止：tt=+1，若tS，则返回第2步；如果tS或者rt=0停止迭代进入第7步。7.估计ˆ：集合t中存放非零项位置，ˆ中对应的非零值为最终迭代求得的ˆt输出信号稀疏表示系数估计ˆStOMP算法在每次迭代过程中选取了与残差相关性大于一定阀值的原子集合拓充原子支撑集，一定程度上提高了运算速度。但是，阈值的设置对准确的原子支撑集的搜索有很大影响。本章在2.3节进行了仿真实验，比较了不同稀疏度下阈值的取值对重建结果的影响。2.2.3正则化正交匹配追踪Neeldell和Vershynin等对OMP算法进行了改进，摒弃原OMP算法直接选择与残差最相关的原子的支撑集拓充方式，采用选择相关性最大且能量分布近似的K个原子的方式来拓充原子支撑集。在OMP基础上提出了正则化正交匹配追踪（RegularizedOrthogonalMatchingPursuit，简称为ROMP）[30]算法。ROMP算法的计算复杂度和OMP算法一致均为OMNK()，该算法流程表如下表2-4所示。13 电子科技大学硕士学位论文表2-4ROMP算法流程表输入传感矩阵：MNM观测值：y稀疏度：K迭代1.初始化：初始迭代次数t=1；残差ry0=；信号稀疏表示系数初值ˆ=0；索引集0合=0；匹配矩阵=02.鉴定：u=uuj|j=rt−1,aj,1jN；如果uK0，则列序号集合Ju0=supp(K)；如果uK，则J0中存放u中所有原子的列序号；03.正则化：找出满足ui()2()uj，ij,J0；选择所有满足要求的J0中，maxu|J02对应的那组J；04.支撑集更新：=J,,=ajJ；tt−−10tt1j0−15.信号稀疏表示系数估计值更新：ˆ=argminyy−=(TT)；tttttt−16.残差更新：r=−yˆ=−y(TT)y；ttttttt7.更新迭代次数，判断迭代终止条件：tt=+1，如果tK，则返回第2步；如果tK或t02K或者rt=0，则迭代停止并进入第8步；8.估计ˆ：集合t中存放非零项位置，ˆ中对应的非零值为最终迭代求得的ˆt输出信号稀疏表示系数估计ˆROMP算法和OMP算法最大的不同之处它在每次迭代中都进行两次原子的筛选，第一次筛选是根据残差和备选原子集中原子的相关性为准则，从字典中选取多个原子来拓充原子索引候选集，二次原子筛选是在候选集中通过正则化方法优选出满足正则化条件的原子集合，再将这个原子集合加入最终原子索引的支撑集。2.2.4压缩采样匹配追踪算法压缩采样匹配追踪算法（CompressiveSamplingMatchingPursuit，简称为CoSaMP）[31]算法在OMP算法的基础上引入回溯思想，在每次迭代都从待选原子集合中选择一定数量与残差较相关的原子，并以这些原子与观测值之间的相关度为准则剔除部分与观测值相关度较低的原子，提高了算法效率。CoSaMP算法保证了候选集合中原子个数最多不超过3K，每次最多剔除2K个原子，以保证支撑集OMN()中有K个原子（其中K为迭代步长）。CoSaMP的算法的运算复杂度为，该算法流程如表2-5所示。14 第二章压缩感知重建算法表2-5CoSaMP算法流程表输入传感矩阵：MNM观测值：y稀疏度：K迭代1.初始化：初始迭代次数t=1；残差ry0=；信号稀疏表示系数初值ˆ0=0；支撑集集合=；匹配矩阵=；002.鉴定：u=uuj|j=rt−1,aj,1jN,令Ju02=supp(K)；3.原子候选集更新：令C=J,,=ajJ；tt−−10tt1j0−14.信号稀疏表示系数估计值更新：ˆ=argminyy−=(TT)；tttttt5.更新支撑集合：令ˆtk=suppˆtk，将对应的t中的K列用tk表示；对应tk的索引序号用表示，更新集合=；tkttk−16.残差更新：r=−yˆ=−y(TT)y；ttktktktktktk7.更新迭代次数，检验是否迭代停止：tt=+1，如果tK，则返回第2步；如果tK或残差rt=0，则迭代停止并进入第8步；8.估计ˆ：集合t中存放非零项位置，ˆ中对应的非零值为最终迭代求得的ˆt输出信号稀疏表示系数估计ˆCoSaMP算法每次迭代中将一次性选择多个原子，且最终用来重建原始信号的支撑集大小是确定的，因此在迭代过程中要不断的选中原子的同时剔除部分先前选中的原子。2.2.5子空间追踪算法子空间追踪算法（SubspacePursuitAlgorithm,简称为SP）[32]的基本思想和CoSaMP算法的基本思想是一致的，同样引入了回溯的思想，在得到支撑集之前先建立一个原子的候选集，之后再从候选集中舍弃不需要的原子，形成最终支撑集。。SP算法的运算复杂度为OMN(log)K，该算法流程如表2-6所示。通过对比表2-5表2-6可知，SP算法和CoSAMP算法的最大不同点就在于选择新原子加入支撑集的方式上。CoSAMP算法在每次迭代过程中新增2K个与残差相关性最大的列来拓充原子支撑集，SP算法改变了新增原子个数，每次迭代只选择K列原子，因而SP算法的具有更高的计算效率，相较于CoSAMP算法SP算法的约束等距收敛条件更容易满足。15 电子科技大学硕士学位论文表2-6SP算法流程表输入传感矩阵：MNM观测值向量：y稀疏度：K迭代1.初始化：初始迭代次数t=1；残差ry0=；信号稀疏表示系数初值ˆ0=0；支撑集索引集合=；匹配矩阵=；002.判别：u=uuj|j=rt−1,aj,1jN；令Ju0=supp()k；3.原子候选集更新：令C=J,,=ajJ；tt−−10tt1j0−14.信号稀疏表示系数估计值更新：ˆ=argminyy−=(TT)；tttttt5.原子支撑集合更新：令ˆtk=suppˆtk，将对应的t中的K列用tk表示；对应tk的索引序号用表示，更新集合=；tkttk−16.更新残差：r=−yˆ=−y(TT)y；ttktktktktktktt−17.更新迭代次数，检验是否迭代停止：如果rr，令=并退出迭代进22tt−1入第8步；否则tt=+1，返回第2步；8.估计ˆ：集合t中存放非零项位置，ˆ中对应的非零值为最终迭代求得的ˆt输出信号稀疏表示系数估计ˆ2.2.6稀疏度自适应匹配追踪算法稀疏度自适应匹配追踪算法（SparsityAdaptiveMatchingPursuit，简称为SAMP）[33]结合了上述算法的优点，延用了StOMP的分段的方式逐步拓充原子的支撑集，并使用类似CoSaMP以及SP中回溯的方式对原子进行挑选获取最终支撑集。SAMP算法流程如表2-7所示。从SAMP流程表2-7中可以看出，当步长S等于1的时候，SAMP算法类似于OMP算法，只是在原子支撑集更新的过程中剔除了不可靠原子，使得SAMP算法的原子支撑集的拓充速率次于OMP算法，但是SAMP算法的原子支撑集中的原子比OMP算法对原始信号的表达能力更强。当步长S等于K的情况下，若感知矩阵满足RIP条件，SAMP算法就等同于SP算法，这时仅通过一次迭代就可以找到原始信号的K-稀疏近似。当步长S小于K时，SAMP算法在每次迭代过程中原子更新的思想依然和SP算法是近似的，在寻找原子支撑集的过程中，SAMP算法期望通过相较于较SP算法更小的原子支撑集重建原始信号同时期望达到更高的准确性。SAMP算法的输入参数中不需要原始信号的稀疏度K，由迭代过程自适应更改步长S逐步逼近原始信号。正是SAMP算法的这一优点使得该算法较于前几个16 第二章压缩感知重建算法算法在实际中具有更好的适用性。表2-7SAMP算法流程图输入传感矩阵：MNM观测值向量：y步长：S迭代1.初始化：残差ry0=，信号稀疏表示系数初值ˆ0=0，索引集合=0，匹配矩阵=，初始步长LS=，初始化变量i=1，初始化迭代次数t=1；02.判别：u=uuj|j=rt−1,aj,1jN，取出列序号集合Skj=j|max(,)uL；3.原子候选集更新：令Ck=t−1Sk,,=tajjCk；−14.信号稀疏表示系数估计值更新：ˆ=argminyy−=(TT)；tttttt5.原子支撑集合更新：ˆtL=max(,)ˆtL，其中对应的t中的L列记为tL，对应的列序号记为tL，记集合F=tL；−16.残差更新：r=−yˆ=−y(TT)y；tptLtLtLtLtLtL7.更新迭代次数，判断运算终止条件：如果残差rt=0则停止迭代进入第8步，如果rr，令ii=+1，LiS=，返回第2步继续迭代；如果上述两个条件均不tpt−122满足，令=tF，rrt=tp，tt=+1，返回第2步继续迭代；8.估计ˆ：集合t中存放非零项位置，ˆ中对应的非零值为最终迭代求得的ˆt输出信号稀疏表示系数估计ˆ2.3仿真结果与分析本节首先通过实验探究了StOMP算法的阀值参数对精确重建概率概率的影响以及SAMP算法的步长设置对不同信号重建概率的影响；并通过一维信号和图像的重建效果对比了2.2节提及的贪婪算法的性能。本节实验是在Windows操作系统下使用MATLABR2014a软件进行仿真。实验一：在文献[29]中指明StOMP算法的阀值参数取值范围为23t，为验s证StOMP算法在阀值t取不同值时精确恢复概率和稀疏度之间的关系，进行如下s实验。测量次数固定M=128，稀疏度K(10,15,20,25,...,125)，阈值ts(2,2.2,2.4,...,3)时，通过进行1000次独立重复试验计算准确重建概率−6（xxˆ−10时认为重建成功）。图2-2(a)和2-2(b)分别代表高斯信号的恢复概率2曲线和0-1信号的恢复概率曲线。17 电子科技大学硕士学位论文(a)(b)图2-2StOMP算法阀值取不同值时重构概率随稀疏度的变化情况(a)高斯信号重建概率；(b)0-1信号重建概率；由图2-2(a)和2-2(b)可知，在测量次数一定的情况下，针对服从高斯分布的稀疏信号的恢复和服从0-1分布的信号的恢复，在ts取较小值的情况下，重建效果更优。18 第二章压缩感知重建算法实验二：SAMP算法中的输入参数步长S的取值影响着SAMP算法的运行速度和求解精度。为验证SAMP算法在步长S取不同值时精确恢复概率和测量数量之间的关系。取稀疏度固定K=12的一维稀疏信号x，测量次数M(20,30,40,...,120)，对于测量次数取不同值的情况，通过进行1000次独立重复试验计算准确重建概率。对不同信号的重建概率曲线如图2-3所示。(a)(b)图2-3SAMP算法步长S变化对重建概率的影响(a)高斯信号重建概率；(b)0-1信号重建概率19 电子科技大学硕士学位论文由图2-3(a)和2-3(b)可知，对于服从高斯分布的稀疏信号的重建，在稀疏度一定的情况下，步长S越小重建概率越高。相反，对于服从0-1分布的稀疏信号的重建，步长S越大重建概率越高。因此在实际应用中，需要针对信号的分布情况选取合适的步长S才能获取更好的重建效果。实验三：以下仿真实验中StOMP算法的阀值参数取ts=2.2；SAMP算法的对于高斯信号重建步长参数设置为S=1，对于0-1信号的重建步长参数设置为S=6，对于图像信号的重建步长参数设置为S=1。a：目标为一维稀疏信号，比较各贪婪算法的重构性能（1）测量次数M=128固定，以长度N=256的高斯稀疏信号和0-1分布的稀疏信号为目标，稀疏度K(10,15,20,...,60)，使用2.2节所提及的算法对信号进行重建，对于不同的稀疏度分别进行1000次独立重复试验，获得的重建概率和信号稀疏度之间的关系曲线如图2.4所示。由图2-4(a)和2-4(b)可知，在测量次数固定的情况下，对于高斯信号的重构，SAMP算法和SP算法的重构性能最高，ROMP算法的重构性能最弱。StOMP算法在稀疏度K35时能够精确重构信号；SP算法和CoSaMP算法在稀疏度K40时能够完成信号的准确重建；ROMP算法在稀疏度K20时可以准确重构信号；OMP算法在稀疏度K10时可以准确重构信号。对于0-1信号的重构，SP算法、CoSaMP算法、SAMP算法的重构性能最好，ROMP算法和OMP算法的重构性能最弱，StOMP算法重构性能居中。其中，ROMP算法和OMP算法在K10的情况下就不能完全保证信号的重构的准确性；StOMP算法在K25的情况下无法准确重构信号；SP算法、CoSaMP算法、SAMP算法在K30的情况下可以准确重构信号。(a)20 第二章压缩感知重建算法(b)图2-4不同贪婪类算法的重构概率和稀疏度变化关系曲线。(a)高斯信号重建概率；(b)0-1信号重建概率综上可知，测量次数一定时，信号稀疏度越高，正确重建的概率越大。重建SP算法、CoSaMP算法和SAMP算法对于高斯信号和0-1信号的重建效果较OMP算法和ROMP算法好。其中，SAMP算法在重建高斯随机信号时，较于其他算法具K55有显著优势，该算法可以在比率r==0.43的条件下准确重建原始信号。M128除ROMP算法外，上述各类算法在0-1信号的重建性能上均低于对高斯信号的重建；相反，ROMP算法在重建0-1信号的重建性能优于对高斯信号的重建。（2）稀疏度K=20固定，以长度N=256的高斯稀疏信号和0-1分布的稀疏信号为目标，观测次数M(50,60,70,80,90,100)，使用2.2节所提及的算法对信号进行重建，对于不同的稀疏度分别进行1000次独立重复试验，获得的重建概率和观测次数之间的关系曲线如图2-5所示。由2-5(a)和2-5(b)所示，稀疏度K=20固定。对于高斯信号的重建，SAMP算法的重建性能较其他几个算法具有明显优势，在测量次数为70的情况下就可以95%的概率准确重建原始信号；StOMP算法、SP算法和CoSaMP算法在测量次数达到80的情况下可以以接近95%的概率重建原始信号；OMP算法的在测量次数达到100的情况下可以以高于90%的概率重建原始信号；在观测次数小于100的情况下，ROMP算法几乎无法完成信号重建。对于0-1信号的重建SAMP算法、SP算法和CoSaMP算法在测量次数大于90的情况下可以以高于90%的概率准确重建原21 电子科技大学硕士学位论文始信号；StOMP算法在测量次数等于100的情况下可以以高于90%的概率重建原始信号；OMP算法在测量次数等于100的情况下，准确重建原始信号的概率仅能达到21%；ROMP算法在测量次数小于100的情况下，重建概率最多可以达到15%。(a)(b)图2-5不同贪婪类算法的重构概率和观测次数曲线(a)高斯信号重建概率；(b)0-1信号重建概率22 第二章压缩感知重建算法综上可知，稀疏度固定，观测次数越多，正确重建概率越大。OMP算法、CoSaMP算法、SP算法和SAMP算法对0-1信号的准确重建相比于对高斯信号的准确重建需要更多的测量次数，相反，对于ROMP算法，在测量次数和稀疏度固定的情况下，ROMP算法对0-1信号的重构优于其对高斯信号的重构。b：目标为图像信号，比较各贪婪算法的重构性能M定义图像压缩比r=，以峰值信噪比PSNR和运行时间作为标准衡量重构N图像质量。PSNR定义如下：255PSNR=20lg(2-12)xx−ˆ2上式中x代表原始信号，xˆ代表重构信号。实验中稀疏度取=MN/2ln()，稀疏矩阵为小波基，观测矩阵为高斯矩阵。以大小为256256的Lena图像为重建目标，在不同压缩比的情况下，各贪婪算法重构Lena图像PSNR如表2-8所示。表2-8各贪婪算法重构图像的PSNR(dB)压缩比算法0.20.30.40.50.6OMP19.2121.4023.6725.0626.11StOMP19.9023.5326.0128.3730.38ROMP19.8323.5125.7226.9827.32CoSaMP19.6821.9024.1325.5226.68SP19.5021.8924.0625.4326.59SAMP19.7822.7125.5928.5230.88由表2-8可知，当测量的压缩比增大时，上述贪婪重构算法的重构图像PSNR增大，因此通过增加观测次数可以提高重构图像的PSNR值。当压缩比一定时，OMP算法重构图像的PSNR值最小，SAMP算法的重构图像的PSNR最大，StOMP算法、ROMP算法、CoSaMP算法和SP算法的重构图像PSNR介于两者之间。重构图像的PSNR值的大小反映了重构图像与原始图像的接近程度，重建图像的PSNR值越高，则对应重建算法的重建图像越接近于原始图像。所以OMP算法较于StOMP算法、ROMP算法、CoSaMP算法和SAMP算法对图像的重构能力最差，SAMP算法的图像重构能力最优。在不同压缩比的情况下，各贪婪算法重构Lena图像耗费时间如表2-9所示：23 电子科技大学硕士学位论文表2-9各贪婪算法的重构时间(s)压缩比算法0.20.30.40.50.6OMP0.1050.1720.2770.3990.517StOMP0.3830.7991.3891.6192.533ROMP0.1390.1710.3220.5490.638CoSaMP0.2690.3490.7511.1401.576SP0.2470.3310.6791.1261.567SAMP5.1410.1420.6438.4274.52由表2-9可知，当测量的压缩比增大时，上述贪婪重构算法的完成图像重构耗费的时间也越大。压缩固定的情况下，SAMP算法进行图像重构耗费的时间最多；SAMP算法图像重建时间随压缩比增加的增长幅度最大，StOMP算法、ROMP算法、CoSaMP算法和SP算法图像重建时间随压缩比的增加而增加的幅度较缓。在压缩比r=0.5的情况下，Lena原图及各贪婪算法重构图像效果如图2-6所示。其中2-6(b)代表Lena图像经过小波变换基表示后的稀疏系数，很大范围的区域都是黑色的说明了变换系数非常稀疏，因而Lena图像具备了使用CS重构算法的前提条件。在压缩比r=0.5的情况下，各个贪婪类重建算法的图像重建都比较接近原始图像，可以良好地反映原图内容。(a)(b)(c)24 第二章压缩感知重建算法(d)(e)(f)(g)图2-6压缩比r=0.5时各算法重构图像(a)原始图像；(b)小波变换后的图像；(c)OMP重建图像；(d)StOMP重建图像；(e)CoSaMP重建图像；(f)SP重建图像；(g)SA-MP重建图像2.4本章小结本章简要介绍了压缩感知的理论基础，着重介绍了CS重建算法中的几个经典贪婪类重建算法，包括OMP算法、StOMP算法、ROMP算法、CoSaMP算法、SP算法和SAMP算法。详细的梳理了各个算法的实现流程，总结了各算法的特点。通过各算法对重建一维高斯信号和0-1信号的重建，比较了各算法对不同信号的重构性能；并使用各算法对Lena图像进行了图像重建，并以PSNR和运行时间作为图像评价指标，对各算法进行了定性分析。25 电子科技大学硕士学位论文第三章基于随机原子选择的匹配追踪算法研究OMP算法是贪婪类算法中最典型的一个，一直以来受到人们的广泛关注，为改善OMP算法的准确重建概率和对于不同类型信号重建性能的稳定性，人们在此基础上做出了很多改进。如第二章提及的ROMP算法通过对选择原子加入预先定义的正则化方式进行原子筛选；StOMP算法通过设置门限参数对原子进行筛选；SP算法和CoSaMP算法通过加入回溯的过程改善信号估计支撑集原子；总而言之，这些OMP改进型算法的研究重点就是原子支撑集的选择策略问题。本章对两个新颖的改进型算法（多路径匹配追踪算法（MultipathMatchingPursuit，简称MMP）和广义正交匹配追踪算法（GeneralizedOrthogonalMatchingPursuit，简称gOMP））的原子选择方式进行深入分析，并指出了它们存在的不足。针对它们存在的问题，摒弃了现有算法确定性原子的选择方式，在进行原子的支撑集拓充的过程中引入了“适度”的随机性，提出了随机策略匹配追踪算法（RandomStrategyMatchingPursuit，简称为RSMP）。3.1研究的出发点3.1.1多路径匹配追踪MMP[35]算法通过保留多个较可靠的原子支撑集的方式来增加获取正确原子支撑集的概率。该算法与第二章所提及的算法的最大的不同点在于它的树形结构，MMP算法按树形结构的“生长”方式可分为广度优先多路径匹配追踪算法（MultipathMatchingPursuitBreadthFirstSearch，简称为MMP-BF）和深度优先多路径匹配追踪算法（MultipathMatchingPursuitDepthFirstSearch,简称为MMP-DF）。3.1.1.1广度优先多路径匹配追踪MMP-BF算法的每条路径的会产生L个子路径（由残差和观测矩阵的列相关性选择L条路径）作为子路径；显然当搜索路径条数L=1时，MMP-BF算法就等同于OMP算法。在稀疏度K=3，搜索路径L=2时，MMP-BF算法和OMP算法的原子支撑集对比如图3-1所示。3由图3-1可知，三次迭代后OMP算法原子支撑集集合S和MMP-BF算法的333原子支撑集集合S中的第一个子集S相等，集合S和集合S都是通过不断选择3113与残差最相关的列（原子）产生的。OMP算法对信号的重建是利用集合S中元素对应的原子还原信号，而MMP-BF算法对信号的重建是利用集合S中残差最小的326 第三章基于随机原子选择的匹配追踪算法研究子集所对应的原子还原原始信号。S1=2S1=512112SS2,422222S2SS1=2,4S2=2,3S3=5,4S4=5,333333332,4,5SS1=2,4,5S2=2,4,3S3=5,4,1S4=2,3,5S5=5,4,3S(a)OMP(b)MMP-BF图3-1OMP和MMP-BF算法原子候选集更新示意图由于OMP算法的最终支撑集集合是MMP-BF算法的支撑集集合的一个子集，所以MMP-BF算法相较于OMP算法正确重构原始信号的概率更高。MMP-BF算法流程如表3-1所示。表3-1MMP广度优先算法流程输入传感矩阵：观测值：y稀疏度：K搜索路径个数：L0迭代初始化残差ry0=，索引集S=，始迭代次数k=0迭代：whilekKdokk=+k1,u=0,S=;fori=1tok−1doS2Tk−1=argmax(ri)=L2forj=1toLdok−1sstemp=ijifksSthentempuu=+1kssu=temp27 电子科技大学硕士学位论文kkkS=Ssuˆk†xyu=sk;ukkr=−ykxˆuusuendifendforendforendwhile2Kur=argminu2Kss=u−1†††TT信号稀疏表示系数估计xyˆ=,其中代表的伪逆：=()输出sMMP-BF算法最终搜索获得的原子支撑集个数多，通过择取最优的支撑集重建原始信号，因而重建概率高。但是，MMP-BF算法每次迭代时，每条支路都会产K生L个子支路，所以在K次迭代后，MMP-BF算法生成树的支路个数为L，除去重复的集合，MMP-BF算法所需的存储和计算量依然很大。3.1.1.2深度优先多路径匹配追踪为控制MMP-BF算法计算复杂度，MMP-DF算法在MMP-BF算法的基础上做出了改进，该算法采用顺序构造树形结构每一条路径。当支路的最小残差的模值满足一个合适的终止条件或者支路个数达到设定的最大值时停止迭代。当稀疏度K=2，支路最大个数lmax=3，子代分支L=2时，MMP-DF算法搜索方式如图3-2所示。第二条路径(,,)ccc=(2,1,1)123第一条路径(,,)ccc123=(1,1,1)c1=1c1=2c=2c=12c=122c=1c=1c3=133第三条路径(,,)ccc=(1,2,1)123图3-2MMP-DF算法搜索方式示意图第l条路径对应的序号(,,)ccc123是由一种模数策略确定。模数层顺序ck和路径28 第三章基于随机原子选择的匹配追踪算法研究Kk−1序数l之间的关系满足l=+1(ck−1)L，模数层的顺序ck是按照原子和残差之间k=1的相关性从高到底排列的。因此，MMP-DF算法思想是优先选择较可靠原子序列集合作为原子支撑集，不断比较残差是否满足要求，进行小范围、高可靠性的原子支撑集搜索。MMP-DF算法的流程如表3-2所示。表3-2MMP-DF算法流程表输入传感矩阵：观测值向量：y停止阈值：最大候选集集合个数：lmax步骤初始化：残差的幅值ρ=∞，候选集合序号l=0；迭代：while𝑙<𝑙maxanddoll=+10ry=[,...,cc]=computecklLK_(,,)1Kfork=1toKdo2Tk−1=argmax(ri)=L2kk−1ssl=lckˆk†xy=k;slkkr=−ykxˆslendforifKrthenK=rˆ*ˆKxx=endifendwhile输出信号稀疏表示系数估计𝑥̂∗MMP-DF算法在l=1时等价于OMP算法，该算法通过和合理的停止条件，max避免了“过度”搜索的问题，提高了搜素效率。29 电子科技大学硕士学位论文3.1.1.3分析MMP-BF算法最终的原子支撑集集合的子集个数超过了MMP-DF算法的原子支撑集集合的子集个数，而OMP算法搜索得到的原子支撑集只是MMP-BF算法和MMP-DF算法的一个子集。它们之间的关系如图3-7所示。MMP-BF支撑集集合MMP-DF支撑集集合OMP支撑集图3-3OMP算法、MMP-BF算法和MMP-DF算法支撑集集合关系示意图如图3-3所示，MMP-BF算法对应区域所包含的原子支撑集个数最多，MMP-DF算法所包含的原子支撑集个数次之，OMP算法只有一个原子支撑集。MMP-DF算法和OMP算法相比，它们的共同点是以残差和原子的相关性作为原子选择的指导，不同的是MMP-DF算法保留了“次相关”的原子集；然而MMP-DF算法的重建性能高于OMP算法，是由于这些“次相关”的原子集合中包含的原子对于原始信号具有更强的“表达能力”。因而，最优原子支撑集的原子挑选取决于原子和残差的相关性，但是不完全和它们之间的相关性一致。MMP-DF算法的原子支撑集集合是MMP-BF算法的子集，通常，MMP-BF算法信号重建性能高于MMP-DF算法的信号重建性能，主要是由于MMP-DF算法的这种模数策略(确定性的选择)并没有选择到MMP-BF算法原子支撑集合中最优的原子支撑集，所以确定性选择策略并不是原子支撑集拓充方式的最优策略。3.1.2广义正交匹配追踪gOMP算法[34]和OMP算法框架大体相同，只是在每次迭代时选择L原子，该方式使得gOMP算法较OMP算法的计算复杂度更低，减少了运行时间，广义正交匹配追踪算法的流程如表3-3所示。30 第三章基于随机原子选择的匹配追踪算法研究表3-3广义正交匹配追踪算法流程表输入传感矩阵MNM观测值向量y稀疏度K每次选择原子的个数L迭代1.初始化：初始迭代次数t=1；残差ry0=；信号稀疏表示系数初值ˆ0=0；索引集=0；匹配矩阵=0；2.支撑集索引集合搜索：u=uuj|j=rt−1,aj,1jN，令Ju0=supp()L；3.支撑集索引更新：=tt−1Jj0,J0；匹配矩阵更新=tt−10ajj,J−14.稀疏表示系数估计值更新：ˆ=argminyy−=(TT)；tttttt−15.残差更新：r=−yˆ=−y(TT)y;ttttttt6.迭代次数更新并检验是否迭代停止：tt=+1，若tK，则返回第2步，否则迭代停止并进入第7步；7.估计ˆ：集合t中存放非零项位置，ˆ中对应的非零值为最终迭代求得的ˆt输出信号稀疏表示系数估计ˆ由表3-3所示gOMP算法不同于其他的OMP改进算法，相较于第二章的OMP改进算法只是通过每次迭代选取LL(1)个与残差最相关原子的方式来改善OMP算法的性能，OMP算法是gOMP算法在每次迭代选取原子个数N=1时的一个特例。在每次迭代选取原子个数L1时，gOMP算法的完成信号重建所需迭代次数相较于OMP算法更少。然而gOMP算法每次迭代过程固定选取L个相关性最大的原子，使得gOMP算法太过“呆板”，不能根据具体条件“随机应变”。下面举例说明这种固定性选择拓充原子支撑集的方式存在的不足：例一：当选择原子个数L=3时，如果在一次迭代过程中计算的原子与残差之间的相关性集合中有wwL()个值较大，如u=0.9,0.8,0.05,0.038,0.027,0.02,0.019，则选取与残差相关性为0.9，0.8和0.05对应的原子，可以看出第三个原子的相关性远低于前两个原子的相关性，而这个原子很可能是非可靠原子，当非可靠原子加入了原子支撑集，就会影响残差的更新，从而致使后续原子选择不正确。例二：当选择原子个数L=3时，如果在一次迭代过程中计算的原子与残差之间的相关性中有ww()L个值较大，如u=0.98,0.97,0.968,0.965,0.95,0.03,0.19，这时集合u中的5个值较大，只选取前3个较大值对应原子拓充原子支撑集合，这种选择策略使得算法的灵活性不够，该过程并没有将相关性较大的5个可靠原子31 电子科技大学硕士学位论文一次取出，所以gOMP算法在搜索可靠原子支撑集的过程中需要更多的迭代次数。3.2随机原子选择匹配追踪算法3.2.1随机优化的优点匹配追踪类压缩感知重构算法是通过迭代最小化残差的方式寻找稀疏信号的支撑集，再通过最小二乘的方式估计出原始信号非零分量的值，该过程实质上等同于一个最优化[45]求解问题。在最优化理论中，根据随机性，最优化理论可以被划分为确定性优化和随机优化。确定性优化方法对输入的参数的依赖性强，当参数设置不在最优值附近时，确定性优化会丧失对最优解的搜索能力。相较于确定性优化，统计学理论表明，随机优化对全局最优解的搜索能力更强，随机优化比确定性优化更加可靠，同时随机优化在数学上更加简单且易于编程。3.2.2随机策略匹配追踪算法MMP算法保存了多个可靠候选原子支撑集，并择取残差最小的支撑集进行原始信号的重建，依此来增加正确重构概率；gOMP算法在每次进行原子拓充时选择与残差相关性最大的L个原子，从而减少了算法迭代次数。上述算法虽然在一定程度上提升了OMP算法的性能，但是MMP算法的多支路树形结构复杂，同时为保证最终待选原子支撑集集合不包含重复的原子支撑集，迭代过程中需要将本次原子支撑集与先前保存的多个原子支撑集作比较，无疑增加存储量且比较过程也耗费了很多计算时间。gOMP算法每次固定选择L个原子的方式在很大程度上优化了OMP算法的性能，然而这个步长L的选择需要人为的设定，当步长大的情况下可以提高算法的计算速度，但是同时会引起信号重构精度降低，在步长过大的情况下，可能会使算法不收敛导致无法准确重建原始信号。由上一小节分析我们得出结论：最优原子支撑集的原子挑选取决于原子和残差的相关性，但是不完全和它们之间的相关性一致；同时确定性选择策略并不是原子支撑集拓充方式的最优策略。为改进算法性能，本小节结合了随机优化的优点，将“适度”的随机性引入原子选择操作过程，提出了随机策略匹配追踪算法（RandomStrategyMatchingPursuit，简称为RSMP）。RSMP算法的具体步骤如表3-4所示。32 第三章基于随机原子选择的匹配追踪算法研究表3-4随机策略匹配追踪算法流程表输入传感矩阵：MNM观测值向量：y稀疏度：K迭代1.初始化：初始迭代次数t=1；残差ry=；稀疏表示系数初值ˆ=0；索引集00=；匹配矩阵=；002.计算相关性，u=uuj|j=rt−1,aj,1jN,Su02=supp(k)3.将相关性作为评价指标，对集合S0进行轮盘赌K次，将选择的对应原子存入集合J；04.支撑集索引更新：=tt−1Jj0,J0；匹配矩阵更新=tt−10ajj,J；−15.稀疏表示系数估计值更新：ˆ=argminyy−=(TT)，当矩阵的列大ttttttt于K时进入第6步，否则进入第7步；6.原子支撑集合更新：令ˆtk=suppˆtk，将对应的t中的K列用tk表示；对应tk的索引序号用tk表示，更新集合=ttk；−17.残差更新：r=−yˆ=−y(TT)y；ttttttt8.迭代次数更新并检验是否迭代停止：tt=+1，若tM，则返回第2步，否则停止迭代进入第9步。9.估计ˆ：集合t中存放非零项位置，ˆ中对应的非零值为最终迭代求得的ˆt输出信号稀疏表示系数估计ˆ由表3-4可知，RSMP算法始终只含有一个原子支撑集，该算法相较于MMP算法结构更简单。MMP算法通过多支路、多次重复的方式搜索最佳原子支撑集；不同于MMP算法限定性选择满足一定条件的固定原子进行原子支撑集拓充，RSMP算法在原子选择中引入了随机性，使得原子支撑集中原子为多样，且RSMP算法引入回溯的过程，不断剔除不可靠的原子，使得单路径的RSMP算法以更大概率找到正确的原子支撑集，以单路径的形式同样达到多路径的目的。RSMP算法较于gOMP算法在初始化时不需要设定原子选择个数，通过进行轮盘赌式原子选择策略进行（具体方式见4.1.1节）K次原子选择，每次原子的选择范围为与残差较相关的原子集合S，来实现“适度”的随机原子选择。本算法在0原子支撑集拓充的过程中采用轮盘赌原子选择策略从集合S中依相关性随机选取0K次，首先，相关性大的原子可以被选择多次，因而每次选出的原子个数是随机的，其次，通过轮盘赌的方式选取的原子是随机的，在集合S中的原子都有一定的概0率被选中，从而增加了选择原子的多样性。不同于gOMP算法每次迭代固定的选取L个最大的原子，RSMP算法每次迭代选择的原子个数不定，相较于gOMP算33 电子科技大学硕士学位论文法更为灵活，当原子集合S中的原子与残差之间的相关性只有极少数原子的相关0性模值较大时，选取的集合J0中会多次重复的出现相关性模值较大的原子，所以集合J中选择的不同原子个数就相应减少；当原子集合S中的原子与残差之间的00相关性有多个原子的模值较大时，相关性大的原子有很大概率被选中，所以选取的集合J中原子的个数就会增加。所以RSMP算法相较于gOMP算法具有“随机应0变”的特性，能够在迭代过程中自适应选取合适个数的原子。3.3仿真结果与分析本小节将OMP算法、gOMP算法、MMP-BF算法、MMP-DF算法和RSMP算法在有噪和无噪情况下对高斯信号和0-1信号的重建效果进行对比。（1）无噪情况测量次数M=100固定，以长度N=256的服从高斯分布稀疏信号和服从0-1分布的稀疏信号为目标，稀疏度K(5,10,15,20,...,40)，对于不同的稀疏度分别进−6行500次独立重复试验，在xxˆ−10时认为重建成功，重建概率和信号稀疏度2之间的关系曲线如图3-4所示。(a)34 第三章基于随机原子选择的匹配追踪算法研究(b)图3-4重建概率和信号稀疏度之间的关系(a)高斯信号重建概率曲线；(b)0-1信号重建概率曲线图3-4中可以看出，在测量次数M=100的情况下，OMP算法、gOMP算法和MMP-DF算法、MMP-BF算法和RSMP算法对于高斯信号和0-1信号的重建概率都随着稀疏度的增加而减小。OMP算法的高斯信号和0-1信号的重建性能最弱。gOMP算法对于高斯信号的重建在L=3的情况下正确重建原始信号概率最大，对于0-1信号的重建，在步长L=9的情况下重建概率最高。RSMP算法对于高斯信号的重建概率高于gOMP算法在L=6和L=9时的重建概率，且非常趋近于gOMP算法L=3时的仿真概率曲线；与MMP算法相比，RSMP算法重建概率优于MMP-DF算法，次于MMP-BF算法；对于0-1信号的重建RSMP算法的重建概率相较于gOMP算法和MMP算法具有绝对优势。以长度N=256的稀疏度K=30高斯稀疏信号和稀疏度K=20的0-1分布的稀疏信号为目标，观测次数M(60,70,80,90,100,110,120)，对于不同的观测次数分别进行500次独立重复试验，重建概率和观测次数之间的关系曲线如图3-5所示。35 电子科技大学硕士学位论文(a)(b)图3-5重建概率和观测次数之间的关系(a)高斯信号重建概率曲线(K=30)；(b)0-1信号重建概率(K=20)如图3-5所示，在稀疏度一定的情况下OMP算法、gOMP算法、MMP-DF算法、MMP-BF算法和RSMP算法对于高斯信号和0-1信号的重建概率都随着观测36 第三章基于随机原子选择的匹配追踪算法研究次数的增加而增大。其中OMP算法对于高斯信号和0-1信号的整体重建性能最弱。gOMP算法对于高斯信号L=3的情况下准确重建原始信号的概率最大；对于0-1信号的重建L=9的情况下准确重建原始信号的概率最高。对于高斯信号的重建，与gOMP算法相比，RSMP算法较gOMP算法L=3和L=6的情况重建性能更优，稍次于gOMP算法L=3的情况；与MMP算法相比，RSMP算法概率曲线变化趋势更为陡峭，在观测次数M90时，RSMP算法重建概率高于MMP-DF算法，在M100时，RSMP算法重建概率高于MMP-BF算法，因而在观测次数满足一定条件时，RSMP算法较于MMP算法具有更高的重建概率。对于0-1信号的重建重构RSMP算法重建概率最高，在M=90的情况下，RSMP算法的重建概率高于MMP-DF算法25%，高于MMP-BF算法12%。综上，在无噪情况下，gOMP算法对于高斯信号的恢复在步长L取值较小时准确重建概率最大，在对于0-1信号的重建步长L取稍大的值时准确重建概率最大，所以对于不同的信号，想要得到最大的重建概率需要不断调整步长L的取值。MMP算法对于高斯信号的重构性能较好，但是对于0-1信号的重构性能比较弱。而本节所提出的RSMP算法在不调整任何参数的情况下，对不同类型的重建性能都较为理想。（2）加噪声情况测量次数M=100固定，以长度N=256的稀疏度K=30高斯稀疏信号和稀疏度K=20服从0-1分布的稀疏信号为目标，信噪比SNR(5,10,15,...30)dB，对于每个固定的信噪比分别进行500次独立重复试验，以归一化均方误差NMSE(NormalizedMeanSquareError)作为衡量指标，其中NMSE由公式3-1计算：N2xx−ˆn=1NMSE=10lg（3-1）N2xn=1信噪比SNR和NMSE之间的关系曲线如图3-6所示。由图3-6可以看出，在观测次数和稀疏度固定的情况下，对于不同种类信号的重建（高斯信号和0-1信号），OMP算法、gOMP算法、MMP-DF算法、MMP-BF算法和RSMP算法的NMSE性能均随着SNR的增大而提高。对于不同信号的重建，gOMP算法在L=3时NMSE性能优于L=6和L=9的情况；RSMP算法的NMSE性能整体上优于L=3的gOMP算法，且RSMP算法与上述算法中具有最优NMSE性能的MMP算法非常趋近。37 电子科技大学硕士学位论文(a)(b)图3-6信噪比SNR和NMSE之间的关系曲线(a)高斯信号NMSE变化曲线(K=30)；(b)0-1信号NMSE变化曲线(K=20)测量次数M=100固定，以长度N=256的高斯稀疏信号和服从0-1分布的稀疏信号为目标，信噪比SNR=30dB，稀疏度K(5,10,...,40)，对于每个固定的稀38 第三章基于随机原子选择的匹配追踪算法研究疏度分别进行500次独立重复试验，稀疏度K和NMSE的关系曲线如图3-7所示。(a)(b)图3-7稀疏度和归一化均方误差关系曲线(a)高斯信号NMSE变化曲线(K=30)；(b)0-1信号NMSE变化曲线(K=20)由图3-7可以看出，在观测次数和SNR固定的情况下，对于不同种类信号的重建，OMP算法、gOMP算法、MMP-DF算法、MMP-BF算法和RSMP算法的39 电子科技大学硕士学位论文NMSE性能都随着稀疏度的增大而降低。信号越稀疏，通过少量的观测次数各算法可以实现原信号的高准确度重建，当信号稀疏度逐渐增大时，则各算法实现原始信号的准确重建所必需的观测次数也随之增加。对于高斯信号的重构，在K40的整个范围内，MMP算法NMSE的变化量较稳定；在K30时，RSMP算法和gOMP算法NMSE的变化量比较稳定；在K30时，RSMP算法和gOMP算法NMSE性能骤减，表明在该条件下不满足RSMP算法和gOMP算法完成信号准确重构的条件，这时就需要更多的观测次数才能使得它们实现原始信号的准确重建；在满足各算法准确重建高斯信号的条件下，RSMP算法的NMSE性能远优于gOMP算法，且RSMP算法的重建性能非常趋近于MMP算法。对于0-1信号的重构，在K20时，MMP算法和gOMP算法NMSE的变化量较为稳定，在K20时，MMP算法和gOMP算法NMSE性能急剧下降；在K25时，RSMP算法NMSE的变化量较为稳定，在K25时，RSMP算法NMSE性能急剧下降；表明在观测次数固定（M=100）时，RSMP算法实现信号准确重建相较于MMP算法和gOMP算法对于稀疏度的约束条件更为宽松；在满足各算法准确重建0-1信号的条件下，RSMP算法的NMSE性能远优于gOMP算法，且RSMP算法的NMSE性能稍优于MMP算法。以长度N=256的稀疏度K=30高斯稀疏信号和稀疏度K=20服从0-1分布的稀疏信号为目标，信噪比SNR=30dB，观测次数M(60,70,...,130)，对于每个固定的观测次数分别进行500次独立重复试验，观测次数M和NMSE之间的关系曲线如图3-8所示。由图3-8可以看出，在稀疏度和SNR固定的情况下，对于不同类型信号的重建，OMP算法、gOMP算法、MMP-DF算法、MMP-BF算法和RSMP算法的NMSE性能都随着观测次数的增加而提高。对于高斯信号的重建，MMP算法在观测次数M90时，NMSE性能趋于稳定；gOMP算法和RSMP算法在观测次数M100时，NMSE性能趋于稳定；在观测次数满足各算法实现高斯信号准确重建的需求时，RSMP算法重建信号的NMSE性能远优于gOMP算法，RSMP算法的NMSE性能和MMP算法比较接近。对于0-1信号的重构，gOMP算法和MMP算法在观测次数M100时，NMSE性能趋于稳定；RSMP算法在观测次数M90时，NMSE性能趋于稳定，表明在上述条件下，RSMP算法实现信号准确重建相较于MMP算法和gOMP算法对于必需的测量次数的要求更少；在观测次数满足各算法实现0-1信号准确重建的需求时，RSMP算法重建信号的NMSE性能远优于gOMP算法，RSMP算法的NMSE40 第三章基于随机原子选择的匹配追踪算法研究性能与MMP算法非常接近。(a)(b)图3-8观测次数和归一化均方误差关系曲线(a)高斯信号NMSE变化曲线(K=30)；(b)0-1信号NMSE变化曲线(K=20)综上，在信号加入噪声时，在满足各算法准确重建信号对于观测次数和稀疏度41 电子科技大学硕士学位论文要求的情况下，对于高斯信号的重建，MMP算法的NMSE性能最优，RSMP算法的NMSE性能和MMP算法的NMSE性能极其接近，MMP算法和RSMP算法的NMSE性能均远优于gOMP算法；对于0-1信号的重建，RSMP算法的NMSE性能最优，MMP算法稍次于RSMP算法，gOMP算法重构信号的NMSE性能最差。3.4本章小结本章通过对路径匹配追踪算法(MMP，包含MMP-BF算法和MMP-DF算法)和广义正交匹配追踪（gOMP）算法的原子选择方式进行深入分析，总结了原子选择方式对重建概率的影响。摒弃了现有算法确定性原子的选择方式，在进行原子的支撑集拓充的过程中引入了“适度”的随机性，提出了随机策略匹配追踪算法（RSMP）。相较于MMP算法，RSMP算法在原子选择中引入了随机性，使得原子支撑集中原子为多样，依靠回溯的过程，不断剔除不可靠的原子，使得单路径的RSMP算法以更大概率找到正确的原子支撑集，本章所提出的的RSMP算法以单路径的形式同样达到多路径的目的。在无噪条件下，RSMP算法对于高斯信号的重构概率介于MMP-DF算法和MMP-BF算法之间，对于0-1信号的重构性能远优于MMP算法。在信号加噪的条件下，对于高斯信号的重建，在观测次数足够的条件下，RSMP算法的NMSE性能与MMP算法非常相近，对于0-1信号的重建，RSMP算法的NMSE性能优于MMP算法；因而在不同环境下（有噪声和无噪声条件），对于不同类型信号（高斯信号和0-1信号）的重建，RSMP算法的重建性能更加稳定。相较于gOMP算法，RSMP算法无需预先人为设置每次迭代选择原子的个数L，RSMP算法在原子选择时采用轮盘赌原子选择策略，相关性大的原子可以被选择多次，每次选出的原子个数是随机的，因而RSMP算法具有“随机应变”的特性，能够在迭代过程中自适应选取合适个数的原子；同时这种策略使得选择的原子具有多样性，使得RSMP算法找到正确支撑集的概率更大。在无噪条件下，RSMP算法对高斯信号的重建概率与gOMP算法原子选择个数为最优值（L=3）时的重建概率相近；对于0-1信号的重建，RSMP算法的重建性能优于gOMP算法的重建性能。在信号加噪声的条件下，本章提出的RSMP算法对于不同类型的信号的重建NMSE性能均远远优于gOMP算法，表明RSMP算法相较于gOMP算法具有更强的噪声鲁棒性。42 第四章随机原子选择策略研究第四章随机原子选择策略研究贪婪类重构算法通过迭代的方式拓充原子支撑集，再采用最小二乘估计原信号非零元素的值。显然，贪婪类重构算法的研究重点就在于拓充原子支撑集的方法的问题，第三章通过大量的仿真实验表明了随机原子选择策略对于正确原子支撑集的搜索能力较确定性原子选择策略更强，本章着重讨论了随机策略原子选择对不同类型信号的恢复性能。4.1随机原子选择策略遗传算法结合了Darwin进化论和Mendel遗传学的思想，模仿了自然界生物进化过程。它是一种全局优化随机搜索的算法，每个个体通过选择、交叉和变异操作进化为更高适应度个体，最终得到问题的最优解[46]；该算法过程中的选择操作遵循“物竞天泽，适者生存”的自然法则。本节将结合遗传算法中三类选择算子“择优”思想，将该思想引入了随机原子选择方式中，提出了三种随机原子选择策略，它们分别为按比例选择的轮盘赌式原子选择、按排序选择的具有排名的转盘式原子选择以及竞争选择的锦标赛式原子选择方法。4.1.1轮盘赌式原子选择策略轮盘赌选择方法（RouletteSelection）属于比例选择策略范畴，是一种回放式随机采样方法。采用轮盘赌的方式选择原子可以保证原子被选中的概率和原子与残差之间的相关性成正比。若待选原子集合中原子个数为K，待选原子集合中各原子与残差之间的相关性为C，则第i个个体被选中的概率为：iCiP=(4-1)iKCii=1显然，概率反映了原子i的相关性在整个待选原子集合的原子与残差的相关性总和中所占的比例。原子与残差的相关性越大。其被选择的概率就越高、反之亦然。候选原子集合中的原子对应图4-1的一个扇形区域，每个扇形区域的大小取决于对应原子被选中的概率，概率越高与其对应扇形区域的占比就越大。每进行一次原子选择就转动一次轮盘，待到轮盘静止，指针指向哪个区域就选中对应区域代表的原子。轮盘赌原子选择过程可用如下过程模拟：43 电子科技大学硕士学位论文（1）在0,1之间产生均匀随机数r；（2）如果rq1，则第1个原子被选中；（3）如果qrq(2jK)，则选中原子x。jj−1j其中q表示原子x的累计概率，q的计算公式见公式4-2。jjjjqji=Px()(4-2)i=1图4-1轮盘赌概率分布示意图4.1.2具有排名的转盘式原子选择策略具有排名的转盘式选择方法属于排序选择(SortSelection)策略范畴。排序选择策略是将原子与残差间的相关度的差异变换成为它们在序列中的先后顺序。排序选择方式选择操作主要包含两项操作：一、要根据待选原子集中原子与残差的相关性依照其相关性高低进行排序；二、依据排列序数按照特定的规则或方式对集合中的原子进行选择。具有排名的转盘式选择方式按照各个原子与余量的相关性大小排列xxx，然后按照线性函数计算被选择概率：12K1bip=a−,i=1,2,,K(4-3)iKK+1其中i表示排名序数，K待选原子集合中原子个数，ab,是常量，且一般情况下12a，ba=−2(1)。通过这个选择概率依照轮盘赌的选择方式进行原子选择。选择排序操作把种群中个体之间的适应度差别转换为它们在排列好的序列中的先后顺序。44 第四章随机原子选择策略研究4.1.3锦标赛式原子选择策略锦标赛选择方法(TournamentSelection)属于竞争选择策略范畴，这里的竞争选择是指通过竞争的方式确定哪一个原子被选择，这种选择方式直接根据原子和残差之间的相关性进行原子的挑选，不同于上述两种选择方式，该方法不需要对原子按照原子与残差之间的相关性大小进行排序，也不需要计算整个待选原子集合的原子与残差的相关性总和。因而可以降低计算量、节约时间，采用锦标赛选择方式相较于前两种搜索方式效率更高。锦标赛选择方式的具体步骤如下：（1）确定每次选择原子数量SS()K（2）从待选原子集中随机选取（每个原子被选中的概率均等）S个原子构成组；（3）对于步骤（2）中选取的组的原子，通过比较各原子与残差的相关性大小，选取相关性最大的原子放入原子支撑集；（4）重复步骤（2）和步骤（3），直到选择的原子达到预定需求。4.2仿真结果与分析本小节将具有排名的转盘式原子选择策略和锦标赛式原子选择策略替换原RSMP算法在拓充原子支撑集时所用的轮盘赌式原子选择策略，并对这两种改进型算法和RSMP算法和gOMP算法进行对比。第三章节仿真实验结果表明，无噪环境中，gOMP算法对于高斯信号的重构，在L=3的条件下重构概率最高，对于0-1信号的重构，在L=9的条件下重构概率最高；有噪声情况下，对于高斯信号和0-1信号的重建，在L=3的情况重构性能最优。在以下仿真实验中，gOMP算法L的取值为对应环境下的最优值，具有排名的转盘式选择方式的参数a=1.1，锦标赛选择方式单次参与竞争的原子数量S=3。（1）无噪情况测量次数M=100固定，以长度N=256的高斯稀疏信号和0-1分布的稀疏信号为目标，稀疏度K(5,10,15,20,...,40)，对于不同的稀疏度分别进行500次独立−6重复试验，在xxˆ−10时认为重建成功，重建概率和信号稀疏度之间的关系曲2线如图4-2所示。从图4-2中可以看出，采用不同的原子选择方式，对于不同类型的信号的重建，各算法的准确重建概率均随着信号稀疏度的增加而减小。对于高斯信号的重构，采用锦标赛原子选择策略的改进型算法的重构概率最优，gOMP算法在L=3的条件45 电子科技大学硕士学位论文下的重建概率稍优RSMP算法和排序选择策略的改进型算法，其中排序选择策略改进型算法的重建概率稍优于RSMP算法。对于0-1信号的重建，RSMP算法、基于排序选择策略和竞赛选择策略的改进算法的重建概率明显优于L=9条件下的gOMP算法。(a)(b)图4-2重建概率和信号稀疏度之间的关系曲线(a)高斯信号重构概率曲线；(b)0-1信号重构概率曲线46 第四章随机原子选择策略研究以长度N=256的稀疏度K=30高斯稀疏信号和稀疏度K=20的0-1分布的稀疏信号为目标，观测次数M(60,70,80,90,100,110,120)，对于不同的观测次数分别进行500次独立重复试验，获得的重建概率和观测次数之间的关系曲线如图4-3所示。(a)(b)图4-3重建概率和观测次数之间的关系曲线(a)高斯信号重构概率曲线(K=30)；(b)0-1信号重构概率曲线(K=20)47 电子科技大学硕士学位论文由图4-3可以看出，采用不同的原子选择方式，对于不同类型的信号的重建，各算法的准确重建概率均随着观测次数的增加而减小。对于高斯信号的重建，锦标赛选择策略改进型算法的重构概率最高，L=3条件下gOMP算法的重构概率和RSMP算法相近，基于排序选择策略的改进型算法的重构概率最差。对于0-1信号的重建，RSMP算法、锦标赛选择策略和排序选择策略的改进型算法的重构概率优于L=9条件下的gOMP算法的重建概率，其中锦标赛选择策略的改进型算法的重建概率最高。（2）加噪声情况测量次数M=100固定，以长度N=256的稀疏度K=30高斯稀疏信号和稀疏度𝐾=20服从0-1分布的稀疏信号为目标，信噪比SNR(5,10,15,...30)dB，对于每个固定的信噪比分别进行500次独立重复试验，以归一化均方误差NMSE作为衡量指标，信噪比SNR和NMSE之间的关系曲线如图4-4所示。由图4-4可以看出，采用不同的原子选择方式，对于不同类型的信号的重建，各算法的NMSE性能随着SNR的增加而提高。对于高斯信号和0-1信号的重构，RSMP算法、锦标赛选择策略和排序选择策略的改进型算法优于L=3条件下的gOMP算法的NMSE性能。(a)48 第四章随机原子选择策略研究(b)图4-4信噪比与归一化均方误差的关系曲线(a)高斯信号NMSE变化曲线(K=30)；(b)0-1信号NMSE变化曲线(K=20)测量次数M=100固定，以长度N=256的高斯稀疏信号和服从0-1分布的稀疏信号为目标，信噪比SNR=30dB，稀疏度K(5,10,...,40)，对于每个固定的稀疏度分别进行500次独立重复试验，以归一化均方误差NMSE作为衡量指标，稀疏度K和NMSE的关系曲线如图4-5所示。(a)49 电子科技大学硕士学位论文(b)图4-5稀疏度与归一化均方误差的关系曲线(a)高斯信号NMSE变化曲线；(b)0-1信号NMSE变化曲线由图4-5可以看出，采用不同的原子选择方式，对于不同类型的信号的重建，各算法的NMSE性能随着稀疏度K的增加而降低。对于高斯信号的重构，锦标赛选择策略NMSE性能最优；在稀疏度K30的条件下RSMP算法、锦标赛选择策略和排序选择策略的改进型算法的NMSE性能几乎一致，且均远优于gOMP算法；在稀疏度K30的情况下，RSMP算法的NMSE性能急剧下降，在K35时，RSMP算法的NMSE性能低于gOMP算法；在K35时，排序选择策略的改进型算法的NMSE性能骤然下降，在K40的范围内，排序选择策略的改进型算法的NMSE性能整体上优于L=3条件下的gOMP算法。对于0-1信号的重构，RSMP算法、锦标赛选择策略和排序选择策略的改进型算法的NMSE性能优于L=3条件下的gOMP算法的NMSE性能；其中锦标赛选择策略和排序选择策略的改进型算法的NMSE性能非常接近，且它们的NMSE性能均稍优于RSMP算法。以长度N=256的稀疏度K=30高斯稀疏信号和稀疏度K=20服从0-1分布的稀疏信号为目标，信噪比SNR=30dB，观测次数M(60,70,...,130)，对于每个固定的观测次数分别进行500次独立重复试验，观测次数M和NMSE之间的关系曲线如图4-6所示50 第四章随机原子选择策略研究(a)(b)图4-6观测次数和归一化均方误差变化曲线(a)高斯信号NMSE变化曲线；(b)0-1信号NMSE变化曲线由图4-6可以看出，对与不同类型信号的重建，在信号稀疏度固定的情况下，各算法的NMSE性能均随着观测次数的增加而提高。对于高斯信号的重构，锦标赛策略改进型算法的NMSE性能最优，在观测次数较少时，gOMP算法的NMSE性能优于RSMP算法和排序选择策略改进型算法，当观测次数增大时且各算法的NMSE性能趋于稳定时，RSMP算法和排序选择策略改进型算法的NMSE性能远51 电子科技大学硕士学位论文优于gOMP算法。对于0-1信号的重构，RSMP算法、锦标赛选择策略和排序选择策略的改进型算法的NMSE性能优于L=3条件下的gOMP算法的重建概率，其中锦标赛策略改进型算法的NMSE性能稍优于RSMP算法和排序选择策略的改进型算法的NMSE性能。综上，在无噪声的条件下，对高斯信号的重构，RSMP算法(轮盘赌式原子选择)的重建概率略低于该环境下L取最优值时的gOMP算法；实现高斯信号的准确重建，排序式原子选择策略改进型算法必需的观测次数最多，当观测次数足够时，排序式原子选择策略改进型算法的重构概率稍优于RSMP算法，它的概率与该环境下L取最优值时的gOMP算法近似；实现高斯信号准确重构，锦标赛式原子选择策略改进算法必需的观测次数最少，同时该算法的重建概率最高。对0-1信号的重构，RSMP算法必需的观测次数比该环境下L取最优值时的gOMP算法更少，它的重建概率也远远超过了gOMP算法；排序式原子选择和锦标赛式原子选择策略改进算法保持了RSMP算法的优越性，其中锦标赛式原子选择策略改进算法的重构性能最好。在信号加噪声的情况下，对高斯信号的重构，实现信号的准确重构，RSMP算法和排序式原子选择策略改进型算法实现信号准确重建所必需的观测次数比L取最优值时的gOMP算法稍多，但是当观测次数足够时，RSMP算法和排序式原子选择策略改进型算法的NMSE性能比gOMP算法更优，也就是说它们比gOMP算法具有更强的噪声鲁棒性；与gOMP算法相比，锦标赛式原子选择策略改进型算法不仅必需的观测次数更少，而且该算法的NMSE性能更优。对0-1信号的重建，RSMP算法、排序式原子选择和锦标赛式原子选择策略改进算法实现信号准确重建所必需的观测次数比该环境下L取最优值时的gOMP算法更少，并且它们的NMSE性能远优于gOMP算法；其中锦标赛式原子选择策略改进算法的NMSE性能最好，该算法的噪声鲁棒性最强。4.3本章小结本章结合遗传算法中三类选择算子“择优”思想，提出了三种随机原子选择策略，并详述了各随机策略的原子选择流程。利用上述随机策略对RSMP算法进行改进，并将改进型算法与RSMP算法和gOMP算法进行对比，大量的仿真实验结果表明了这几种原子选择策略对于正确原子支撑集的搜索能力更强，并且这些改进型算法的噪声鲁棒性更好。对于本章所提及的三类随机原子选择策略中，锦标赛式原子选择策略改进算法的性能最优。52 第五章总结与展望第五章总结与展望5.1全文总结压缩感知（CS）理论突破了香农采样定理的限制，在很大程度上丰富了信号采样理论，拓宽了相关领域研究的视野，对多个领域的发展有着积极的促进作用。因而压缩感知理论自其被提出以来就受到各界优秀学者的关注，其中信号的稀疏表示、信号的观测和信号的重构是压缩感知的主要研究内容，其中信号重构是研究CS理论最为重要的一环，高效且稳定的重构算法是将CS理论推向实际应用的关键。本文介绍了CS模型下信号处理框架，梳理了压缩感知重建算法研究现状，着重介绍了匹配追踪类算法，并在此基础上提出了改进方法。本文的主要内容和创新点如下：（1）介绍了CS的由来及其理论基础，重点介绍了几种经典的匹配追踪类贪婪重构算法，包括OMP算法、StOMP算法、ROMP算法、CoSaMP算法、SP算法和SAMP算法，并通过大量的仿真实验比较了这些重构算法的性能。（2）对多路径匹配追踪(MMP)算法和广义正交匹配追踪(gOMP)算法的原子选择进行深入剖析，分析了原子选择对算法重建性能的影响，在选择原子时采用随机原子选择策略，提出了随机策略匹配追踪算法(RSMP)。RSMP算法以单路径随机搜索的方式拓充原子支撑集，该算法与MMP算法相比具有数学上更加简单、编程方便的优点。与gOMP算法相比RSMP算法在每次迭代过程中自适应的随机选取适量原子来拓充原子支撑集，不仅减少了算法的输入控制参量，消除了gOMP算法对预定义值L的依赖；而且提高了算法对不同类型信号的重建性能，且大量的仿真实验结果证明了RSMP算法较gOMP算法具有更强的噪声鲁棒性。（3）进一步对随机原子选择策略进行研究，结合遗传算法中选择算子“择优”思想，提出了多种随机原子选择策略，并详述了原子选择的流程。通过大量仿真实验证明了随机原子选择策略改进型算法具有更好的重建性能。这些工作为匹配追踪类贪婪算法的原子选择方法提供了新思路。5.2未来工作的展望压缩感知理论（CS）自提出来便吸引了大量学者的关注，在十余年的发展过程中，不断的有新的CS重构算法被提出，这些新型改进算法都朝着更高的重建精53 电子科技大学硕士学位论文度，更快的重构速度，更强的噪声鲁棒性的方向发展。然而CS理论并没有很好的落实在实际应用中，说明了现有的CS理论还有待进一步完善。由于本人水平的局限和课题时间的约束，本文对CS重构算法的研究的还不够深入，目前，CS理论的研究工作仍然存在着很多亟待解决的问题。（1）CS重构算法对于越稀疏的信号的重建性能越好，依据被测信号特征设计出能够更加稀疏表示信号的稀疏基来改善信号重建效果是未来的一个研究方向。（2）信号重建对于稀疏度先验知识的依赖，使得在稀疏度估计不准确的时候，很难做到原始信号的准确重建，盲稀疏度下信号的准确重构算法的研究也是将来的一个研究方向。（3）随机原子选择策略能够很好的提高算法的性能，然而对不同信号要用何种随机选择方法才能更有效的重构原始信号是将来的一个研究方向。（4）更高重建精度，更小的计算复杂度，更强的噪声鲁棒性的CS重构算法是人们一直追求的目标。54 致谢致谢光阴荏苒，研究生生活即将结束，在三年的科研生活中，我得到了许多关怀和帮助，此刻向他们表达我诚挚的谢意！首先，感谢我的导师马凯学教授，本论文的顺利完成离不开马教授的耐心指导。马教授专业理论知识很强，理论实践经验丰富，学术科研态度严谨，为我树立了一个榜样，对今后的学习和生活有着积极的影响。在此，再次马教授表示我深深的感激之情，并祝愿您在之后的科研中取得更大的成就！同时，感谢给予我帮助的林川副教授，林教授在论文的完成过程中给予了很多指导性意见，使我的研究和写作过程更加顺利。尤其感谢卿安永教授，卿教授学识渊博，对优化理论研究颇深，看事情的角度独特，每次向卿教授请教问题时，卿教授的点播总让我有醍醐灌顶之感。感谢教研室同学徐强、邓正林、王艳丽、易亮，大家共同研讨问题，生活中互相帮助；感谢博士师兄孟杨、赵怿哲、刘浩、张成，在科研方面给予的热心帮助；感谢室友王影、何秋阳、游伊莎一路的陪伴，在我因外界因素而沮丧、失落的时候给予我的鼓励和支持。最后，感谢三年来给予我关心与帮助的所有老师和同学。55 电子科技大学硕士学位论文参考文献[1]C.E.Shannon.AmathematicaltheoryofCommunication[J].BellSystemTechnicalJournal,1948:623-656[2]金坚,谷源涛,梅顺良.压缩采样技术及其应用[N].电子与信息学报,2010[3]E.J.CandèsCompressiveSampling[C].ProceedingsoftheInternationalCongressofMathematicians,2006,969-985[4]E.J.Candès,J.Romberg.Sparsityandincoherenceincompressivesampling[J].InverseProblems,2007,23(3):969-985[5]E.J.Candès,J.Romberg,T.Z.Tao.RobustUncertaintyPrinciplesExactSignal[J].IEEETransalctionOnInformationTheory,2006,52(2):489-509[6]W.S.Lu.Compressedsensingandsparesignalprocessing[EB/OL].https://wenku.baidu.com/view/ef1d9405bed5b9f3f90f1c09.html,July16,2017[7]A.C.Gurbuz,J.H.McClellan,R.Waymond.CompressiveSensingforGPRImaging[J].2007ConferenceRecordoftheForty-FirstAsilomarConferenceonSignals,SystemsandComputers,SystemsandComputers,2007,2223-2227[8]M.F.Duarte,M.A.Davenport,D.Takhar,etal.Single-pixelimagingviacompressivesampling[M].IEEESignalProcessingMagazine.2008,83-91[9]J.Wright,A.Y.Yang,A.Ganesh,et.al.Robustfacerecognitionviasparserepresentation[C].IEEETransactiononPatternAnalysisMachineIntelligence,2009,210-227[10]A.B.Suksmono,E.Bharata,A.A.Lestari,etal.CompressiveStepped-FrequencyContinuous-WaveGround-PenetratingRadar[J].IEEEGeoscienceandRemoteSensingLetters,2010,7(4):665-669[11]A.Masoum,N.Meratnia,P.J.MHavinga.ADistributedCompressiveSensingTechniqueforDataGatheringinWirelessSensorNetworks[C].The4thInternationalConferenceonEmergingUbiquitousSystemsandPervasiveNetworks,2013,207-216[12]H.D.Kurniawan,A.B.Suksmono.ACompressive-SamplingStepped-FrequencyContinuousWaveSodarSystem[J].201610thInternationalConferenceonTelecommunicationSystemsServicesandApplications,2016,1-4[13]J.J.Mecherya,R.MbCompressivesensingbasedunderwaterchannelestimation[C].7thInternationalConferenceonAdvancesinComputingandCommunications,2017,683-690[14]石光明,刘丹华,高大化,等.压缩感知理论及其研究进展[N].电子学报,200956 参考文献[15]余慧敏,方广有.压缩感知理论在探地雷达三维成像中的应用[N].电子与信息学报,2010[16]X.Y.Jiang,M.Li,Y.Yao,et.al.OvercompleteRadonbasesfortargetpropertymanagementinsensor[J].Proceedingsofthe10thACM/IEEEInternationalConferenceonInformationProcessinginSensorNetworks,2011:25-36[17]J.F.Chen,Y.H.Li,J.Q.Wang,etal.ACompressiveSensingImagingAlgorithmforMillimeter-waveSyntheticApertureImagingRadiometerinNear-field[C].2013Asia-PacificMicrowaveConferenceProceedings,2013,972-974[18]K.X.Tian,J.Li,D.Q.Wang.ANoise-ResistantUWBChannelEstimationSchemeBasedonCompressedSensing[J].2016IEEEInternationalConferenceonInternetofThingsandIEEEGreenComputingandCommunicationsandIEEECyber,PhysicalandSocialComputingandIEEESmartData,2016,675-679[19]A.C.Gilbert,S.Guha,P.Indy,etal.Near-OptimalSparseFourierRepresentationsviaSampling[C].Proceedingsofthe34thAnnualACMSymposiumonTheoryofComputing,NewYork,2000,152-161[20]A.C.Gilbert,M.Straukrishnan,M.Strauss.Improvedtimeboundsfornear-optimalsparseFourierrepresentations[C].ProceedingsofSPIEWaveletsXI,SanDiego,2005,398-412[21]A.C.Gilbert,M.J.Strauss,J.A.Tropp,etal.Algorithmiclineardimensionreductioninthel1normforsparsevectors[C].Proceedingsofthe44thAnnualAllertonConferenceonCommunication,ControlandComputing,Allerton,2006,1-9[22]E.J.Candes,B.Recht.ExactMatrixCompletionviaConvexOptimization[J].FoundationsofComputationalMathematics,2008,9(6):717-772[23]S.G.Mallat,Z.Zhang.MatchingPursuitsWithTime-FrequencyDictionaries[C].IEEETransactionsonSignalProcessing,1993,3397-3415[24]W.Lu,N.Vaswani.ModifiedBasisPursuitDenoising(modified-BPDN)fornoisycompressivesensingwithpartiallyknownsupport[C].IEEEInternationalConferenceonAcousticsSpeech&SignalProcessing,2010,3926-3929[25]Y.Nesterov.Gradientmethodsforminimizingcompositeobjectivefunction[J].MathematicalProgramming,2013,140(1):125-161[26]I.Daubechies,M.Defrise,C.D.Mol.Aniterativethresholdingalgorithmforlinearinverseproblemswithasparsityconstraint[J].Math,2004,57:1413-1457[27]A.Beck,M.Teboulle.AFastIterativeShrinkage-ThresholdingAlgorithmforLinearInverseProblems[J].SIAMJournalonImagingSciences,2009,2(1):183-20257 电子科技大学硕士学位论文[28]J.A.Tropp,A.C.Gilbert.SignalRecoveryFromRandomMeasurementsViaOrthogonalMatchingPursuit[J].IEEETransactionsonInformationTheory,2007,53(12):4655-4666[29]D.L.Donoho,Y.Tsaig,I.Drori,J.L.Starck.SparsesolutionofunderdeterminedSystemsoflinearequationsbystagewiseorthogonalmatchingpursuit[J].IEEETransactionsonInformationTheory,2012,58(2):1094-1121[30]D.Needell,R.Vershynin.Uniformuncertaintyprincipleandsignalrecoveryviaregularizedorthogonalmatchingpursuit[J].FoundationsofComputationalMathematics,2009,9(3):317-334[31]D.Needell,J.A.Tropp.CoSaMP:Iterativesignalrecoveryfromincompleteandinaccuratesamples[J].AppliedandComputationalHarmonicAnalysis,2009,26(3):301-321[32]D.Wei,S.Guha,P.Indy,etal.SubspacePursuitforCompressiveSensingSignal[J].IEEETransactionsonInformationTheory,2009,55(5):2230-2249[33]T.T.Do,L.Gan,N.Nguyen,etal.SparsityAdaptiveMatchingPursuitSlgorithmforPracticalCompressedSensing[C].AsilomarConferenceonSignals,PacificGrove,2008,581-587[34]J.Wang,S.Kwon,B.Shim.GeneralizedOrthogonalMatchingPursuit[C].IEEETransactionsonSignalProcessing,2012,6202-6216[35]S.Kwon,J.Wang,B.Shim.MultipathMatchingPursuit[J].IEEETransactiononInformationTheory,2014,60(5):2986-3001[36]W.Q.Huang,J.L.Zhao,Z.Q.Lv,etal.SparsityandStep-sizeAdaptiveRegularizedMatchingPursuitAlgorithmforCompressedSensing[C].2014IEEE7thJointInternationalInformationTechnologyandArtificialIntelligenceConference,2014,536-540[37]贾艳云,赵航芳.压缩传感-稀疏信号的采样与重构[J].声学与电子工程,2010,13-17[38]闫敬文,刘蕾,屈小波.压缩感知及其应用[M].国防工业出版社,2015[39]S.S.Cheny,D.L.Donoho,A.S.Michael.Atomicdecompositionbybasispursuit[J].1998,20(1):33-61[40]R.Baraniuk.compressivesensing[J].IEEEsignalprocessingmagazine,2007[41]Y.Tsaig,D.L.Donoho.ExtensionsofCompressedSensing[J].SignalProcessing,2006,549-571[42]F.Sebert,Y.M.Zou,L.Ying.Toeplitzblockmatricesincompressedsensingandtheirapplicationsinimaging[C].InternationalConferenceonInformationTechnologyandApplicationsinBiomedicine,2008,47-50[43]G.Zhang,S.H.Jiao,X.L.Xu,etal.Compressedsensingandreconstructionwithbernoullimatrices[C].IEEEInternationalConferenceonInformationandAutomation,2010,455-46058 参考文献[44]E.J.Candes,T.Tao.DecodingbyLinearPrograming[J].IEEETransactiononInformationTheory,2005,51(12):4203-4215[45]孙文瑜,徐成贤,朱德通.最优化方法[M],高等教育出版社,2004[46]JGalletly.EvolutionaryAlgorithmsinTheoryandPractice:EvolutionStrategies,EvolutionaryProgramming,GeneticAlgorithms[M].OxfordUniversityPress,199659 电子科技大学硕士学位论文攻读硕士学位期间取得的成果[1].ZhenglinDeng,MingyaoHe,AnyongQing,et.al.Designofthinmultilayerplanarabsorberforactivemillimeter-waveimagingsystem[J].2017InternationalAppliedComputationalElectromagneticsSocietySymposium(ACES).2017:1-2.[2].JiefengZang,AnyongQing,MingyaoHe,et.al.Designofspatialfilterappliedtomillimeterwavefastimagingsystem[J].2017InternationalAppliedComputationalElectromagneticsSocietySymposium(ACES).2017:1-260
