压缩感知基本理论-回顾与展望-邵文泽

17120121JournalofImageandGraphicsVol．17No．1Jan．2012TN911．72A1006-8961201201-0001-12．J．20121711-122010-04-272011-05-238632007AA12Z1426080203960672074200702880501981—、、、、。[e-mail]210094。、。Candès2006Nyquist。、、3。AdvancesandperspectivesoncompressedsensingtheoryShaoWenzeWeiZhihuiSchoolofComputerScienceandTechnologyNanjingUniversityofScienceandTechnologyNanjing210094ChinaAbstractInthepastcenturytheShannonsamplingtheoremhasunderlainnearlyallthemodernsignalacquisitiontechniques．Itclaimsthatthesamplingratemustbeatleasttwicethemaximumfrequencypresentinthesignal．Oneinherentdisadvantageofthetheoremhoweveristhelargenumberofdatasamplesparticularlyinthecaseofspecial-purposeapplications．Thesamplingdatahavetobecompressedforefficientstoragetransmissionandprocessing．RecentlyCandèsreportedanovelsamplingtheorycalledcompressedsensingalsoknownascompressivesamplingCS．Thetheoryassertsthatonecanrecoversignalsandimagesfromfarfewersamplesormeasurementsnotstrictlyspeakingaslongasoneadherestotwobasicprinciplessparsityandincoherenceorsparsityandrestrictedisometryproperty．TheaimofthisarticleistosurveytheadvancesandperspectivesoftheCStheoryincludingthedesignofsparsedictionariesthedesignofmeasurementmatricesthedesignofsparsereconstructionalgorithmsandourproposalofseveralimportantproblemstobestudied．Keywordscompressedsensingsparseapproximationincoherencemeasurementmatrixsparseoptimization0。Nyquist。。Nyquist。、、、2．cjig．cn17、。JPEG2000。1。NK。Nyquist。1/Fig.1Sketchmapoftraditionalsignalsamplingandcompression/decompressionNyquist。、、、1。NyquistCandès、Tao、Romberg、Donoho2-9。2。。2。2Fig.2Sketchmapofcompressivesampling。-10、11、12、13、14、15、16、17、18-19、20。Rice21-22。3123。。、、3。11．1RN。ψiNi=1RNx∈RNx=ΣNi=1siψix=Ψs1sxΨsi=〈xψi〉=ψ*ixΨ=ψ1|ψ2|…|ψNN×NΨ。12x∈RNΨK-1Kψii∈ΩΩ12…N|Ω|≤K13sKsi≠0i∈Ω。22x∈RNΨsx。3xΨ-。。———JPEG2000。1。、。、。Kbyte。3-Fig.3Sparserepresentationofsignalsintheformofmatrix-vector1．223yk=〈xφk〉k=12…M2x∈RNykφk。φkDeltaykNyquistφkykφkykFourier。MNxyy=Φx3x∈RNyM×1Φ=φ1|φ2|…|φM*M×N。x=Ψs3Θy=ΦΨs=Θs4Θ=ΦΨM×N。4-。x4y=Θx=ΦxΘ=Φ。4-Fig.4Sketchmapofcompressivesamplingintheformofmatrix-vectorΦMNxMN3。xΨ。1．3。1．3．136Φ～ΨRNΦ～*Φ～=IΨ*Ψ=IΦ～xΨx。Θ～=Φ～ΨμΘ～=槡Nmax1≤kj≤N|Θ～kj|。Φ～ΨμΦ～Ψ槡=Nmax1≤kj≤N〈φ～kψj〉5Φ～ΨΘ～=Φ～Ψ。Θ～L211≤μΘ～≤槡N。Θ～1槡/NΘ～μΘ～=1Θ～14．cjig．cn170Θ～μΘ～=槡N。μΘ～槡=NMN0。μΦ～Ψ=1Φ～Ψ。Φ～Ψ。1Φ～Ψ。16x∈RNΨK-。Φ～My=QΦ～x=QΘ～s=ΘsQM×NΘ=QΘ～M×N。M≥Cμ2Φ～ΨKlogN6C＞03mins∈RN‖s‖1s．t．Θs=y73s=s。1Φ～Ψ。6μΦ～Ψykk=12…Mx。μΦ～Ψ1OKlogN。L1OKlogN。1K-7。1．3．2Candès。23。4K=12…ΘδK81－δK‖s‖22≤‖Θs‖22≤1+δK‖s‖228sK-8RIP。δK1ΘRIP。δ2K＜1ΘRIPΘ2KΘT|T|=2K2K-ΘNullsi≠0i∈Ξ|Ξ|≤2K∩ΝΘ=0。ΘyK-s。K-s1y=Θs1K-s2≠s1y=Θs2。2K-s=s1－s2Θs=Θs1－s2=0δ2KΘRIP2K-ΘNull。Θ。RIP2L0、。223-24sRNK-Θ2Kδ2K＜13mins∈RN‖s‖0s．t．Θs=y9s=s。2。Θ2K11234。2L09NP-hard。3523sRNδ2K＜槡2－13mins∈RN‖s‖1s．t．Θs=y10s‖s－s‖2≤C‖s－sK‖1槡/K‖s－s‖1≤C‖s－sK‖111C＞0sKsK15sK0。3Θ2KL1。xΨK-sKs=s。Θ2K0．41410MN。3K-。11CsN－K。MKNΨΦ。Nyquist。223y=Φx+z12z。4523sRNδ2K槡＜2－112mins∈RN‖s‖1s．t．‖Θs－y‖2≤ε13εs‖s－s‖2≤C1‖s－sK‖1槡/K+C2ε14C1＞0、C2＞0sKsK。1412。。4。MKNΨΦ。3、4CandèsRIP224-27。。、928-41。22．1x。。。、、。Wavelet1Ridgelet、Curvelet、Bandlet、ContourletBeyondWavelet42-48“”49-55。、、、。53。53Fig.53Dsketchmapsofdifferentgeometricalstructuresinimages1993MallatZhang49。6．cjig．cn17。“”。。。NN。。。WaveletCosine、Gabor50、Refinement-Gaussian51、Gabor52。Wavelet、CosineWaveletWaveletCosine。Gabor。Gabor。Refinement-GaussianGauss。Gabor“”532Gabor、、。54-56。K-SVD。。。。57-61。5859。2．2。。。CandèsMKN。2．2．1Φ～Ψ。μΦ～Ψ=17OKlogN。Φ～ΨDeltaFourier24623。1x∈RNK-φ～kFourierφ～kj=N－1/2e－i2πkj/NψjDeltaψjk=δj－kFourierM=OKlogNsΩ|Ω|=Mx∈RNFourierK-φ～kDeltaφ～kj=δj－kψjFourierψjk=N－1/2ei2πjk/NM=OKlogN。7M=Oμ2Φ～ΨKlogN223。Φ～NoiseletΨHarrWaveletμΦ～Ψ槡=2ΨDaubechiesD4WaveletμΦ～Ψ=2．2Ψ17DaubechiesD8WaveletμΦ～Ψ=2．9。ΨΦ～Φ～Ψ23。NΦ～Ψ2log槡NΦ～GaussianBernoulliΦ～Ψ。1K-。xR-Lpxx1≥…≥xNixixi≤Ri－1/p1≤i≤N15xp。。15Φ～ΨΦ～Ψ。54x∈RNΨ150＜p＜1‖x‖1≤Rα。Φ～MM≥C·μ2Φ～ΨKlogNC＞03mins∈RN‖s‖1s．t．Θs=y161611－ON－ρ/α‖s－s‖2≤CpαRK/logN－r17r=1/p－1/2Cpαpα。2．2．25233、4ΘΦRIP。Φ。RIP。。2．2．1Φ～ΨM≥CKlogN4CΘ=QΦ～ΨRIP。RIPOn－ββ＞0M≥CKlogN5。2．2．1Φ～Φ1RMNΦ21/MΦ3±1槡/MBernoulliΦ。ΨΦM≥CKlogN/KΘ=ΦΨRIP。ΨΦ。Θ=ΦΨΦΨ。2．3。。3。、、。2K-Θ2K1L0。L0L0NP-hard。N。。L2s。3、、62-65。3。1L166。6L2、L1、L02D。3ΘRIPL0L1。L18．cjig．cn17BP8。BP6467M≥cKc≈logN/KON3L1。68-69、LASSO70、LARs71、GPSR72、/SIT/HIT2473-74。OKlogN/K。6L2、L1、L02DFig.62DsketchmapsofsparsesignalreconstructionbasedonL2L1L02。MP49、OMP75-77、OMPGP78、ROMP34、TMP79、StOMP32、SP80、CoSaMP33、SAMP81。OKlogN。M≥cKc≈2logNOMPONK2。BPOMP。DonohoStOMPOMP。9SAMP。3。、、。Lp0＜p≤1FOCUSS318283-85。Chartrand83LpδaK+bδa+1K＜b－1b＞1a=bp/2－p2δ2K＜1。Ji40GaussianGamma、Babacan86LaplacianJeffreyBayesianCS2。3、。3．11L1L1。L1Ψ、Φ、M、。。M。2ΨΦΘ=ΦΨRIP。MΨ。Φ3ΨΘ=ΦΨRIPMΦRIPM19。3、。1。87。Φ。。。。3．21、、“”。、。。23、4ΨΦΘ=ΦΨRIP。ΨΦ。、、、。。3、、NMR。L1。L1。4Mistretta。。。CandèsM≥2KFourier388。。。3EmmanuelJ．Candès、TerenceTao、JustinRomberg。、、、、、、、。Nyquist。。、、。1L12345610．cjig．cn17。。、、、、。。。Nyquist88。References1MallatS．AWaveletTourofSignalProcessingM．2nded.NewYorkAcademicPress1999．MallatS．M.2．．1999．2CandèsE．CompressivesamplingC//ProceedingsoftheInternationalCongressofMathematicians．MadridSpainEuropeanMathematicalSocietyPublishingHouse200631433-1452．3CandèsERombergJTaoT．RobustuncertaintyprinciplesExacts