压缩感知课件

1XIDIANUniversity压缩感知理论与应用智能信息处理研究所智能感知与图像理解教育部重点实验室2011年8月IntelligentPerceptionandImageUnderstandingKeyLabofMinistryofChina2上次课内容回顾Lecture1：压缩感知概述•为什么研究压缩感知•压缩感知的涵义•压缩感知的过程•压缩感知的关键问题3FromNyquisttoCS4CompressionOriginal2500KB100%Compressed950KB38%Compressed392KB15%Compressed148KB6%“Canwenotjustdirectlymeasurethepartthatwillnotendupbeingthrownaway?”Donoho5Sparserepresentationofanimageviaamultiscalewavelettransform.(a)Originalimage.(b)Waveletrepresentation.Largecoefficientsarerepresentedbylightpixels,whilesmallcoefficientsarerepresentedbydarkpixels.Observethatmostofthewaveletcoefficientsareclosetozero.Sparseinwavelet-domain6Sparseapproximationofanaturalimage.(a)Originalimage.(b)Approximationofimageobtainedbykeepingonlythelargest10%ofthewaveletcoefficients.Sparseinwavelet-domain7OurPoint-Of-ViewCompressedSensing(CS)mustbebasedonsparsityandcompressibility.Thesignalsmustbesparseintime-domainorinfrquency-domain.8CompressedSensing“Canwenotjustdirectlymeasurethepartthatwillnotendupbeingthrownaway?”Donoho“sensing…asawayofextractinginformationaboutanobjectfromasmallnumberofrandomlyselectedobservations”Candèset.al.NyquistrateSamplingAnalogAudioSignalCompression(e.g.MP3)High-rateLow-rateCompressedSensing9ConceptGoal:Identifythebucketwithfakecoins.Nyquist:WeighacoinfromeachbucketCompressionBucket#numbers1numberCompressedSensing:Bucket#1numberWeighalinearcombinationofcoinsfromallbuckets10MathematicalToolsyAxnon-zeroentriesatleastmeasurementsRecovery:brute-force,convexoptimization,greedyalgorithms,andmore…11CStheoryCompressedsensing(2003/4andon)–MainresultsMaximalcardinalityoflinearlyindependentcolumnsubsetsHardtocompute!isuniquelydeterminedbyDonohoandElad,2003Smallestnumberofcolumnsthatarelinearly-dependent.12isuniquelydeterminedbyisrandomwithhighprobabilityDonoho,2006andCandèset.al.,2006NP-hardConvexandtractableGreedyalgorithms:OMP,FOCUSS,etc.Donoho,2006andCandèset.al.,2006Tropp,Cotteret.al.Chenet.al.andmanyotherCompressedsensing(2003/4andon)–MainresultsCStheoryDonohoandElad,200313RIPcriterion(a)Themeasurementscanmaintaintheenergyoftheoriginaltime-domainsignal.(b)Ifissparse,themustbedensetomaintaintheenergy.14VectorspaceUnitspheresinforthenormswith,andforthequasinormwith15VectorspaceThenormsisusedtoreconstructthesignalBestapproximationofapointinbyaone-dimensionalsubspaceusingthenormsfor,andthequasinormwithLecture2:ModernSamplingMethodsandCS[]cn[]cn[]cn17Sampling:“AnalogGirlinaDigitalWorld…”JudyGorman99DigitalworldAnalogworldSignalprocessingDenoisingImageanalysis…ReconstructionD2ASamplingA2D[]cn[]cn[]cn[]cn[]cn(Interpolation)18Applications:SamplingRateConversionCommonaudiostandards:8KHz(VOIP,wirelessmicrophone,…)11.025KHz(MPEGaudio,…)16KHz(VOIP,…)22.05KHz(MPEGaudio,…)32KHz(miniDV,DVCAM,DAT,NICAM,…)44.1KHz(CD,MP3,…)48KHz(DVD,DAT,…)…19LensdistortioncorrectionImagescalingApplications:ImageTransformations20Applications:CTScans21Applications:SpatialSuperresolution22OurPoint-Of-ViewThefieldofsamplingwastraditionallyassociatedwithmethodsimplementedeitherinthefrequencydomain,orinthetimedomainSamplingcanbeviewedinabroadersenseofprojectionontoanysubspaceorunionofsubspacesCanwesampleasignalbelowNyquistsamplingrate.(Wemustknowsomethingaboutthesignals).23Shannon’ssamplingtheoremrevisited24Cauchy(1841):Whittaker(1915)-Shannon(1948):A.J.Jerri,“TheShannonsamplingtheorem-itsvariousextensionsandapplications:Atutorialreview”,Proc.IEEE,pp.1565-1595,Nov.1977.BandlimitedSamplingTheorems25LimitationsofShannon’sTheoremInputbandlimitedImpracticalreconstruction(sinc)IdealsamplingTowardsmorerobustDSPs:GeneralinputsNonidealsampling:generalpre-filters,nonlineardistortionsSimpleinterpolationkernels26Generalizedanti-aliasingfilterSamplingProcessSamplingfunctions27EmployestimationtechniquesSamplingProcessNoise28SignalPriorsx(t)bandlimitedx(t)piece-wiselinearDifferentpriorsleadtodifferentreconstructions29SparsityIfasequencehaselementsandonlyofthemarenonzeros.Thenthesequenceissparse.Ifasequenceisasparsevector,thenthe30SignalPriors：SparsityPriorsWavelettransformofimagesiscommonlysparseSTFTtransformofspeechsignalsiscommonlysparseFouriertransformofradiosignalsiscommonlysparse31FromdiscretetoanalogDiscreteCompressedSensingAnalogCompressiveSampling32AnalogCompressedSensingAsignalwithamultibandstructureinsomebasisnomorethanNbands,maxwidthB,bandlimitedto(MishaliandEldar2007)1.Eachbandhasanuncountablenumberofnon-zeroelements2.Bandlocationslieonaninfinitegrid3.BandlocationsareunknowninadvanceWhatisthedefinitionofanalogsparsity?(Eldar2008)Moregenerallyonlysequencesarenon-zero33SamplingandReconstructionSamplingReconstruction34Unionofsubspaces35Predefined(e.g.linearinterpolation)Ifthefilterisdifferentfrom,thenamultiratecorrectionsystemmustbegiven.(Inpractice,thefiltersareoftenundesirable).Problem36Sub-NyquistsamplingBothprocessandrecoveryarebasedonlowratecomputation.Therawdatacanbedirectlystored.37SomequestionsabouttheSub-NyquistsamplingHowtoobtainthedigitalsignalatasub-nyquistrate?Canwereconstructthesignalwithhighprobabilityapproximately?Sub-Nyquistsamplingan