On the Recovery Limit of Sparse Signals Using Orthogonal Matching Pursuit

《On the Recovery Limit of Sparse Signals Using Orthogonal Matching Pursuit》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、OntheRecoveryLimitofSparseSignalsusingOrthogonalMatchingPursuitJianWangandByonghyoShimInformationSystemLaboratorySchoolofInformationandCommunicationKoreaUniversity,Seoul,Korea136-713Email:jwang@isl.korea.ac.kr,bshim@korea.ac.krPhone:82-2-3290-4842AbstractOrthogonalmatchingpurs

2、uit(OMP)isagreedysearchalgorithmpopularlybeingusedfortherecoveryofcompressivesensedsignal.Inthispaper,weshowthatiftheisometryconstantK+1ofthesensingmatrixsatisfies

3、tantialimprovementovertherecentresultofDavenportandWakin,andalsoclosesgapbetweentherecoveryboundandfundamentallimitoverwhichtheperfectrecoveryoftheOMPcannotbeguaranteed.IndexTermsCompressedsensing(CS),sparsesignal,orthogonalmatchingpursuit(OMP),restrictedisometryproperty(RIP).

4、ThisworkwassupportedbyMid-careerResearcherProgramthroughNRFgrantfundedbytheMEST(No.2009-0083945)andsecondBrainKorea21project.February27,2012DRAFT1OntheRecoveryLimitofSparseSignalsusingOrthogonalMatchingPursuitI.INTRODUCTIONA.OrthogonalMatchingPursuitAsasamplingparadigmguarante

5、eingthereconstructionofsparsesignalwithsamplingratesignificantlylowerthantheNyquistrate,compressivesensing(CS)hasreceivedconsiderableattentioninrecentyears[1][9].Foragivenmatrix∈Rm×n(n>m),CSrecoveryalgorithmgeneratesanestimateofK-sparsevectorx∈Rnfromasetoflinearmeasurementsy=

6、x.(1)Althoughthesystemisunder-determinedandhencetheinverseproblemisingeneralill-posed,duetothepriorinformationofsignalsparsity,xcanbeperfectlyreconstructedviaproperlydesignedrecoveryalgorithm.Amongmanyrecoveryalgorithmsintheliterature,greedysearchmethodssequentiallyinvestigati

7、ngthesupportofthesparsesignalhasgeneratedagreatdealofinterestforpracticalbenefit.Ineachiterationofgreedysearchalgorithms,correlationsbetweeneachcolumnofandthemodifiedmeasurements(socalledresidual)arecomparedtoidentifytheelementofthesupport.Algorithmscontainedinthiscategoryinclu

8、deorthogonalmatchingpursuit(OMP)[1],regularizedorthogonalmatc