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

压缩感知技术研究进展摘要：信号采样是联系模拟信源和数字信息桥梁.人们对信息巨量需求造成了信号采样、传输和存储巨大压力.如何缓解这种压力又能有效提取承载在信号中有用信息是信号及信息处理中急需解决问题之一.近年国际上出现压缩感知理论(CompressedSensing,CS)为缓解这些压力提供了解决方法.本文综述了CS理论框架及关键技术问题，并介绍了仿真实例、应用前景,评述了其中公开问题,对研究中现存难点问题进行了探讨,最后对CS技术做了一下总结和展望.关键词：压缩感知；稀疏表示；观测矩阵；编码；解码AdvancesinTheoryandApplicationofCompressedSensingAbstract：Samplingisthebridgebetweenanalogsourcesignalanddigitalsignal.Withtherapidprogressofinformationtechnologies,thedemandsforinformationareincreasingdramatically.Sotheexistingsystemsareverydifficulttomeetthechallengesofhighspeedsampling,largevolumedatatransmissionandstorage.Howtoacquireinformationinsignalefficientlyisanurgentprobleminelectronicinformationfields.Inrecentyears,pressedsensing(CS)providesagoldenopportunityforsolvingthisproblem.Thispaperreviewsthetheoreticalframeworkandthekeytechnicalproblemsofcompressedsensingandintroducesthelatestdevelopmentsofsignalsparserepresentation,designofmeasurementmatrixandreconstructionalgorithm.ThenthispaperalsoreviewsseveralopenproblemsinCStheoryanddiscussestheexistingdifficultproblems.Intheend,theapplicationfieldsofcompressedsensingareintroduced.Keywords:compressedsensing;sparserepresentation;theobservationmatrix;coding;decoding一、引言在过去半个世纪里，奈奎斯特采样定理几乎支配着所有信号或图像等获取、处理、存储以及传输。它要求采样频率必须大于或等于信号带宽两倍，才能不失真重构原始信号。在许多实际应用中，例如高分辨率数码装置及超带宽信号处理，高速采样产生了庞大数据，为了降低存储，处理或传输成本，只保留其中少量重要数据。由于采样后得到大部分数据都被丢弃了，所以这种方式造成了采样资源严重浪费。设想如果在采样同时直接提取信号少量重要信息，就可以大大降低采样频率，节约资源，提高效率而且仍能够精确重构原始信号或图像。这就是Donoho、Candes以及Tao等人提出压缩感知(CompressedSensing、CompressiveSampling或CompressiveSensing，CS)理论主要思想。压缩感知理论指出：如果信号在某个变换域是稀疏或可压缩，就可以利用一个及变换基不相关观测矩阵将变换所得高维信号投影到一个低维空间上，根据这些少量观测值，通过求解凸优化问题就可以实现信号精确重构。在传统理论指导下，信号X编解码过程如图1所示：编码端首先获得XN点采样值，经变换后只保留其中K个最大投影系数并对它们幅度和位置编码，最后将编得码值进行存储或传输。解压缩仅是编码过程逆变换。实际上，采样得到大部分数据都是不重要，即K值很小，但由于奈奎斯特采样定理限制，采样点数N可能会非常大，采样后压缩是造成资源浪费根本所在。CS很好解决了这一问题，它将信号采样、压缩及编码合并在了同一步骤中，不经过N点采样中间过程而直接得到信号表示，其编解码过程如图2所示。可压缩信号X通过一个线性观测过程获得M个观测值后直接进行存储或传输。在满足一定条件下接收端可以根据这M个观测值通过一个非线性优化过程恢复出原信号X。二、压缩感知基本理论及核心问题假设有一信号f(fGRn)，长度为N，基向量为中(i=1,2,...,N)，对信i号进行变换：f二寸ay或f=*ai=1显然f是信号在时域表示，a是信号在乎域表示。信号是否具有稀疏性或者近似稀疏性是运用压缩感知理论关键问题，若⑴式中a只有K个是非零值(N>>K)者仅经排序后按指数级衰减并趋近于零，可认为信号是稀疏。信号可稀疏表示是压缩感知先验条件。在已知信号是可压缩前提下，压缩感知过程可分为两步：(1)设计一个及变换基不相关M义N(M«N)维测量矩阵对信号进行观测，得到M维测量向量。(2)由M维测量向量重构信号。2.1信号稀疏表示文献［4］给出稀疏数学定义：信号X在正交基乎下变换系数向量为@=¥TX，假如对于0<p<2和R>0，这些系数满足：||01|三(Z10.1p)1/p<Ri则说明系数向量0在某种意义下是稀疏．文献［1］给出另一种定义：如果变换系数°厂<X，+i>支撑域亿0产0｝势小于等于K，则可以说信号X是K项稀疏。如何找到信号最佳稀疏域?这是压缩感知理论应用基础和前提，只有选择合适基表示信号才能保证信号稀疏度，从而保证信号恢复精度。在研究信号稀疏表示时，可以通过变换系数衰减速度来衡量变换基稀疏表示能力。Candes和1@0研究表明，满足具有幂次(power-law)速度衰减信号，可利用压缩感知理论得到恢复。最近几年，对稀疏表示研究另一个热点是信号在冗余字典下稀疏分解．这是一种全新信号表示理论：用超完备冗余函数库取代基函数，称之为冗余字典，字典中元素被称为原子．字典选择应尽可能好地符合被逼近信号结构，其构成可以没有任何限制．从从冗余字典中找到具有最佳线性组合K项原子来表示一个信号，称作信号稀疏逼近或高度非线性逼近［12,13］。目前信号在冗余字典下稀疏表示研究集中在两个方面：(1)如何构造一个适合某一类信号冗余字典；(2)如何设计快速有效稀疏分解算法．这两个问题也一直是该领域研究热点，学者们对此已做了一些探索，其中以非相干字典为基础一系列理论证明得到了进一步改进．西安电子科技大学石光明教授也对稀疏表示问题进行了认真研究，并基于多组正交基级联而成冗余字典提出一种新稀疏分解方法［17］。2.2信号观测矩阵用一个及变换矩阵不相关M义N(M<<N)测量矩阵G对信号进行线性投影，得到线性测量值y：y=Gf测量值y是一个M维向量，这样使测量对象从N维降为M维。观测过程是非自适应即测量矩阵少选择不依赖于信号f。测量矩阵设计要求信号从f转换为y过程中，所测量到K个测量值不会破坏原始信号信息，保证信号精确重构。由于信号f是是可稀疏表示，上式可以表示为下式：其中0是一个MxN矩阵。上式中，方程个数远小于未知数个数，方程无确定解，无法重构信号。但是，由于信号是K稀疏，若上式中0满足有限等距性质(RestrictedIsometryProperty,简称RIP),即对于任意K稀疏信号f和常数5kg(0,1)，矩阵0满足：||0f||21-5<—2_2<1+5k11fl|2k则K个系数能够从M个测量值准确重构。RIP性质等价条件是测量矩阵^和稀疏基于不相关。目前，用于压缩感知测量矩阵主要有以下几种：高斯随机矩阵,二值随机矩阵(伯努力矩阵),傅立叶随机矩阵,哈达玛矩阵,一致球矩阵等。2.3信号重构算法当矩阵0满足RIP准则时。压缩感知理论能够通过对上式逆问题先求解稀疏系数a=*Tx，然后将稀疏度为K信号x从M维测量投影值y中正确地恢复出来。解码最直接方法是通过l0范数下求解最优化问题：minila||s.ty=O^aa l0从而得到稀疏系数估计。由于上式求解是个NP—HARD问题。而该最优化问题及信号稀疏分解十分类似,所以有学者从信号稀疏分解相关理论中寻找更有效求解途径。文献［10］表明，l1最小范数下在一定条件下和l0最小范数具有等价性，可得到相同解。那么上式转化为11最小范数下最优化问题：minilalls.ty=O^aa l111最小范数下最优化问题又称为基追踪(BP)，其常用实现算法有：内

点法和梯度投影法。内点法速度慢，但得到结果十分准确：而梯度投影法速度快，但没有内点法得到结果准确［14］。二维图像重构中，为充分利用clc： 早for 初■块没有卷盖到的地方■补口匕图像梯度结构。可修正为整体部分(1。1.严丫青号戈，tv)最小化法。由if <=ntic：iiic(i.3)=1111(^j);tic：end于l最小范数下算法速度慢，新快速贪婪法被逐渐采用，如匹配追踪法(MP)endiKFLnreadl/lerLa256,'ptr''1;还有迭代阈值法以及各种改进渭言;和正交匹配追踪法(OMP)。此外，有效算法还有迭代阈值法以及各种改进im2=Eerosljbm=16; 'bn=16;im2=Eerosljbm=16; 'bn=16;p=0.8;d=bn浴bn;forx=1:bx;府对每个小块妞里砌块划、三、压缩感知仿真实例先信号长度fory=1;by;b=inc((1+[s-1)*hm)t(x*bm)j(1+ )*bn):(y*bn));Kin=reshape(b,i1):sin=double(ain); 先输入信号ena图像进行仿真计算，，由于数据量过大，将图b^deiKn/bn);粉块数 Phi=randn［N,d);抬高斯随机矩阵皿.皿像分为16义16大小分块进行计算，稀疏矩阵采用。婕矩阵，观测矩阵采用s=Fhi*xm凫测量倡FTiLEaiidrFTiLEaiidr凤山；峪高斯随搬P阵T搬眦触代码如下辎降s=Phi*xin; %测量,值hat_y=zeros(13d); 为。MP算法Aug_t=[];aug_y=口；pcis_mira尸口；r_n=s;times=l;whilenonTL(r_n)>0.01

forcol=l:d;product(col)=abs(T(:jcol)?*r_n);end[valjpos]=m.az:(product);和二[Aug_tjT(;jpos)].T(;jpos)=-xero5t.Nj1);豆口&一尸(Aug_t?^Aug_t)*Aug_t?+3;r_n=3-Aug_t*aug_y;pos^jLt.ray(time3J=po3;111103=1imes-l-1;end高斯随机矩阵，重构算法采用OMP(正交匹配追踪)算法:hat_K=hat_y;hat_x2=inir(A)j*ha-t_K?; %复原信号b2=reshapg(hat_x2jbm,bn);%樨计算好的分治组合inc2((1+(k-1)*hn);GK+bn.)j(1+(y-LJ+bn);(y*bn))=b2;endendinic2=uint8(.iiiLc2);imZ-iiicZdznij1:nj;113Msim(sum(ab2(im-iji2).%2))/(n*cn);%一和误差toe;喻1■其时间figure(l>; *显示图像.intagesc(im2)：title(strest「呆祥率二'miimiZstt卬),牙块二丁...nun2str(bn)」：'：'3nun2str(bn)」,讦算时间=!」.・・r.un2str(round(toc/t)),?sJ[SE=?nini&tr(roundtmse*l0)/10)]1:colornapgray;E叵且第原图像 采样率0.7 采样率0.5 采样率0.3采用均方误差MSE评价重构后图像质量。不同采样率下计算时间及计算误差如下图所示：CS应用前景能从少量非相关观测值中高效获取可压缩信号信息，CS这一特点决定了其应用广泛性。CS应用领域涉及数据压缩、模拟/信息转换、压缩成像、信道编码、信道估计、生物传感、语音识别、雷达成像、雷达遥感、学习理论及模式识别等诸多领域。在压缩成像方面，RICE大学已成功研制了“单像素”压缩数码照相机，该相机不像传统相机那样获取原始信号N个像素值，而是直接获取M个随机线性观测值，在实践中为取代传统相机迈出了实质性一步。在通信领域，压缩感知也有着强大生命力，由于无线多径信道一般情况下是稀疏，即使在时延扩展很大时，大幅度径个数也很少，因此利用少量导频就能获取未知信道频域响应估计。此外压缩感知理论还可用于通信信道错误检测、传感网络分布式信源编码、认知无线电中频谱感知等。研究公开问题p2范数优化问题压缩感知理论在图像压缩编码等方面也应该有很广泛前景,但由于信号恢复方法是建立在12范数意义下,数据之间还有很大冗余性没有去除,相比传统小波变换编码,压缩感知理论应用于图像压缩效果还不理想.p2范数优化是提高基于压缩感知理论压缩算法效果必经之路.p2范数优化方法是一个公开问题(openproblem),对它研究将推动压缩感知理论在压缩方面应用，具有很深远意义.p2范数意义下优化问题是一个凸函数优化问题，目前已有一些成熟算法，但p2范数优化是一个非凸函数优化问题，其中有很多数学问题有待解决.有关p2范数非凸函数优化问题，也有一些学者开展研究.如RickChartrand［用典型合成数据做了一些实验,表明在一定稀疏误差范围内,可以得到最小值.在文献［19］中,他进一步给出了变换基空间内系数严格等距条件(restrictedisometry),由于有了严格约束,完全适合于大多数实际信号.笔者期望通过借用自然优化计算以及将p2范数非凸函数转换为近似凸函数优化等方法，提出一种新求解p2范数范数优化问题，以实现在p2范数意义下压缩感知理论信号恢复,最大可能减少信号冗余.该思路正在研究之中.观测矩阵及恢复性能关系前面提到,观测矩阵及稀疏变换基不相干特性是压缩感知理论具有良好性能基础.由于随机高斯分布观测矩阵具有及其它固定基都不相关特性而被广泛采用.但在实际应用中,这种观测矩阵存在存储矩阵元素容量巨大、计算复杂度高缺点.文献［20］提出一种部分傅立叶变换采样方法.它首先对信号进行傅立叶变换再对变换系数进行随机抽取.这种随机抽取使得各观测值具有随机不相关特性.由于变换时可以采用快速算法而使得计算量大大降低.但由于傅立叶基仅及在空域稀疏信号不相干,故这种观测矩阵应用范围受到很大限制.此外,采用随机滤波器滤波也是一种有效观测方法,不过目前仍缺乏理论基础,也缺少对其性能详细分析.文献［21］将伪高斯矩阵和部分傅立叶方法巧妙结合在一起,提出了一种结构化随机观测矩阵设计方法,这种观测矩阵具有及所有基不相干特性,同时也有较快计算速度.总结以上工作可以得出如下结论:观测矩阵随机不相关特性是正确恢复信号一个充分条件,观测矩阵和信号高度不相干是有效恢复信号保证.但是,现在仍然无法确定随机不相关特性是否是最优恢复信号必要条件,这仍是一个公开问题.另外,如何衡量观测矩阵不相干特性,以及它们及恢复性能之间关系也是一个尚未解决问题.另外,自适应观测矩阵设计也是观测矩阵设计一个重要方面.在众多有关压缩感知理论文献中,大部分观测矩阵都是预先设计好,不需要根据观测信号而自适应变化.实际上,如果能够进行自适应观测,压缩感知压缩性能可以得到进一步提高.在文献［22］中，作者用Bayes估计观点对压缩感知做出了一种全新解释.在文献中,压缩感知解可信度可以通过微分熵来衡量,这样在已有观测基础上,下一次最优观测向量应该使问题解微分熵下降最快,它可以由已有观测向量和观测值唯一确定.而且,幸运是这一特性在编码端和解码端是同样.由于对观测矩阵最优化设计,BayesianCS及使用普通随机观测矩阵相比，在同等观测次数情况下,性能得到了很大提高.当然这也付出了一定代价,计算最优观测向量需要很大计算量,所以能够简捷有效地确定最优观测向量仍是这方面一个有待解决问题.分布式压缩感知理论(DistributedCompressedSensing,DCS)目前,针对单个信号压缩感知研究和应用已经开展得比较深入,但是对分布式信号处理仍然研究得不够.例如,对于一个包含大量传感器节点传感器网络,每个传感器都会采集大量数据,这些数据将会传输到一个控制中心,也会在各个节点之间传输.显然,在这种分布式传感器网络中,数据传输对功耗和带宽需求非常大,那么,如何对分布式信号进行压缩以减少通信压力成为非常紧迫需求.2006年川@口口1WNowak将压缩感知理论应用到多个信号环境中，然而他们方法仅研究了多个信号互相关性,却没有考虑单个信号内相关性.Baron等人在压缩感知理论基础上提出了分布式压缩感知（DCS）[18],进一步扩展了压缩感知理论应用,将单信号压缩采样扩展到了信号群压缩采样,它着重研究如何利用信号内相关性和互相关性对多个信号进行联合重构.这种联合重构重要意义在于,相对于压缩感知,分布式压缩感知可节约相当可观观测数目.文献[18]中实验结果表明对于两个相关信号可节约观测数目大约为30%.DCS理论建立在一个称之为信号群/联合稀疏（JSM）0概念上.它指出,如果多个信号都在某个基下稀疏,并且这些信号彼此有关,那么每个信号都能够通过利用另一个不相关基（例如一个随机矩阵）进行观测和编码,得到远少于信号长度编码.将每个编码后少量数据传输到解码端，那么在适当条件（如JSM21）下，解码端利用接收到少量数据就能够精确重建每一个信号.文献[18]系统地阐述了DCS理论及其应用，提出了相应压缩感知方法及恢复算法,并采用稀疏随机投影矩阵作为观测矩阵,详细分析了分布式压缩感知理论观测过程,而文献[23]则从重构误差估计角度对分布式压缩感知理论进行了研究.DCS理论为分布式信号处理提供了新方法,目前热点和难点主要集中在如何将其应用到各种复杂实际传感器网络中.在某种意义上,DCS是一种分布式信源压缩框架,它在很长时间内都将是一个具有挑战性公开难题.六总结及展望压缩感知理论利用了信号稀疏特性,将原来基于奈奎斯特采样定理信号采样过程转化为基于优化计算恢复信号观测过程.也就是利用长时间积分换取采样频率降低,省去了高速采样过程中获得大批冗余数据然后再舍去大部分无用数据中间过程,从而有效缓解了高速采样实现压力,减少了处理、存储和传输成本,使得用低成本传感器将模拟信息转化为数字信息成为可能.这种新采样理论将可能成为将采样和压缩过程合二为一方法理论基础.本文对压缩感知理论框架全过程进行了描述,详细阐述了压缩感知理论所涉及关键技术,综述了国内外研究成果、存在公开问题及最新相关理论扩展,如冗余字典下压缩感知理论、模拟2信息理论、分布式压缩感知理论等.并对其中问题进行了概括性讨论.压缩感知理论研究已经有了一些成果,但是仍然存在大量问题需要研究.概括为以下几个方面:(1)对于稳定重构算法是否存在一个最优确定性观测矩阵;(2)如何构造稳定、计算复杂度较低、对观测次数限制较少重构算法来精确地恢复可压缩信号;(3)如何找到一种有效且快速稀疏分解算法是冗余字典下压缩感知理论难点所在;(4)如何设计有效软硬件来应用压缩感知理论解决大量实际问题,这方面研究还远远不够;⑸对于p2范数优化问题求解研究还远远不够；(6)含噪信号或采样过程中引入噪声时信号重构问题也是难点所在,研究结果尚不理想.此外,压缩感知理论及信号处理其它领域融合也远不够,如信号检测、特征提取等.CS理论及机器学习等领域内在联系方面研究工作已经开始.压缩感知理论是新诞生,虽然还有许多问题待研究,但它是对传统信号处理一个极好补充和完善,是一种具有强大生命力理论,其研究成果可能对信号处理等领域产生重大影响参考文献[1]石光明.刘丹华.高大化.刘哲.林杰.王良君压缩感知理论及其研究进展-ACTAElectronicaSinica2009,37(5)[2]张锐基于压缩感知理论图像压缩初步研究-ComputerKnowledgeAndTechnology2010，6(4)[3]CandesE,RombergJ,TaoT.Robustuncertaintyprinciples:Exactsignalreconstructionfromhighlyincompletefrequencyinformation[J].IEEETrans.InformationTheory,2006,52(4):489-509．[4]ECandesandJRomberg,Quantitativerobustuncentaintyprinciplesandoptimallysparsedecompositions[J].FoundationsofComputMath,2006,6(2):227-218．[5]ECandes.TTaoNearoptimalsignalrecoveryfromrandomprojections:Universalencodingstrategies2006(12)[6]DLDonohoCompressedsensing2006(04)[7]BKashin.Thewidthsofcertainfinitedimensionalsetsandclassesofsmoothfunctions[J]．IzvAkadNaukSSSR.1977,41(2):334-351．[8]ECandesCompressivesampling2006[9]喻玲娟.谢晓春压缩感知理论简介-VideoEngineering2008,32(12)[10]DONOHOD.TSAIGYExtensionsofcompressedsensing2006(03)[11]GuangmingShi.JieLin.XuyangChen.FeiQi,DanhuaLiuLiZhangUWBechosignaldetectionwithultralowratesamplingbasedoncompressedsensing2008(04)[12]张春梅.尹忠科.肖明霞基于冗余字典信号超完备表示及稀疏分解-科学通报2006(06)[13]VTemlyakovNonlinearMethodsofApproximation[IMIResearchReports]2001[14]FIGUEIREDOMAT.NOWAKRD.WRIGHTSJGradientprojectionforsparsereconstruction:applicationtocompressedsensingandotherinvemeproblems2007(04)[15]SMallat.杨力华.戴道清.黄文良信号处理小波导引2002[16]覃凤清.数字图像压缩综述J].宜宾学院学报,2006(6)[17]刘丹华.石光明.周佳社一种冗余字典下信号稀疏分解新方法-西安电子科技大学学报(自然科学版)2008(02)DBaron,MBWakin,MDuarte,etc.Distributedcompressedsensing[OL].DCS112005.19]RChartrand.ExactReconstructionofSparseSignalsviaNon2convexMinimization[J].IEEESignalProcessingLetters.2007,14(10):7072710.20]EJCandes,JRomberg.Sparsityandincoherenceincompres2sivesampling[J].InverseProblems.2007,23(3):9692985.TTDo,TD.Tran,LGan.Fastcompressivesamplingwithstructurallyrandommatrces[OL].SJi,YXue,LCarin.Bayesiancompressivesensing[J].IEEETransactionsSignalProcessing,2008,56(6):234622356.WWang,MGarofalakis,KRamchandran.Distributedsparserandomprojectionsforrefinableapproxim2ation[A].Proceed2ingsoftheSixthInternationalSymposiumonInformationPro2cessinginSensorNetworks,(IPSN2007)[C].NewYork:As2sociationforComputingMachinery,2007.3312339.论文题目 压缩感知技术研究进展 中文摘要信号采样是联系模拟信源和数字信息桥梁.人们对信息巨量需求造成了信号采样、传输和存储巨大压力.如何缓解这种压力又能有效提取承载在信号中有用信息是信号及信息处理中急需解决问题之一.近年国际上出现压缩感知理论(CompressedSensing,CS)为缓解这些压力提供了解