贪婪算法与压缩感知理论

3712Vol.37,No.12201112ACTAAUTOMATICASINICADecember,201112(Compressedsensing,CS).;,,MP,OMP,IBOOMP,StOMP,SP,ROMPCoSaMP,,,,;,,,.,,,,DOI10.3724/SP.J.1004.2011.01413GreedyAlgorithmsandCompressedSensingFANGHong1YANGHai-Rong2AbstractRecentlyafamilyofiterativegreedyalgorithmshavereceivedextensiveapplicationincompressedsensing(CS)duetotheirfastreconstructionandlowreconstructioncomplexity.Inthispaper,thebasictheoryofCSis¯rstintroducedandthenweputemphasisonthemaingreedyalgorithmsforreconstruction,whichincludeMP,OMP,IBOOMP,StOMP,SP,ROMP,CoSaMPandsoonandprovidetheirmathematicalframeworks,respectively.Next,weclassifyallthealgorithmsaccordingtothestrategyofelementselectionandtheupdateoftheresidualerror.Undertheconditionofrestrictedisometryconstant,furtherdiscussionontheperformanceofreconstructionalgorithmssuchasrunningtime,reconstructionstabilityandsoonispresented.Last,thereconstructionresultsfromsimulatedexperimentsfurthershowtheperformanceofallalgorithms.Andfromthoseresultswealsoacquiretherelationshipamongtheperformanceofthealgorithms,thesparsityofsignalstobereconstructedandthenumberofmeasurements,whichlaysagoodbasisforproposingnewandbetteralgorithms.KeywordsGreedyalgorithms,compressedsensing(CS),restrictedisometryconstant,residualerror,sparsityShannon/Nyquist,,(Com-pressivesensing,CS)Shannon/Nyquist.CSDonoho[1]Candes[2].,Donoho,2010-09-062011-07-14ManuscriptreceivedSeptember6,2010;acceptedJuly14,2011(EGD08006),(XQD208008),(KJ2011B131)SupportedbyResearchFundfortheExcellentYouthSchol-arsofMinistryofEducationofShanghai(EGD08006),Founda-tionofShanghaiSecondPolytechnicUniversity(XQD208008),andAnhuiProvincialNaturalScienceFoundationProject(KJ2011B131)1.2012092.2306011.SchoolofScience,ShanghaiSecondPolytechnicUniversity,Shanghai2012092.DepartmentofMathematics,HefeiNor-malUniversity,Hefei230601[3¡4].CS(),.Shannon/Nyquist,.,((MassachusettsIn-stituteofTechnology)(StanfordUni-versity)(PrincetonUniversity)(RiceUniversity)(DukeUni-versity)(TechnicalUniversityofMunich)(EdinburghUniversity))CS;2008IntelGoogleCS,CS[5¡7].CS,,(FourierWavelet),141437.,,.,.,\,,.,CS,CS.1CSCS4:.`1,(Ba-sispursuit,BP)[8],(Gradientprojectionforsparsereconstruction,GPSR)[9],(Iterativethresholding,IT)[10],(Iterativehardthresholding,IHT)[11]Bregman(Bregmaniterative,BI)[12¡15].4,,,,,;,,[16],(Chainingpursuit,CP)[17],HHSP(Heavyhittersonsteroidspursuit,HHSP)[18¡19],,,,,,.:[20¡22];[23],,.,,,.CS,,,,,CS.,(Matchingpursuit,MP)[24](Or-thogonalmatchingpursuit,OMP)[25](Stagewiseorthogonalmatchingpursuit,StOMP)[26](Regularizedorthogonalmatchingpursuit,ROMP)[27](Compressivesamplingmatchingpur-suit,CoSaMP)[28](Subspacepursuit,SP)[29]OOMP(Improvedback-wardoptimizedOMP,IBOOMP)[30].4,OMP,.;,,,,;,.2CSCS.:()ª=[ÃÃÃ1;ÃÃÃ2;¢¢¢;ÃÃÃN]m-Nxxx2RN,xxx=NXn=1µ(n)ÃÃÃn=mXl=1µ(nl)ÃÃÃ(nl)()©=(ÁÁÁT1;ÁÁÁT2;¢¢¢;ÁÁÁTM)M(m·MN)yyy(i)=hxxx;ÁÁÁTii,i2f1;2;¢¢¢;Mg.,yyy=©xxx=©ª®®®.,®®®m-,Myyy,©M£N.M(MN)yyyxxx.m·MNCS.MN,xxx,xxx,,,.Candes[31]:,©(Restrictedisometryproperty,RIP).12:1415RIP.1(RIP).©2RM£N,jIj·mMI½f1;2;¢¢¢;Ngvvv2RjIj,0±1,:(1¡±)kvvvkl2·k©Ivvvkl2·(1+±)kvvvkl2(1),(m;±)RIP,:©II½f1;2;¢¢¢;Ng©,(1)±(Restrictedisometryconstant,RIC),±m.1(RIC).©2RM£N(m;±)RIP,jIj·mI½f1;2;¢¢¢;Ng,:1¡±m·¸min(©TI©I)·¸max(©TI©I)·1+±m(2)¸min¸max.1)1:(1),±=0,kvvvkl2·k©Ivvvkl2·kvvvkl2,k©Ivvvkl2=kvvvkl2,,©I,,;0±1,,l2,;,,±mm.2)2:(2)RIC,CmN,,RICNP.RIPRIC,[32]©RIC±m+±2m+±3m1,l1m-;[33]±3m+3±4m2;[34]RIC±2kp2¡1;[35]±2k0:4531;[36]±2k0:472.,[37]±k0:307,±k.RIP,[38].,,,,,.33.1CS,©Myyy=©xxx.xxxm,,yyy©m.,yyy©xxx©m().:yyy©(MN)m-,xxx.,CS,,,,,.3.2,.MPOMP,xxx,©Tyyy,,12.1.MP1)rrr0=yyy,t=1;2)¸t,:¸t=argmaxj=1;2;¢¢¢;Njhrrrt¡1;©jij;3)aaatrrrt:aaat=hrrrt¡1;©¸ti©¸t,rrrt=rrrt¡aaat4)t=t+1,tK,2).MPOMP,©rrrt¡1.,MPrrrt©¸t(hrrrt;©¸ti=hrrrt¡1¡aaat;©¸ti=0),rrrt©¸t,rrrtf©¸1;©¸2;¢¢¢;©¸tg,MPK,MP.OMP(24)141637)Pt,rrrt=yyy¡Ptyyy,MP.2.OMP1)rrr0=yyy,¤0=Á,t=1;2)¸t,:¸t=argmaxj=1;2;¢¢¢;Njhrrrt¡1;©jij;3)¤t=¤t¡1[f¸tg;4)f©¸:¸2¤tgPt;5)aaarrr:aaat=Ptyyy,rrrt=yyy¡aaat;6)t=t+1,tm,2);7)bs¸¤m,:aaam=P¸2¤mbs¸©¸.OMPMP,,,\.\,,,.,,\\,.OMP\,IBOOMP[30],3.3.IBOOMP1)rrr0=yyy,°°°j=©j,j=1;2;¢¢¢;N,¸1=argmax1·j·Njh©j;yyyij,¤1=f¸1g,ÃÃÃ1=©¸1=¯¯¯1c1=h©¸1;yyyi,t=1;2)j=1;2;¢¢¢;N,:°°°j=°°°j¡ÃÃÃjhÃÃÃt;©ti,bj=h°°°j;yyyi,dj=dj¡jhÃÃÃt;©jij2,ej=jbjj2=dj;3)t=t+1,¸t,¸t=argmax1·j·Nej,¤t=¤t¡1[f¸tg.:kRRRtk2=kRRRt¡1k2¡e¸t,ÃÃÃt=°°°¸tpd¸t,¯¯¯t=°°°¸td¸t;4)j=1;2;¢¢¢;t¡1:¯¯¯j+1=¯¯¯j¡¯¯¯th©¸t;¯¯¯ji,cj+1=cj¡h©¸t;¯¯¯jict;5)2)»4)±,kRRRtk2·±,,ccc,jcccj=Mm;6)cccM¡m.:IBOOMP,MPOMP,,,.ROMPSP,45.4.ROMP1)rrr0=yyy,I=;,t=1,mjIj¸2m;2)u=hrrrt¡1;©ji;3):m,J;4):J0½J:ju(i)j·2ju(j)j,i;j2J0,kujJ0kl2J0;5):J0:IÃI[J0,:xxx=argminzzz2RIkyyy¡©zzzkl2,rrr=yyy¡©xxx5.SP1):bT=f©Tyyymgyyyr=resid(yyy;©bT);2):yyyr=0,;;3)T0=bT[f©Tyyyrmgxxx0p=©yT0yyy,eT=fxxx0pmg,eyyyr=resid(yyy;©eT);4):keyyyrkl2kyyyrkl2,;,bT=eTyyyr=eyyyr,;:bxxxf1;2;¢¢¢;Ng¡bT=0xxxbT=©ybTyyybxxx.ROMPSP,©Tyyyr(yyyr)m;,ROMPJ0,J0kyyy¡©zzzkl2xxx,yyy¡©xxx,\,\,.SPROMP,,(T0)xxxbT=©ybTyyy,SP\,ROMP.,SP,(),,(),.,[39]SP|(StepwiseoptimalSP,SOSP).SOSP12:1417,GreedyAddGreedyRemove,,.,SOSPSPeT.StOMPCoSaMP,67.6.StOMP1)xxx=0,rrr0=yyy,s=1;2)s,Cs=©Trrrs¡1=h©;rrrs¡1i;3)h=ts¾s,Js=fj:jCs(