Sparse Recovery With Orthogonal Matching Pursuit Under RIP

《Sparse Recovery With Orthogonal Matching Pursuit Under RIP》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、IEEETRANSACTIONSONINFORMATIONTHEORY,VOL.57,NO.9,SEPTEMBER20116215SparseRecoveryWithOrthogonalMatchingPursuitUnderRIPTongZhang,Member,IEEEAbstract—Thispaperpresentsanewanalysisfortheorthog-onalmatchingpursuit(OMP)algorithm.Itisshownthatifthere-strictedisometryproperty(RIP)issatisfiedatsparsityl

2、evel,thenOMPcanstablyrecovera-sparsesignalin2-normundermeasurementnoise.Forcompressedsensingapplications,thisre-sultimpliesthatinordertouniformlyrecovera-sparsesignalin,onlyrandomprojectionsareneeded.Thisanal-ysisimprovessomeearlierresultsonOMPdependingonstrongerconditio

3、nsthatcanonlybesatisfiedwithorrandomprojections.IndexTerms—Estimationtheory,featureselection,greedyalgo-Fig.1.Fullycorrectivegreedyboostingalgorithm(OMP).rithms,statisticallearning,sparserecovery.However,thisoptimizationproblemisgenerallyNP-hard.I.INTRODUCTIONThereforeoneseeksc

4、omputationallyefficientalgorithmsthatONSIDERasignal,andsupposethatweobservecanapproximatelysolve(3),withthegoalofrecoveringsparseCitslineartransformationplusmeasurementnoiseassignal.Thispaperconsidersthepopularorthogonalmatchingpursuitalgorithm(OMP),whichhasbeenwidelyusedforthispurpose(forexam

5、ple,see[5],[14],[15]).Wearespecificallyinterestedintwoissues:theperformanceofOMPintermsHere,isanmatrix.IfwedefineanobjectivefunctionofoptimizingandtheperformanceofOMPintermsofrecoveringthesparsesignal.(1)thenwemayestimatetheparameterbyminimizing,II.MAINRESULTsubjecttoappropriateconstraints.Oura

6、nalysisconsidersamoregeneralobjectivefunctionIf,thenthesolutionoftheunconstrainedoptimizationthatdoesnotnecessarilytakethequadraticformin(1).problemHowever,weassumethatisconvex.Forsuchageneralconvexobjectivefunction,weconsiderthefully(ortotally)(2)correctivegreedyalgorithminFig.1,whichwasanal

7、yzedin[13].Thispaperrefinestheanalysistoshowthatthealgorithmisnotunique.Inordertoestimate,additionalassumptionsonworksundertherestrictedisometryproperty(RIP)of[3](theisnecessary.Wearespecificallyinterestedinthecasewhererequiredconditionwillbede