压缩感知理论及OMP算法.ppt

2011-01-25,TheCompressiveSensingTheoryAndPracticeofOMPAlgorithm,AnOverviewofCompressiveSensing,For1-DsignalXRN1,mostly，theinformationisredundant.。Wecancompressitbyorthogonaltransformation.,coding：makeorthogonalmatrix,transformationy=x,remainthemostimportantKcomponentsofyandthecorrespondingpositions.decoding：putKcomponentsbacktothecorrespondingpositions,letotherpositionsbezero,makeH，inversetransformationx*=Hy*.,Coding,Sampling,Transformation,Signalx,y,Decoding,Receiveddatay,Inversetransformation,Reconstructedsignalx*,AnOverviewofCompressiveSensing,Buttherearesomeflawsofthismethod:1)ConsideringtheShannonsamplingtheorem，thesamplingintervalwillbeverynarrowtogainbettersignalresolution，whichwillmaketheoriginalsignalverylong,sotheprocessingoftransformationcostslotsoftime.2)ThepositionsofKcomponentsrequiredtoremainvarywhilethesignalchanges.Therefore,thisstrategyisself-adaptive,andweneedtoallocatemorespacetostorethesepositions.3)Pooranti-interference.OnceoneoftheKcomponentslostintransmission,theoutputwillbechangedgreatly.,AnOverviewofCompressiveSensing,In2004,DonohoandCandesputforwardthetheoryofcompressivesensing.Thistheoryindicatesthatwhenthesignalissparseorcompressible,thesignalcanbereconstructedaccuratelyorapproximatelybygatheringveryfewprojectivevaluesofthesignal.,Themeasuredvalueisnotthesignalitself,buttheprojectivevaluefromhigherdimensiontolowerdimension.,Coding,Sparsesignalx,Measurement,coding,y,Decoding,Receivedsignaly,Decoding,reconstruction,Constructedsignalx*,AnOverviewofCompressiveSensing,Theadvantagesofcompressivesensing:1)Non-adaptive,breakthroughthelimitationofShannonsamplingtheorem.2)StrongAnti-interferenceability,everycomponentofthemeasurementisimportant,orunimportant.Itcanstillbereconstructedwhilesomecomponentsarelost.Theapplicationprospectofcompressivesensingisbroad:digitalcameraandaudioacquisitiondevicewithlowcost;astronomy(starsaresparse);network;military.,AnOverviewofCompressiveSensing,Supposex(n)isadigitalsignal,ifitsaK-sparse(hasKnon-zerovalues)orcompressiblesignal,thenwecanestimateitwithfewcoefficientsbylineartransformation.Bycompressivesensingwegetthesignaly(m)(mKlog(n)andhasrestrictedisometryproperty(RIP),x(n)canberebuilt.,AnOverviewofCompressiveSensing,Thedefinitionofnorm:Foravectorx,ifthereisacorrespondedrealfunction|x|,whichfitssuchconditions:1)|x|0,onlyifx=0,|x|=0;2)foranynumbera,|ax|=|a|x|;3)foranyvectorxandy,|x+y|x|+|y|;Thenwecall|x|thenormofx.RIP:forK(0,1)(1-K)|x|22|x|22(1+K)|x|22,AnOverviewofCompressiveSensing,Butfewofnaturalsignalissparse.Accordingtocompressivesensingtheory,signalxcanbesparsebysomereversibletransformation,thatisx=s,sowehavey=x=sBaraniukindicatesthattheequivalentconditionofRIPisthatthemeasurementmatrixandthesparsebaseisirrelevant.ItsconfirmedthatwhenisGuassrandommatrix,theconditioniswellfitted.,OMPAlgorithm,Insomecircumstance,wecanreplacel0normwithl1norm,thatisx*=min|x|1s.t.y=xTheproblemabovecanbesolvedbygreediterativealgorithm,oneofthemostcommonlyusedalgorithmistheorthogonalmatchingpursuit(OMP)method.ThemainideaoftheOMPalgorithm:choosethecolumnofbygreediterativemethod,whichmakesthechosencolumnandthepresentredundantvectorrelatedtothegreatestextent,wesubtracttherelatedpartfrommeasurementvector,repeattheprocedureaboveuntilthenumberofiterationsuptoK.,OMPAlgorithm,Input:sensingmatrix,samplingvectory,sparsedegreeK;Output:theK-sparseapproximationx*ofx;Initialization:theresidualr0=y,indexset0=,t=1;,OMPAlgorithm,Executesteps1to5circularly:Step1:findthemaximumvalueoftheinnerproductofresidualrandthecolumnofsensingmatrixj,thecorrespondingfootmarkis;Step2:renewtheindexsett=t-1,thesensingmatrixt=t-1,;Step3:solvex*t=min|y-tx*|2byleast-squaremethod;Step4:renewtheresidualrt=y-tx*t,t=t+1;Step5:iftK,stoptheiteration,elsedostep1.,SimulationResultsofOMP,WriteprogramsofOMPinmatlabFor1-Dsignal,x=0.3sin(250t)+0.6sin(2100t),SimulationResultsofOMP,Forimageswhichare2-Dsignals,wefirstexecutediscreetwavelettransformation,changingimagesignalintothesparsecoefficientsofcorrespondingbasis(hereweuseHaarbasis),foreachcolumnofthecoefficientsmatrix,weexecuteOMPmethod.ThenweexecutewavletinversetransformationontheOMPresults,andthereconstructedimagehasbeengained.,SimulationResultsofOMP,Therearetwoimagesadoptedinthesimulation,oneisaremotesensingimage,andtheotherislena.Thesizeofimagesisboth512512pixels.,SimulationResultsofOMP,Fortheremotesensingimage,hereareimagesreconstructedatdifferentsamplingrate.,SimulationResultsofOMP,ThePSNRofeachimageatdifferentsamplingrate,SimulationResultsofOMP,Forthelenaimage,SimulationResultsofOMP,ThePSNRofeach