壓縮感知課件

壓縮感知理論與應(yīng)用智能感知與圖像理解教育部重點實驗室2011年8月IntelligentPerceptionandImageUnderstandingKeyLabofMinistryofChinaIntelligentPerceptionandImageUnderstandingKeyLabofMinistryofChina壓縮感知理論與應(yīng)用IntelligentPerceptio上次課內(nèi)容回顧Lecture1：壓縮感知概述為什么研究壓縮感知壓縮感知的涵義壓縮感知的過程壓縮感知的關(guān)鍵問題上次課內(nèi)容回顧Lecture1：壓縮感知概述FromNyquisttoCSFromNyquisttoCSCompressionOriginal2500KB

100%Compressed950KB

38%Compressed392KB

15%Compressed148KB

6%“Canwenotjustdirectlymeasurethepartthatwillnotendupbeingthrownaway?”DonohoCompressionOriginal2500KSparserepresentationofanimageviaamultiscalewavelettransform.(a)Originalimage.(b)Waveletrepresentation.Largecoefficientsarerepresentedbylightpixels,whilesmallcoefficientsarerepresentedbydarkpixels.Observethatmostofthewaveletcoefficientsareclosetozero.Sparse

inwavelet-domainSparserepresentationofanimSparseapproximationofanaturalimage.(a)Originalimage.(b)Approximationofimageobtainedbykeepingonlythelargest10%ofthewaveletcoefficients.Sparse

inwavelet-domainSparseapproximationofanatuOurPoint-Of-ViewCompressedSensing(CS)mustbebasedonsparsityandcompressibility.Thesignalsmustbesparseintime-domainorinfrquency-domain.

OurPoint-Of-ViewCompressedSeCompressedSensing“Canwenotjustdirectlymeasurethepartthatwillnotendupbeingthrownaway?”Donoho“sensing…asawayofextractinginformationaboutanobjectfromasmallnumberofrandomlyselectedobservations”Candèset.al.Nyquistrate

SamplingAnalog

Audio

SignalCompression

(e.g.MP3)High-rateLow-rateCompressed

SensingCompressedSensing“CanwenotConceptGoal:Identifythebucketwithfakecoins.Nyquist:Weighacoin

fromeachbucketCompressionBucket#numbers1numberCompressedSensing:Bucket#1numberWeighalinearcombination

ofcoinsfromallbucketsConceptGoal:IdentifythebuckMathematicalToolsnon-zeroentries

atleastmeasurementsRecovery:brute-force,convexoptimization,

greedyalgorithms,andmore…MathematicalToolsnon-zeroentCStheoryCompressedsensing(2003/4andon)–MainresultsMaximalcardinalityoflinearlyindependentcolumnsubsetsHardtocompute!isuniquelydeterminedbyDonohoandElad,2003Smallestnumberofcolumnsthatarelinearly-dependent.CStheoryCompressedsensing(isuniquelydeterminedbyisrandomwithhighprobabilityDonoho,2006andCandèset.al.,2006NP-hardConvexandtractableGreedyalgorithms:OMP,FOCUSS,etc.Donoho,2006andCandèset.al.,2006Tropp,Cotteret.al.Chenet.al.andmanyotherCompressedsensing(2003/4andon)–MainresultsCStheoryDonohoandElad,2003isuniquelydeterminedbyisrRIPcriterion(a)Themeasurementscanmaintaintheenergyoftheoriginaltime-domainsignal.(b)Ifissparse,themustbedensetomaintaintheenergy.

RIPcriterion(a)ThemeasuremenVectorspaceUnitspheresinforthenormswith,andforthequasinormwithVectorspaceUnitspheresinVectorspaceThenormsisusedtoreconstructthesignalBestapproximationofapointinbyaone-dimensionalsubspaceusingthenormsfor,andthequasinormwith

VectorspaceThenormsiLecture2:ModernSamplingMethodsandCS

16Lecture2:ModernSamplingMeSampling:“AnalogGirlinaDigitalWorld…”JudyGorman99DigitalworldAnalogworldSignalprocessingDenoisingImageanalysis…ReconstructionD2ASamplingA2D(Interpolation)Sampling:“AnalogGirlinaDiApplications: SamplingRateConversionCommonaudiostandards:

8KHz(VOIP,wirelessmicrophone,…)

11.025KHz(MPEGaudio,…)

16KHz(VOIP,…)

22.05KHz(MPEGaudio,…)

32KHz(miniDV,DVCAM,DAT,NICAM,…)

44.1KHz(CD,MP3,…)

48KHz(DVD,DAT,…)

…Applications: SamplingRateCoLensdistortioncorrectionImagescalingApplications: ImageTransformationsLensdistortioncorrectionApplApplications:CTScansApplications:CTScansApplications: SpatialSuperresolutionApplications: SpatialSuperresOurPoint-Of-ViewThefieldofsamplingwastraditionallyassociatedwithmethodsimplementedeitherinthefrequencydomain,orinthetimedomainSamplingcanbeviewedinabroadersenseofprojectionontoanysubspaceorunionofsubspacesCanwesampleasignalbelowNyquistsamplingrate.(Wemustknowsomethingaboutthesignals).

OurPoint-Of-ViewThefieldofShannon’ssamplingtheoremrevisited

Shannon’ssamplingtheoremrevCauchy(1841):Whittaker(1915)-Shannon(1948):A.J.Jerri,“TheShannonsamplingtheorem-itsvariousextensionsandapplications:Atutorialreview”,Proc.IEEE,pp.1565-1595,Nov.1977.BandlimitedSamplingTheorems

Cauchy(1841):BandlimitedSampLimitationsofShannon’sTheorem

InputbandlimitedImpracticalreconstruction(sinc)IdealsamplingTowardsmorerobustDSPs:GeneralinputsNonidealsampling:generalpre-filters,nonlineardistortionsSimpleinterpolationkernelsLimitationsofShannon’sTheorGeneralizedanti-aliasingfilterSamplingProcess

SamplingfunctionsGeneralizedanti-aliasingfiltEmployestimationtechniquesSamplingProcessNoiseEmployestimationtechniquesSignalPriors

x(t)bandlimitedx(t)piece-wiselinearDifferentpriorsleadtodifferentreconstructionsSignalPriorsx(t)bandlimitedxSparsityIfasequencehaselementsandonlyofthemarenonzeros.Thenthesequenceissparse.Ifasequenceisasparsevector,thentheSparsityIfasequencehasSignalPriors：SparsityPriorsWavelettransformofimagesiscommonlysparseSTFTtransformofspeechsignalsiscommonlysparseFouriertransformofradiosignalsiscommonlysparseSignalPriors：SparsityPriorFromdiscretetoanalogDiscreteCompressedSensingAnalogCompressiveSamplingFromdiscretetoanalogAnalogCompressedSensingAsignalwithamultibandstructureinsomebasisnomorethanNbands,maxwidthB,bandlimitedto(MishaliandEldar2007)Eachbandhasanuncountablenumberofnon-zeroelementsBandlocationslieonaninfinitegridBandlocationsareunknowninadvanceWhatisthedefinitionofanalogsparsity?(Eldar2008)Moregenerallyonly

sequences

arenon-zeroAnalogCompressedSensingnomoSamplingandReconstructionSamplingReconstructionSamplingandReconstructionSamUnionofsubspacesUnionofsubspacesPredefined(e.g.linearinterpolation)Ifthefilterisdifferentfrom,thenamultiratecorrectionsystemmustbegiven.(Inpractice,thefiltersareoftenundesirable).ProblemPredefinedIfthefilterSub-NyquistsamplingBothprocessandrecoveryarebasedonlowratecomputation.Therawdatacanbedirectlystored.Sub-NyquistsamplingBothprocSomequestionsabouttheSub-NyquistsamplingHowtoobtainthedigitalsignalatasub-nyquistrate?Canwereconstructthesignalwithhighprobabilityapproximately?SomequestionsabouttheSub-NSub-NyquistsamplingandCompressedSensing

38Sub-NyquistsamplingandComprMulti-BandSensing:GoalsbandsSamplingReconstructionGoal:PerfectreconstructionConstraints:MinimalsamplingrateFullyblindsystemAnalogInfiniteAnalogWhatistheminimalrate?Whatisthesensingmechanism?Howtoreconstructfrominfinitesequences?Multi-BandSensing:GoalsbandsSub-NyquistsamplingLandauminimumratemeanssamplingatoftheNyquistratecanreconstructthesignalperfectly.（butthespectralsupportmustbeknown）Sub-NyquistsamplingLandauminNonuniformsamplingAnalogsignalIneachblockofsamples,onlyarekept,asdescribedbyPoint-wisesamples023002233Multi-Coset:PeriodicNon-uniformontheNyquistgridNonuniformsamplingAnalogsignNonuniformsamplingDenotebythesequenceofsamplestakenattheNyquistrate.Therefore，inwhich.NonuniformsamplingDenotebyNonuniformsamplingThebuildingblocksareuniformsamplersatrate,sothattheaveragesamplingrateis,whichislowerthantheNyquistratewhere.NonuniformsamplingThebuildinNonuniformsamplingReconstructionoftheoriginalsignalisachievedifwerecoveritsspectralcomponents.Buttherearefewerequationsthantheunknownforeach.HOWTORECONSTRUCTTHESIGNALNonuniformsamplingReconstructNonuniformsamplingAmethodshouldbeusedtoreducethedegreeoftheproblem.Some"subcell"areactive,whiletheothersarenot.Theanalogsignalcanbereconstructedperfectlyiftheamplitudeandlocationsofhasbeenknown.NonuniformsamplingAmethodshSomeproblem1PracticalADCsintroduceaninherentbandwidthlimitation,whichdistortsthesamples.AnyspectralcontentbeyondbHzisattenuatedanddistorted.2Anotherpracticalissueofmulticosetsampling,arisesfromthetimeshiftelements.MaintainingaccuratetimedelaysbetweentheADCsintheorderoftheNyquistintervalisdifficult.Someproblem1PracticalADCsIntroducetoRDTosolvetheparcticalproblemssomethingsabouttheRD(randomdemodulated)methordcanbeused.IntroducetoRDTosolvethepaa

Oursystemexploitsspread-spectrumtechniquesfromcommunicationtheory.Ananalogmixingfront-endaliasesthespectrum,suchthataspectrumportionfromeachbandappearsinbaseband.bSignalternatingfunctionscanbeimplementedbyastandard(highrate)shiftregister.Today’stechnologyallowstoreachalternationratesof23GHzandeven80GHz.cBlindmultibandsignal(arbitraryspectrallocations)canbereconstructedbythissystemwithhighprobablity.AdvantageaOursystemexploitsspread多頻帶信號---許多信號只占用了少量帶寬，因而具有稀疏性子空間采樣理論MWC模塊多頻帶信號---許多信號只占用了少量帶寬，因而具有稀疏性子空這里我們需要大量的濾波器，才能精確的重構(gòu)，也就是

值越大越好（對應(yīng)的采樣頻率也逐漸增大），由于信號的稀疏性，一般要求，

為頻帶個數(shù)這里我們需要大量的濾波器，才能精確的重構(gòu)，也就是值越大越實際采樣框圖實際采樣框圖壓縮感知課件傅里葉變換原子傅里葉變換原子如果是離散信號的重構(gòu)，我們可以直接通過優(yōu)化求解，模擬信號我們有無窮多個方程要解，必須轉(zhuǎn)化成有限的模型，高概率的重構(gòu)原始信號引入一個CTF模型，通過和支撐區(qū)間

，我們可以重構(gòu)出信號如果是離散信號的重構(gòu)，我們可以直接通過優(yōu)化求解，模擬信號我們AICviaRandomDemodulation理論框圖

公式描述AICviaRandomDemodulation理論Qusi-Toeplitz矩陣觀測理論框圖幾個參數(shù)的說明

B隨機濾波器的長度，d是信號的長度，N是采樣點數(shù)，s是原始信號，h是隨機濾波器可以看成是其中觀測矩陣為每一行元素移位個單元，構(gòu)成的觀測矩陣Qusi-Toeplitz矩陣觀測理論框圖幾個參數(shù)的說明可實驗結(jié)果實驗結(jié)果壓縮感知課件

Definition：Thosethataredeterminedbyafinitenumberofparameterspertimeunit.Theτ-localrateofinnovationofasignalx(t),denotedρτ,istheminimalnumberofparametersdefininganylength-τsegmentofx(t),dividedbyτ.AnFRIsignalisoneforwhichρτisfinite,atleastforlargeenoughτ.PerhapsthesimplestclassofFRIsignalscorrespondstofunctionsthatcanbeexpressedasFiniterateofinnovationSignalsDefinition：ThosethatareThissetofsignalsisalinearsubspaceofL2,whichisoftentermedashift-invariant(SI)space.FiniterateofinnovationSignalsThissetofsignalsisalineaAunionofsubspacesThismodelgeneralizesthefamilyofmultibandsignalsThefrequencies{ω?}determinethesubspaceandtheamplitudes{a?,m}determinethepositionwithinthesubspace.AunionofsubspacesThismodelOurgoalistorecoverxbyobservingNgeneralizedsamplesc=(c1,...,cN)TobtainedaswhereS:H→RNissome(possiblynonlinear)Frechetdifferentiableoperator.Thisrepresentationismoregeneralthanthewidelyusedlinearsetting,inwhichforsomesetofvectors{sn}inH.Inparticular,itmayaccountfornonlineardistortionsintroducedbythesamplingdevice.Forexample,Scanrepresentthesampleswheref(·)isanonlinearsensorresponse.WesaythatasamplingoperatorSisstablewithrespecttoXifthereexistconstants0<αs≤βs<∞suchthatforallx1,x2∈XSamplingmethodOurgoalistorecoverxbyob壓縮感知課件Thepulseshapeisknowna-priori,andthereforethesignalhasonly2Kdegreesoffreedomperperiod.SincexisperiodicitcanberepresentedintermsofitsFourierseriescoefficientswhereinaweusedPoissonsummationformula,andThepulseshapeisknowna-priwhereukand^p-1denotesthemultiplicativeinverseofp.Sincepisknowna-priori,weassumeforsimplicityofnotationthat^p=1.Inordertondthevaluesukin(1.23),lethdenotethefilterwhosez-transformis,wherethelastequalityisduetothefactthath=0.Thefilteriscalledanannihilatingfilter,sinceitzeroesthesignal^xm.Itsrootsuniquelydefinethesetofvaluesuk,providedthatthelocationstkaredistinct.whereukand^p-1denotesthe壓縮感知課件壓縮感知課件SinckernelsSinckernelsE-splinekernelsE-splinekernelsSoskernelsSoskernelsSuper-resolutionSuper-resolutionUltrasoundimagingUltrasoundimagingSuper-resolutionradarSuper-resolutionradarSinc函數(shù)觀測矩陣Sinc函數(shù)觀測矩陣Sinc函數(shù)觀測矩陣Sinc函數(shù)觀測矩陣加入個周期的觀測矩陣Poisson求和公式的變形為的傅里葉變換用有限個求和表示無窮多個周期相加的觀測矩陣Sinc函數(shù)觀測矩陣加入個周期的觀測矩陣Poisson求和公式的變形為CompressedSensing

ExplosionofinterestintheideaofCS:Recoveravectorxfromasmallnumberofmeasurementsy=AxManybeautifulpaperscoveringtheory,algorithms,andapplicationsCompressedSensing

AnalogCompressedSensingCanweusetheseideastobuildnewsub-NyquistA/Dconverters?Priorwork:Yuet.al.,Raghebet.al.,Troppet.al.

Input

Sparsity

Measurement

Recovery

StandardCSvectorxfewnonzerovaluesrandom/det.matrixconvexoptimizationgreedymethods AnalogCSanalogsignalx(t)?RFhardwareneedtorecoveranaloginput

orspecificdata(demodulation)AnalogCompressedSensingCanwOneapproachtotreatingcontinuous-timesignalswithintheCSframeworkisviadiscretizationAlternative:UsemorestandardsamplingtechniquestoconvertthesignalfromanalogtodigitalandthenrelyonCSmethodsinthedigitaldomain(Xampling=CS+Sampling)Possiblebenefits:Simplehardware,compatibilitywithexistingmethods,smallersizedigitalproblemsPossibledrawbacks:SNRsensitivitiesCanwetiethetwoworldstogether?Sampling/CompressedSensingSampling/CompressedSensingRobustnessinthePresenceofNoiseGedalyahu,Tur&Eldar(2010)Proposedscheme:Mix&integrateTakelinearcombinationsfromwhichFouriercoeff.canbeobtainedSupportsgeneralpulseshapes(timelimited)OperatesattherateofinnovationStableinthepresenceofnoise–achievestheCramer-RaoboundPracticalimplementationbasedontheMWCFouriercoeff.vectorSamplesRobustnessinthePresenceofSub-NyquistsamplerinhardwareCombinesanalogpreprocessingwithdigitalpostprocessingSupportingtheoryprovestheconceptandrobustnessforavarietyofapplicationsincludingmultibandsignalsAllowstimedelayrecoveryfromlow-ratesamples(GedalyahuandEldar09-10)Applicationstoultrasound(TurandEldar09)Xampling:Sub-NyquistSampling(MishaliandEldar,08-10)Xampling:Sub-NyquistSamplingOnlineDemonstrationsGUIpackageoftheMWCVideorecordingofsub-Nyquistsampling+carrierrecoveryinlabOnlineDemonstrationsGUIpacCantheseideasbeexploitedtocharacterizefundamentallimitsinotherareas?DegreesofFreedomToday:Applicationstolineartime-varying(LTV)systemidentificationSub-NyquistsamplingofpulsestreamscanbeusedtoidentifyLTVsystemsusinglowtime-bandwidthproductLowratesamplingmeansthesignalcanberepresentedusingfewerdegreesoffreedomTheXamplingframeworkimpliesthatmanyanalogsignalshavefewerDOFthanpreviouslyassumedbyNyquist-ratesamplingDegreesofFreedomToday:Appli

美國RICE大學(xué)的研究者們將微列陣與單一光學(xué)傳感器結(jié)合起來創(chuàng)造了一種圖像/攝像式照相機，這一相機具有圖像壓縮功能。這所大學(xué)的電子工程學(xué)教授Baraniuk說：“白噪聲是關(guān)鍵，得益于那些數(shù)學(xué)理論，我們能夠在隨機分散的測量中得到有效且連貫的圖像。單像素相機單像素相機結(jié)構(gòu)及成像原理結(jié)構(gòu)及成像原理這種單像素照相機使用了一款來自德州儀器的數(shù)字微反射鏡（DMDdigitalmicromirrordevice）及單一光電二極管。有趣的部件是數(shù)字微反射鏡，這款芯片主要用在數(shù)字背投或是投影機中。DMD芯片由大量只有細菌大小的鏡片組成，每塊微型鏡片都一面反光，一面不反光，并可以快速這種單像素照相機使用了一款來自德州儀器的數(shù)字微反射鏡翻轉(zhuǎn)。一種偽隨機模式可映射到上面。這種微反射鏡可傾斜12，在芯片的表面有黑白兩部分區(qū)域，白色部分表示反射鏡可傾斜+12.黑色部分表示反射鏡可傾斜-12.這一系列黑白區(qū)域中的反射光集中在光電二極管上。每一種偽隨機模式都會發(fā)出一組系數(shù)（光電壓），應(yīng)用這些系數(shù)和隨機種子87翻轉(zhuǎn)。一種偽隨機模式可映射到上面。這種微反射鏡可傾斜12，可重新建立圖像。Baraniuk說：“壓縮傳感的好處在于我們對樣本的圖片及影像的測量次數(shù)要多于對實際像素的測量。這能大大減少為獲得圖像/錄影編碼所要進行的計算?！?/p>

在整套系統(tǒng)中，被拍攝物體的圖像經(jīng)過鏡頭打在DMD上，而經(jīng)過DMD反射的圖像又經(jīng)過二次鏡頭聚焦在只有一，可重新建立圖像。Baraniuk說：“壓縮傳感的好處在于我個像素的傳感器上，形成一個光信號。而在拍攝過程中，DMD上每個鏡片反射的明暗矩陣以偽隨機碼的形式快速變換，每變化一次形成一個像素的型號。最后，經(jīng)過將每次的信號和偽隨機碼綜合進行計算，就得到了物體的影像.個像素的傳感器上，形成一個光信號。而在拍攝過程中，DMD上每實現(xiàn)設(shè)備實現(xiàn)設(shè)備

由于每次拍照只需要得到多個單像素信號，而在接收端和偽隨機碼綜合計算得到影像。因此解壓成像之前的信號量非常小，做到了很有效的數(shù)據(jù)壓縮，十分有利于遠距離無線傳輸（如：航天攝影）。另外，只需要單像素傳感器的特點，使得在科學(xué)領(lǐng)域中，一些原本需要大面積傳感器，或由于每次拍照只需要得到多個單像素信號是傳統(tǒng)方法無法拍攝的非可見光領(lǐng)域，這種拍攝方法都有其很大的應(yīng)用價值。研發(fā)人員還稱，DMD可以每秒數(shù)百萬次的速度翻轉(zhuǎn)，因此想把這種拍攝方法轉(zhuǎn)為民用，甚至做成和現(xiàn)在一樣的掌上相機也不是沒有可能。盡管現(xiàn)在這套系統(tǒng)只對靜止物體進行拍攝，拍一張照片需要5分鐘，整套設(shè)備要占是傳統(tǒng)方法無法拍攝的非可見光領(lǐng)域，這種拍攝方法都有其很大的應(yīng)據(jù)一張大桌子。針對數(shù)字?jǐn)z影不能應(yīng)用在很多科學(xué)領(lǐng)域，需對照相機進行改進，例如：有可能應(yīng)用在消費者市場的Terahertz圖像技術(shù)。據(jù)一張大桌子。針對數(shù)字?jǐn)z影不能應(yīng)用在很多科學(xué)領(lǐng)域，需對照相機

拍攝效果拍攝效果

拍攝效果拍攝效果

具有單像素探測器的太赫茲相機可以提高測量速度，在太赫茲頻段快速成像，能夠在機場中的隱蔽武器探測以及航天飛機隔熱層泡沫材料中的定位缺陷探測等方面發(fā)揮重要作用?；趩蜗袼叵鄼C概念的太赫茲成像的新方法，有望改進太赫茲相機的性能，使其克服現(xiàn)有成像系統(tǒng)的缺點，具有單像素探測器的太赫茲相機可以提高測量速度，在太同時提供較高的速度和較強的探測能力。這種成像方法的另一個優(yōu)點是硬件的簡單性和多功能性。通過采用一個連續(xù)波太赫茲光源，如一臺太赫茲量子級聯(lián)激光器，這種相機可以使用靈敏的單像素探測器（如高萊盒探測器）取代探測器陣列，因此降低了對同時提供較高的速度和較強的探測能力。光源功率的要求。如果采用脈沖光源，這種相機還可以將其成像能力擴展到捕獲光譜相位其他超光譜特征。

這種相機的下一代產(chǎn)品將采用電驅(qū)動或光驅(qū)動的太赫茲空間調(diào)制器來取代隨機模式的擋板。這將使其能在不需要任何機械移動部件的情況下，非常快速地對太赫茲光束進行調(diào)制。預(yù)期到那時光源功率的要求。如果采用脈沖光源，這種相機還可以將其成像能力，相機就能以視頻成像的速度獲取到充足的圖像重建信息了。

，相機就能以視頻成像的速度獲取到充足的圖像重建信息了。下圖:在單像素太赫茲相機的實驗裝置中，光束通過一塊由不透明像素的隨機圖案構(gòu)成的擋板，對一個帶有字母“R”形狀的透光孔的不透明物體進行成像。下圖:在單像素太赫茲相機的實驗裝置中，光束通過一塊由不透明壓縮感知課件壓縮感知課件目標(biāo)物體在白光中成像（左圖）。同一物體的太赫茲圖像分別通過300個測量值的壓縮傳感（中圖）和600個測量值的壓縮傳感（右圖）重建。

目標(biāo)物體在白光中成像（左圖）。同一物體的太赫茲圖像分別通過3ProposedCSColorCameraRG1G2BRG1G2BRG1G2BRG1G2BA/DColorImageRearrangetoMosiacStructureJointColorCSReconstructionDemosaicingRNG+RotationControlLens1RotatingColorFilterDMDArrayPhotodiodeLens2Fig1:(a)Shows“VirtualBayerFilter”structureontheDMDarray.ThereisnorealBayerfilter,buteachmicromirrorisvirtually“l(fā)abeled”sothatmosaicstructureofaBayerfilterisformed.(b)ProposedcolorCScameraarchitecture.ThishasaRotatingColorFilter(RCF)andaRotationControlunit(RC)asnewcomponentsintheCameraof[3].ItcapturesR,GandBmeasurementsdirectlyonBayerplanes,(therebyreducingtheoverallmeasurements)andusesjointR-G-Breconstructionschemetoproducebetterqualitycolorimage.s(a)(b)ProposedCSColorCameraRG1G2BVisualResultsFig.2:Showssomesamplehighresolutioncolorimagesusedfortesting.Fromtopright,Lena,Peppers,Light-House,Lady,Gold-HillandGirl.TheperformanceresultsontheseimagesaretabulatedinTable1,for30%,25%measurementsontheBayerR,G1,G2andBplanes.Fig.3:Showsimagesections&correspondingresults.Column-wise:Col1istheBayersampledanddemoisaicedreferenceimage(bilinearinterpolation),Col2,3arejointR-G-BE-JSM,JSMreconstructedimagesrespectively.Col4isR,G,Bindependentlyreconstructedimages.Row-wise:croppedsectionsoforiginalimages,Lady,Light-HouseandPepperinRows1,2and3respectively.VisualResultsFig.2:ShowssoLongersignalsvia“random”transformsNon-GaussianmeasurementschemeLowcomplexitymeasurement(approxO(N)versusO(MN))universallyincoherentLowcomplexityreconstructione.g.,MatchingPursuitcomputeusingtransforms

(approxO(N2)versusO(MN2))PermutedFFT(PFFT)FastTransform

(FFT,DCT,etc.)Truncation

(keepMoutofN)PseudorandomPermutationLongersignalsvia“random”trReconstructionfromPFFTOriginal65536pixelsWaveletThresholding6500coefficientsCSReconstruction26000measurements4xoversamplingenablesgoodapproximationWaveletencodingrequiresextralocationencoding+fancyquantizationstrategyRandomprojectionencodingrequiresnolocationencoding+onlyuniformquantizationReconstructionfromPFFTOriginRandomFiltering

[withJ.Tropp]Hardware/softwareimplementationStructureofconvolutionToeplitz/circulantdownsamplingkeepcertainrowsiffilterhasfewtaps,issparsepotentialforfastreconstructionCanbegeneralizedtoanaloginputDownsample(keepMoutofN)“Random”FIRFilterTime-sparsesignalsN=128,K=10Fourier-sparsesignalsN=128,K=10RandomFiltering

[withJ.TropReconstructionfromPFFTCoefficientsOriginal65536pixelsWaveletThresholding6500coefficientsCSReconstruction26000measurements4xoversamplingenablesgoodapproximationWaveletencodingrequiresextralocationencoding+fancyquantizationstrategyRandomprojectionencodingrequiresnolocationencoding+onlyuniformquantizationReconstructionfromPFFTCoeffSensornetworks:

intra-sensorand

inter-sensorcorrelation

dictatedbyphysicalphenomenaCanweexploitthesetojointlycompress?Popularapproach:collaborationinter-sensorcommunicationoverheadcomplexityatsensorsOngoingchallengeininformationtheorycommunityCorrelation

inSignal

EnsemblesSensornetworks:

intra-sensorBenefits:DistributedSourceCoding:exploitintra-andinter-sensorcorrelationsfewermeasurementsnecessaryzerointer-sensor

communicationoverheadDistributedCompressiveSensing(DCS)compresseddatadestination(reconstructjointly)CompressiveSensing:universality(randomprojections)“future-proof”encryptionrobustnesstonoise,packetlossscalabilitylowcomplexityatsensorsJointsparsitymodelsandalgorithmsfordifferentphysicalsettingsBenefits:DistributedCompressiJSM-1:Common+InnovationsModelMotivation:samplingsignalsinasmoothfieldJointsparsitymodel:length-

sequences

and

islength-

commoncomponent

,

length-

innovationcomponentshassparsity

,

havesparsity

,MeasurementsIntuition:Sensorsshouldbeableto“sharetheburden”ofmeasuringJSM-1:Common+InnovationsModeJSM-2:CommonSparseSupportsmeasureJsignals,eachK-sparsesignalssharesparsecomponents,differentcoefficients…JSM-2:CommonSparseSupportJointsparsitymodel#3(JSM-3):generalizationofJSM-1,2:length-sequenceseachsignalisincompressiblesignalsmay(DCS-2)ormaynot(DCS-1)sharesparsesupportsIntuition:eachmeasurementvectorcontainscluesaboutthecommoncomponentJSM-3:Non-SparseCommonModel…Jointsparsitymodel#3(JSM-3DCSReconstructionMeasureeachxj

independentlywithMjrandomprojectionsReconstructjointlyatcentralreceiver“Whatisthesparsestjointrepresentationthatcouldyieldallmeasurementsyj?”linearprogramming:useconcatenationofmeasurementsyjgreedypursuit:iterativelyselectelementsofsupportsetsimilartosingle-sensorcase,butmorecluesavailableDCSReconstructionMeasureeachTheoreticalResultsMj<<(standardCSresults);furtherreductionsfromjoint

reconstructionJSM-1:Slepian-WolflikeboundsforlinearprogrammingJSM-2:c=1withgreedyalgorithmasJincreases.CanrecoverwithMj

=1!JSM-3:CanmeasureatMj=cKj,essentiallyneglectingz;useiterativeestimationofzandzj.WouldotherwiserequireMj

=N!TheoreticalResultsMj<<(sJSM-1:RecoveryviaLinearProgramming117JSM-1:RecoveryviaLinearPro寫在最后成功的基礎(chǔ)在于好的學(xué)習(xí)習(xí)慣Thefoundationofsuccessliesingoodhabits118寫在最后成功的基礎(chǔ)在于好的學(xué)習(xí)習(xí)慣118謝謝大家榮幸這一路，與你同行It'SAnHonorToWalkWithYouAllTheWay講師：XXXXXXXX年XX月XX日

119謝謝大家講師：XXXXXX119壓縮感知理論與應(yīng)用智能感知與圖像理解教育部重點實驗室2011年8月IntelligentPerceptionandImageUnderstandingKeyLabofMinistryofChinaIntelligentPerceptionandImageUnderstandingKeyLabofMinistryofChina壓縮感知理論與應(yīng)用IntelligentPerceptio上次課內(nèi)容回顧Lecture1：壓縮感知概述為什么研究壓縮感知壓縮感知的涵義壓縮感知的過程壓縮感知的關(guān)鍵問題上次課內(nèi)容回顧Lecture1：壓縮感知概述FromNyquisttoCSFromNyquisttoCSCompressionOriginal2500KB

100%Compressed950KB

38%Compressed392KB

15%Compressed148KB

6%“Canwenotjustdirectlymeasurethepartthatwillnotendupbeingthrownaway?”DonohoCompressionOriginal2500KSparserepresentationofanimageviaamultiscalewavelettransform.(a)Originalimage.(b)Waveletrepresentation.Largecoefficientsarerepresentedbylightpixels,whilesmallcoefficientsarerepresentedbydarkpixels.Observethatmostofthewaveletcoefficientsareclosetozero.Sparse

inwavelet-domainSparserepresentationofanimSparseapproximationofanaturalimage.(a)Originalimage.(b)Approximationofimageobtainedbykeepingonlythelargest10%ofthewaveletcoefficients.Sparse

inwavelet-domainSparseapproximationofanatuOurPoint-Of-ViewCompressedSensing(CS)mustbebasedonsparsityandcompressibility.Thesignalsmustbesparseintime-domainorinfrquency-domain.

OurPoint-Of-ViewCompressedSeCompressedSensing“Canwenotjustdirectlymeasurethepartthatwillnotendupbeingthrownaway?”Donoho“sensing…asawayofextractinginformationaboutanobjectfromasmallnumberofrandomlyselectedobservations”Candèset.al.Nyquistrate

SamplingAnalog

Audio

SignalCompression

(e.g.MP3)High-rateLow-rateCompressed

SensingCompressedSensing“CanwenotConceptGoal:Identifythebucketwithfakecoins.Nyquist:Weighacoin

fromeachbucketCompressionBucket#numbers1numberCompressedSensing:Bucket#1numberWeighalinearcombination

ofcoinsfromallbucketsConceptGoal:IdentifythebuckMathematicalToolsnon-zeroentries

atleastmeasurementsRecovery:brute-force,convexoptimization,

greedyalgorithms,andmore…MathematicalToolsnon-zeroentCStheoryCompressedsensing(2003/4andon)–MainresultsMaximalcardinalityoflinearlyindependentcolumnsubsetsHardtocompute!isuniquelydeterminedbyDonohoandElad,2003Smallestnumberofcolumnsthatarelinearly-dependent.CStheoryCompressedsensing(isuniquelydeterminedbyisrandomwithhighprobabilityDonoho,2006andCandèset.al.,2006NP-hardConvexandtractableGreedyalgorithms:OMP,FOCUSS,etc.Donoho,2006andCandèset.al.,2006Tropp,Cotteret.al.Chenet.al.andmanyotherCompre