Shannon Theory for Compressed Sensing

《Shannon Theory for Compressed Sensing》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ShannonTheoryforCompressedSensingYihongWuADissertationPresentedtotheFacultyofPrincetonUniversityinCandidacyfortheDegreeofDoctorofPhilosophyRecommendedforAcceptancebytheDepartmentofElectricalEngineeringAdviser:ProfessorSergioVerduSeptember2011cCopyrightbyYihongWu,2011.All

2、rightsreserved.AbstractCompressedsensingisasignalprocessingtechniquetoencodeanalogsourcesbyrealnumbersratherthanbits,dealingwithecientrecoveryofarealvectorfromtheinformationprovidedbylinearmeasurements.Byleveragingthepriorknowledgeofthesignalstructure(e.g.,sparsity)andde

3、signingecientnon-linearreconstructionalgorithms,eectivecompressionisachievedbytakingamuchsmallernumberofmeasurementsthanthedimensionoftheoriginalsignal.However,partiallyduetothenon-discretenatureoftheproblem,noneoftheexistingmodelsallowacompleteunderstandingofthetheoret

4、icallimitsofthecompressedsensingparadigm.Asopposedtotheconventionalworst-case(Hamming)approach,thisthesispresentsastatistical(Shannon)studyofcompressedsensing,wheresignalsaremodeledasrandomprocessesratherthanindividualsequences.Thisframeworkencompassesmoregeneralsignalmod

5、elsthansparsity.Focusingonoptimaldecoders,weinvestigatethefundamentaltradeobetweenmeasurementrateandreconstruc-tiondelitygaugedbyerrorprobabilityandnoisesensitivityintheabsenceandpresenceofmeasurementnoise,respectively.Optimalphasetransitionthresholdsaredeterminedasafun

6、ctionaloftheinputdistributionandcomparedtosuboptimalthresholdsachievedbyvariouspopularreconstructionalgorithms.Inparticular,weshowthatGaussiansensingmatricesincurnopenaltyonthephasetransitionthresholdofnoisesensitivitywithrespecttooptimalnonlinearencoding.Ourresultsalsopr

7、ovidearigorousjusticationofpreviousresultsbasedonreplicaheuristicsintheweak-noiseregime.iiiAcknowledgementsIamdeeplyindebtedtomyadvisorProf.SergioVerduforhisconstantguidanceandsupportateverystageofmyPh.D.studies,withoutwhichthisdissertationwouldbeimpossible.Asuperbresea

8、rcherandmentor,hetaughtmehowtoformulateaprobleminthecleanestpossibleway.Hisbrilliantinsights,mat