压缩感知理论及OMP算法(1)

2011-01-25TheCompressiveSensingTheoryAndPracticeofOMPAlgorithmAnOverviewofCompressiveSensing•For1-DsignalX∈RN×1,mostly，theinformationisredundant.。•Wecancompressitbyorthogonaltransformation.coding：makeorthogonalmatrixΨ,transformationy=Ψx,remainthemostimportantKcomponentsofyandthecorrespondingpositions.decoding：putKcomponentsbacktothecorrespondingpositions,letotherpositionsbezero,makeΨH，inversetransformationx*=ΨHy*.CodingSamplingTransformationSignalxyDecodingReceiveddatayInversetransformationReconstructedsignalx*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.CodingSparsesignalxMeasurement,codingyDecodingReceivedsignalyDecoding,reconstructionConstructedsignalx*AnOverviewofCompressiveSensing•Theadvantagesofcompressivesensing:•1)Non-adaptive,breakthroughthelimitationofShannonsamplingtheorem.•2)StrongAnti-interferenceability,everycomponentofthemeasurementisimportant,orunimportant.Itcanstillbereconstructedwhilesomecomponentsarelost.•Theapplicationprospectofcompressivesensingisbroad:•digitalcameraandaudioacquisitiondevicewithlowcost;astronomy(starsaresparse);network;military.AnOverviewofCompressiveSensing•Supposex(n)isadigitalsignal,ifit’saK-sparse(hasKnon-zerovalues)orcompressiblesignal,thenwecanestimateitwithfewcoefficientsbylineartransformation.Bycompressivesensingwegetthesignaly(m)(mn),•y=Φx•Φiscalledsensingmatrixwithm×ndimension.•Thedimensionofyismuchlessthanthatofx,sotheequationhasinfinitivesolutions,whichmakesitdifficulttorebuildoriginalsignal.SincexisK-sparse,wecanrebuildxfromybysolvingtheoptimalproblembelow:•x*=min||x||0s.t.y=Φx•CandesindicatesthatwhenmKlog(n)andΦhasrestrictedisometryproperty(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:forδK∈(0,1)(1-δK)||x||22≤||Φx||22≤(1+δK)||x||22AnOverviewofCompressiveSensing•Butfewofnaturalsignalissparse.•Accordingtocompressivesensingtheory,signalxcanbesparsebysomereversibletransformationΨ,thatisx=Ψs,sowehave•y=Φx=ΦΨs•BaraniukindicatesthattheequivalentconditionofRIPisthatthemeasurementmatrixΦandthesparsebaseΨisirrelevant.It’sconfirmedthatwhenΦisGuassrandommatrix,theconditioniswellfitted.OMPAlgorithm•Insomecircumstance,wecanreplacel0normwithl1norm,thatis•x*=min||x||1s.t.y=Φx•Theproblemabovecanbesolvedbygreediterativealgorithm,oneofthemostcommonlyusedalgorithmistheorthogonalmatchingpursuit(OMP)method.•ThemainideaoftheOMPalgorithm:choosethecolumnofΦbygreediterativemethod,whichmakesthechosencolumnandthepresentredundantvectorrelatedtothegreatestextent,wesubtracttherelatedpartfrommeasurementvector,repeattheprocedureaboveuntilthenumberofiterationsuptoK.OMPAlgorithm•Input:sensingmatrixΦ,samplingvectory,sparsedegreeK;•Output:theK-sparseapproximationx*ofx;•Initialization:theresidualr0=y,indexsetΛ0=∅,t=1;OMPAlgorithm•Executesteps1to5circularly:•Step1:findthemaximumvalueoftheinnerproductofresidualrandthecolumnofsensingmatrixφj,thecorrespondingfootmarkisλ;•Step2:renewtheindexsetΛt=Λt-1∪{λ},thesensingmatrixΦt=[Φt-1,φλ];•Step3:solvex*t=min||y-Φtx*||2byleast-squaremethod;•Step4:renewtheresidualrt=y-Φtx*t,t=t+1;•Step5:iftK,stoptheiteration,elsedostep1.SimulationResultsofOMP•WriteprogramsofOMPinmatlab•For1-Dsignalx=0.3sin(2π×50t)+0.6sin(2π×100t)SimulationResultsofOMP•Forimageswhichare2-Dsignals,wefirstexecutediscreetwavelettransformation,changingimagesignalintothesparsecoefficientsofcorrespondingbasis(hereweuseHaarbasis),foreachcolumnofthecoefficientsmatrix,weexecuteOMPmethod.ThenweexecutewavletinversetransformationontheOMPresults,andthereconstructedimagehasbeengained.OriginalimageSparsecoefficientsReconstructedcoefficientsReconstructedimageDWTOMPInverseDWTSimulationResultsofOMP•Therearetwoimagesadoptedinthesimulation,oneisaremotesensingimage,andtheotherislena.Thesizeofimagesisboth512×512pixels.SimulationResultsofOMP•Fortheremotesensingimage,hereareimagesreconstructedatdifferentsamplingrate.SimulationResultsofOMP•ThePSNRofeachimageatdifferentsamplingrateSimulationResultsofOMP•ForthelenaimageSimulationResultsofOMP•ThePSNRofeachimageatdifferentsamplingrateSimul