压缩感知技术研究进展分析

压缩感知技术研究进展摘要：信号采样是联系模拟信源和数字信息的桥梁.人们对信息的巨量需求造成了信号采样、传输和存储的巨大压力.如何缓和这种压力又能有效提取承载在信号中的有用信息是信号与信息解决中急需解决的问题之一.近年国际上出现的压缩感知理论(CompressedSensing,CS)为缓和这些压力提供理解决办法.本文综述了CS理论框架及核心技术问题,并介绍了仿真实例、应用前景,评述了其中的公开问题,对研究中现存的难点问题进行了探讨,最后对CS技术做了一下总结和展望.核心词：压缩感知；稀疏表达；观察矩阵；编码；解码AdvancesinTheoryandApplicationofCompressedSensingAbstract：Samplingisthebridgebetweenanalogsourcesignalanddigitalsignal.Withtherapidprogressofinformationtechnologies,thedemandsforinformationareincreasingdramatically.Sotheexistingsystemsareverydifficulttomeetthechallengesofhighspeedsampling,largevolumedatatransmissionandstorage.Howtoacquireinformationinsignalefficientlyisanurgentprobleminelectronicinformationfields.Inrecentyears,anemergingtheoryofsignalacquirement.compressedsensing(CS)providesagoldenopportunityforsolvingthisproblem.Thispaperreviewsthetheoreticalframeworkandthekeytechnicalproblemsofcompressedsensingandintroducesthelatestdevelopmentsofsignalsparserepresentation,designofmeasurementmatrixandreconstructionalgorithm.ThenthispaperalsoreviewsseveralopenproblemsinCStheoryanddiscussestheexistingdifficultproblems.Intheend,theapplicationfieldsofcompressedsensingareintroduced.Keywords:compressedsensing;sparserepresentation;theobservationmatrix;coding;decoding一、引言在过去的半个世纪里，奈奎斯特采样定理几乎支配着全部的信号或图像等的获取、解决、存储以及传输。它规定采样频率必须不不大于或等于信号带宽的两倍，才干不失真的重构原始信号。在许多实际应用中，例如高分辨率的数码装置及超带宽信号解决，高速采样产生了庞大的数据，为了减少存储，解决或传输成本，只保存其中少量的重要数据。由于采样后得到的大部分数据都被丢弃了，因此这种方式造成了采样资源的严重浪费。构想如果在采样的同时直接提取信号的少量重要信息，就能够大大减少采样频率，节省资源，提高效率并且仍能够精确重构原始信号或图像。这就是Donoho、Candes以及Tao等人提出压缩感知（CompressedSensing、CompressiveSampling或CompressiveSensing，CS）理论的重要思想。压缩感知理论指出：如果信号在某个变换域是稀疏的或可压缩的，就能够运用一种与变换基不有关的观察矩阵将变换所得的高维信号投影到一种低维空间上，根据这些少量的观察值，通过求解凸优化问题就能够实现信号的精确重构。在传统理论的指导下，信号X的编解码过程如图1所示：编码端首先获得X的N点采样值，经变换后只保存其中K个最大的投影系数并对它们的幅度和位置编码，最后将编得的码值进行存储或传输。解压缩仅是编码过程的逆变换。事实上，采样得到的大部分数据都是不重要的，即K值很小，但由于奈奎斯特采样定理的限制，采样点数N可能会非常大，采样后的压缩是造成资源浪费的根本所在。CS较好的解决了这一问题，它将信号的采样、压缩及编码合并在了同一环节中，不通过N点采样的中间过程而直接得到信号的表达，其编解码过程如图2所示。可压缩信号X通过一种线性观察过程获得M个观察值后直接进行存储或传输。在满足一定的条件下接受端能够根据这M个观察值通过一种非线性优化过程恢复出原信号X。压缩感知的基本理论及核心问题假设有一信号，长度为，基向量为，对信号进行变换：显然是信号在时域的表达，是信号在域的表达。信号与否含有稀疏性或者近似稀疏性是运用压缩感知理论的核心问题，若(1)式中的只有个是非零值者仅经排序后按指数级衰减并趋近于零，可认为信号是稀疏的。信号的可稀疏表达是压缩感知的先验条件。在已知信号是可压缩的前提下，压缩感知过程可分为两步：设计一种与变换基不有关的维测量矩阵对信号进行观察，得到维的测量向量。由维的测量向量重构信号。2.1信号的稀疏表达文献[4]给出稀疏的数学定义：信号在正交基下的变换系数向量为，如果对于和，这些系数满足：则阐明系数向量在某种意义下是稀疏的．文献[1]给出另一种定义：如果变换系数的支撑域的势不大于等于，则能够说信号是项稀疏。如何找到信号最佳的稀疏域?这是压缩感知理论应用的基础和前提，只有选择适宜的基表达信号才干确保信号的稀疏度，从而确保信号的恢复精度。在研究信号的稀疏表达时，能够通过变换系数衰减速度来衡量变换基的稀疏表达能力。Candes和Tao研究表明，满足含有幂次(power-law)速度衰减的信号，可运用压缩感知理论得到恢复。近来几年，对稀疏表达研究的另一种热点是信号在冗余字典下的稀疏分解．这是一种全新的信号表达理论：用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子．字典的选择应尽量好地符合被逼近信号的构造，其构成能够没有任何限制．从从冗余字典中找到含有最佳线性组合的K项原子来表达一种信号，称作信号的稀疏逼近或高度非线性逼近。现在信号在冗余字典下的稀疏表达的研究集中在两个方面：(1)如何构造一种适合某一类信号的冗余字典；(2)如何设计快速有效的稀疏分解算法．这两个问题也始终是该领域研究的热点，学者们对此已做了某些探索，其中以非相干字典为基础的一系列理论证明得到了进一步改善．西安电子科技大学的石光明专家也对稀疏表达问题进行了认真研究，并基于多组正交基级联而成的冗余字典提出一种新的稀疏分解办法。2.2信号的观察矩阵用一种与变换矩阵不有关的测量矩阵对信号进行线性投影，得到线性测量值：测量值是一种维向量，这样使测量对象从维降为维。观察过程是非自适应的即测量矩阵少的选择不依赖于信号。测量矩阵的设计规定信号从转换为的过程中，所测量到的个测量值不会破坏原始信号的信息，确保信号的精确重构。由于信号是是可稀疏表达的，上式能够表达为下式：其中是一种矩阵。上式中，方程的个数远不大于未知数的个数，方程无拟定解，无法重构信号。但是，由于信号是K稀疏，若上式中的满足有限等距性质(RestrictedIsometryProperty，简称RIP)，即对于任意K稀疏信号和常数，矩阵满足：则K个系数能够从M个测量值精确重构。RIP性质的等价条件是测量矩阵和稀疏基不有关。现在，用于压缩感知的测量矩阵重要有下列几个：高斯随机矩阵，二值随机矩阵(伯努力矩阵)，傅立叶随机矩阵，哈达玛矩阵，一致球矩阵等。2.3信号的重构算法当矩阵满足RIP准则时。压缩感知理论能够通过对上式的逆问题先求解稀疏系数，然后将稀疏度为K的信号从维的测量投影值中对的地恢复出来。解码的最直接办法是通过范数下求解的最优化问题：从而得到稀疏系数的预计。由于上式的求解是个NP—HARD问题。而该最优化问题与信号的稀疏分解十分类似，因此有学者从信号稀疏分解的有关理论中寻找更有效的求解途径。文献[10]表明，最小范数下在一定条件下和最小范数含有等价性，可得到相似的解。那么上式转化为最小范数下的最优化问题：最小范数下最优化问题又称为基追踪(BP)，其惯用实现算法有：内点法和梯度投影法。内点法速度慢，但得到的成果十分精确：而梯度投影法速度快，但没有内点法得到的成果精确。二维图像的重构中，为充足运用图像的梯度构造。可修正为整体部分(TotalVariation，TV)最小化法。由于最小范数下的算法速度慢，新的快速贪婪法被逐步采用，如匹配追踪法(MP)和正交匹配追踪法(OMP)。另外，有效的算法尚有迭代阈值法以及多个改善算法。三、压缩感知仿真实例对256×256大小的8bit灰度lena图像进行仿真计算，由于数据量过大，将图像分为16×16大小的分块进行计算，稀疏矩阵采用DCT矩阵，观察矩阵采用高斯随机矩阵，重构算法采用OMP（正交匹配追踪）算法。MATLAB代码以下：在MATLABRb中的计算成果以下：原图像采样率0.7采样率0.5采样率0.3采用均方误差MSE评价重构后的图像质量。不同采样率下的计算时间与计算误差以下图所示：四、CS的应用前景能从少量的非有关观察值中高效获取可压缩信号的信息，CS的这一特点决定了其应用的广泛性。CS的应用领域涉及数据压缩、模拟/信息的转换、压缩成像、信道编码、信道预计、生物传感、语音识别、雷达成像、雷达遥感、学习理论及模式识别等诸多领域。在压缩成像方面，RICE大学已成功研制了“单像素”压缩数码摄影机，该相机不像传统相机那样获取原始信号的N个像素值，而是直接获取M个随机线性观察值，在实践中为取代传统相机迈出了实质性的一步。在通信领域，压缩感知也有着强大的生命力，由于无线多径信道普通状况下是稀疏的，即使在时延扩展很大时，大幅度的径的个数也极少，因此运用少量的导频就能获取未知信道的频域响应预计。另外压缩感知理论还可用于通信信道的错误检测、传感网络的分布式信源编码、认知无线电中的频谱感知等。五、研究的公开问题5.1p2范数优化问题压缩感知理论在图像压缩编码等方面也应当有很广泛的前景,但由于信号的恢复办法是建立在12范数意义下,数据之间尚有很大的冗余性没有去除,相比传统的小波变换编码,压缩感知理论应用于图像压缩的效果还不抱负.p2范数的优化是提高基于压缩感知理论的压缩算法效果的必经之路.p2范数的优化办法是一种公开问题(openproblem),对它的研究将推动压缩感知理论在压缩方面的应用,含有很深远的意义.p2范数意义下的优化问题是一种凸函数优化问题,现在已有某些成熟的算法,但p2范数的优化是一种非凸函数的优化问题,其中有诸多数学问题有待解决.有关p2范数非凸函数优化问题,也有某些学者开展研究.如RickChartrand[用典型的合成数据做了某些实验,表明在一定的稀疏误差范畴内,能够得到最小值.在文献[19]中,他进一步给出了变换基空间内的系数严格的等距条件(restrictedisometry),由于有了严格的约束,完全适合于大多数实际的信号.笔者盼望通过借用自然优化计算以及将p2范数非凸函数转换为近似凸函数优化等办法,提出一种新的求解p2范数范数的优化问题,以实现在p2范数意义下的压缩感知理论的信号恢复,最大可能减少信号的冗余.该思路正在研究之中.5.2观察矩阵与恢复性能关系前面提到,观察矩阵与稀疏变换基的不相干特性是压缩感知理论含有良好性能的基础.由于随机高斯分布的观察矩阵含有与其它固定基都不有关的特性而被广泛采用.但在实际的应用中,这种观察矩阵存在存储矩阵元素容量巨大、计算复杂度高的缺点.文献[20]提出一种部分傅立叶变换采样的办法.它首先对信号进行傅立叶变换再对变换系数进行随机抽取.这种随机抽取使得各观察值含有随机不有关的特性.由于变换时能够采用快速算法而使得计算量大大减少.但由于傅立叶基仅与在空域稀疏的信号不相干,故这种观察矩阵的应用范畴受到很大的限制.另外,采用随机滤波器滤波也是一种有效的观察办法,但是现在仍缺少理论基础,也缺少对其性能的具体分析.文献[21]将伪高斯矩阵和部分傅立叶办法巧妙的结合在一起,提出了一种构造化的随机观察矩阵设计办法,这种观察矩阵含有与全部基不相干的特性,同时也有较快的计算速度.总结以上的工作能够得出以下结论:观察矩阵的随机不有关特性是对的恢复信号的一种充足条件,观察矩阵和信号的高度不相干是有效恢复信号的确保.但是,现在仍然无法拟定随机不有关特性与否是最优恢复信号的必要条件,这仍是一种公开问题.另外,如何衡量观察矩阵的不相干特性,以及它们与恢复性能之间的关系也是一种尚未解决的问题.另外,自适应的观察矩阵设计也是观察矩阵设计的一种重要方面.在众多有关压缩感知理论的文献中,大部分的观察矩阵都是预先设计好的,不需要根据观察信号而自适应变化.事实上,如果能够进行自适应的观察,压缩感知的压缩性能能够得到进一步的提高.在文献[22]中,作者用Bayes预计的观点对压缩感知做出了一种全新的解释.在文献中,压缩感知的解的可信度能够通过微分熵来衡量,这样在已有观察的基础上,下一次最优的观察向量应当使问题解的微分熵下降最快,它能够由已有的观察向量和观察值唯一拟定.而且,幸运的是这一特性在编码端和解码端是同样的.由于对观察矩阵的最优化设计,BayesianCS与使用普通的随机观察矩阵相比,在同等观察次数的状况下,性能得到了很大的提高.固然这也付出了一定的代价,计算最优观察向量需要很大的计算量,因此能够简捷有效地拟定最优观察向量仍是这方面的一种有待解决的问题.5.3分布式压缩感知理论(DistributedCompressedSensing,DCS)现在,针对单个信号的压缩感知的研究和应用已经开展得比较进一步,但是对分布式信号的解决仍然研究得不够.例如,对于一种包含大量传感器节点的传感器网络,每个传感器都会采集大量的数据,这些数据将会传输到一种控制中心,也会在各个节点之间传输.显然,在这种分布式传感器网络中,数据传输对功耗和带宽的需求非常大,那么,如何对分布式信号进行压缩以减少通信压力成为非常急迫的需求.,Haupt和Nowak将压缩感知理论应用到多个信号的环境中,然而他们的办法仅研究了多个信号的互有关性,却没有考虑单个信号的内有关性.Baron等人在压缩感知理论的基础上提出了分布式压缩感知(DCS)[18],进一步扩展了压缩感知理论的应用,将单信号的压缩采样扩展到了信号群的压缩采样,它着重研究如何运用信号内有关性和互有关性对多个信号进行联合重构.这种联合重构的重要意义在于,相对于压缩感知,分布式压缩感知可节省相称可观的观察数目.文献[18]中的实验成果表明对于两个有关的信号可节省的观察数目大概为30%.DCS理论建立在一种称之为信号群的/联合稀疏(JSM)0概念上.它指出,如果多个信号都在某个基下稀疏,并且这些信号彼此有关,那么每个信号都能够通过运用另一种不有关基(例如一种随机矩阵)进行观察和编码,得到远少于信号长度的编码.将每个编码后的少量数据传输到解码端,那么在适宜的条件(如JSM21)下,解码端运用接受到的少量数据就能够精确重建每一种信号.文献[18]系统地叙述了DCS理论及其应用,提出了对应的压缩感知办法及恢复算法,并采用稀疏的随机投影矩阵作为观察矩阵,具体分析了分布式压缩感知理论的观察过程,而文献[23]则从重构误差预计的角度对分布式压缩感知理论进行了研究.DCS理论为分布式信号的解决提供了新的办法,现在的热点和难点重要集中在如何将其应用到多个复杂的实际传感器网络中.在某种意义上,DCS是一种分布式信源压缩的框架,它在很长时间内都将是一种含有挑战性的公开难题.六总结与展望压缩感知理论运用了信号的稀疏特性,将原来基于奈奎斯特采样定理的信号采样过程转化为基于优化计算恢复信号的观察过程.也就是运用长时间积分换取采样频率的减少,省去了高速采样过程中获得大批冗余数据然后再舍去大部分无用数据的中间过程,从而有效缓和了高速采样实现的压力,减少了解决、存储和传输的成本,使得用低成本的传感器将模拟信息转化为数字信息成为可能.这种新的采样理论将可能成为将采样和压缩过程合二为一的办法的理论基础.本文对压缩感知理论框架的全过程进行了描述,具体叙述了压缩感知理论所涉及的核心技术,综述了国内外研究成果、存在的公开问题及最新的有关理论扩展,如冗余字典下的压缩感知理论、模拟2信息理论、分布式压缩感知理论等.并对其中的问题进行了概括性讨论.压缩感知理论的研究已有了某些成果,但是仍然存在大量的问题需要研究.概括为下列几个方面:对于稳定的重构算法与否存在一种最优的拟定性的观察矩阵;如何构造稳定的、计算复杂度较低的、对观察次数限制较少的重构算法来精确地恢复可压缩信号;如何找到一种有效且快速的稀疏分解算法是冗余字典下的压缩感知理论的难点所在;如何设计有效的软硬件来应用压缩感知理论解决大量的实际问题,这方面的研究还远远不够;对于p2范数优化问题的求解研究还远远不够;含噪信号或采样过程中引入噪声时的信号重构问题也是难点所在,研究成果尚不抱负.另外,压缩感知理论与信号解决其它领域的融合也远不够,如信号检测、特性提取等.CS理论与机器学习等领域的内在联系方面的研究工作已经开始.压缩感知理论是新诞生的,即使尚有许多问题待研究,但它是对传统信号解决的一种极好的补充和完善,是一种含有强大生命力的理论,其研究成果可能对信号解决等领域产生重大影响参考文献[1]石光明.刘丹华.高大化.刘哲.林杰.王良君压缩感知理论及其研究进展-ACTAElectronicaSinica，37(5)[2]张锐基于压缩感知理论的图像压缩初步研究-ComputerKnowledgeAndTechnology，6(4)[3]CandesE,RombergJ,TaoT.Robustuncertaintyprinciples:Exactsignalreconstructionfromhighlyincompletefrequencyinformation[J].IEEETrans.InformationTheory,,52(4):489-509．[4]ECandesandJRomberg,Quantitativerobustuncentaintyprinciplesandoptimallysparsedecompositions[J].FoundationsofComputMath,,6(2):227-218．[5]ECandès.TTaoNearoptimalsignalrecoveryfromrandomprojections:Universalencodingstrategies(12)[6]DLDonohoCompressedsensing(04)[7]BKashin.Thewidthsofcertainfinitedimensionalsetsandclassesofsmoothfunctions[J]．IzvAkadNaukSSSR.1977,41(2):334-351．[8]ECandèsCompressivesampling[9]喻玲娟.谢晓春压缩感知理论介绍-VideoEngineering，32(12)[10]DONOHOD.TSAIGYExtensionsofcompressedsensing(03)[11]GuangmingShi.JieLin.XuyangChen.FeiQi,DanhuaLiuLiZhangUWBechosignaldetectionwithultralowratesamplingbasedoncompressedsensing(04)[12]张春梅.尹忠科.肖明霞基于冗余字典的信号超完备表达与稀疏分解-科学通报(06)[13]VTemlyakovNonlinearMethodsofApproximation[IMIResearchReports][14]FIGUEIREDOMAT.NOWAKRD.WRIGHTSJGradientprojectionforsparsereconstruction:applicationtocompressedsensingandotherinvemeproblems(04)[15]SMallat.杨力华.戴道清.黄文良信号解决的小波导引[16]覃凤清.数字图像压缩综述[J].宜宾学院学报,(6)[17]刘丹华.石光明.周佳社一种冗余字典下的信号稀疏分解新办法-西安电子科技大学学报（自然科学版）(02)[18]DBaron,MBWakin,MDuarte,etc.Distributedcompressedsensing[OL].DCS11.[19]RChartrand.ExactReconstructionofSparseSignalsviaNon2convexMinimization[J].IEEESignalProcessingLetters.,14(10):7072710.[20]EJCandes,JRomberg.Sparsityandincoherenceincompres2sivesampling[J].InverseProblems.,23(3):9692985.[21]TTDo,TD.Tran,LGan.Fastcompressivesamplingwithstructurallyrandommatrces[OL].[22]SJi,YXue,LCarin.Bayesiancompressivesensing[J].IEEETransactionsSignalProcessing,,56(6):.[23]WWang,MGarofalakis,KRamchandran.Distributedsparserandomprojectionsforrefinableapproxim2ation[A].Proceed2ingsoftheSixthInternationalSymposiumonInformationPro2cessinginSensorNetworks,(IPSN)[C].NewYork:As2sociationforComputingMachinery,.3312339.论文题目压缩感知技术研究进展中文摘要信号采样是联系模拟信源和数字信息的桥梁.人们对信息的巨量需求造成了信号采样、传输和存储的巨大压力.如何缓和这种压力又能有效提取承载在信号中的有用信息是信号与信息解决中急需解决的问题之一.近年国际上出现的压缩感知理论(CompressedSensing,CS)为缓和这些压力提供理解决办法.本文综述了CS理论框架及核心技术问题,并介绍了仿真实例、应用前景,评述了其中的公开问题,对研究中现存的难点问题进行了探讨,最后对CS技术做