压缩感知中测量矩阵构造综述_王强

2016-08-062016-09-06。E51305454。1992—、1955—、1979—、1988—、1987—、。1001-9081201701-0188-09DOI10．11772/j．issn．1001-9081．2017．01．0188*050003*[e-mail]。、、、、、、。TP301．6ASurveyonconstructionofmeasurementmatricesincompressivesensingWANGQiangZHANGPeilin*WANGHuaiguangYANGWangcanCHENYanlongDepartmentofVehiclesandElectricalEngineeringOrdnanceEngineeringCollegeShijiazhuangHebei050003ChinaAbstractTheconstructionofmeasurementmatrixincompressivesensingvarieswidelyandisonthedevelopmentconstantly．Inordertosortouttheresearchresultsandacquirethedevelopmenttrendofmeasurementmatrixtheprocessofmeasurementmatrixconstructionwasintroducedsystematically．Firstlycomparedwiththetraditionalsignalacquisitiontheorytheadvantagesofhighresourceutilizationandsmallstoragespacewereexpounded．Secondlyonthebasisoftheframeworkofcompressivesensingandfocusingonfouraspectstheconstructionprinciplethegenerationmethodthestructuredesignofmeasurementmatrixandtheoptimalmethodtheconstructionofmeasurementmatrixincompressivesensingwassummarizedandadvantagesofdifferentprinciplesgenerationsandstructureswereintroducedindetail．Finallybasedontheresearchresultsthedevelopmentdirectionsofmeasurementmatrixwereprospected．KeywordsCompressiveSensingCSmeasurementmatrixＲestrictedIsometryPropertyＲIPsignalreconstructionsignalacquisition0。。、、。。Candes1－2。3。、4。、“”5。、、6。、7。MethodofOptimalDirectionsMOD8、K-K-SingularValueDecompositionK-SVD9。JournalofComputerApplications2017371188－196ISSN1001-9081CODENJYIIDU2017-01-10http//．joca．cnCandes10ＲestrictedIsometryConstantＲICCandes11ＲestrictedIsometryPropertyＲIP。ＲIP。、。NP。。、。12、13、14。15、16、17。。。52、136。。1x∈ＲNNxNnxnn=12…NΨ=Ψ1Ψ2…ΨNΨiNxx=∑Ni=1siΨi1ssiNsisi=〈xΨi〉=ΨiTx2T。xsΨ。ΨK-sKNxK。sKN－KΨK-。ΦΦ∈ＲM×NMNΦMΦjj=12…NΦTj∈ＲNMyy=Φx=ΦΨs=Θs3Θ=ΦΨ。MNyxsK-yss。、1。1Fig．1Signalsacquisitionandtransmission。、、。2xΨK-ss。Θs。ΨxΨIΘ=ΦΨ=Φ2。2Fig．2MeasurementprocessofcompressivesensingMyΦxyK≤OMlogNＲIP18ＲIP。33。1024512ＲIP2．75×10－133c1024120ＲIP1．183b。ＲIPＲIPＲIP1、。98113Fig．3Compressivesensingforsparsesignals2．1ＲIP2．1．1ＲICArmin19ＲICＲIC。1K=12…ΦＲICδK41－δK‖x‖2l2≤‖Φx‖2l2≤1+δK‖x‖2l24xK-。ΨδK。2ΨK-K=12…ΘＲICδK51－δK‖x‖2l2≤‖Θx‖2l2≤1+δK‖x‖2l25K-xδ2K。3T12…N|T|≤2KΦTΦTc=xjj∈Tδ2K61－δ2K‖c‖2l2≤‖ΦTc‖2l2≤1+δ2K‖c‖2l26Ψδ2KΦTδ2K71－δ2K‖c‖2l2≤‖ΘTc‖2l2≤1+δ2K‖c‖2l272．1．2ＲIPＲICＲIPI0＜δK＜1ＲIPδ2K槡2－111。ＲIP。ＲIPＲIPＲIP。20Johnson-Lindenstrauss21ＲIP。2．2ＲIP1ＲIPl1On3OKlogN/K。Nchirps16、22。ＲIPＲIPＲIP123StatisticＲestrictedIsometryPropertyStＲIPUniqueness-guaranteedStatisticＲestrictedIsometryPropertyUStＲIP24。Berinde23ＲIPＲIP1。ＲIP23l2l1ＲIP1。4ＲIP125。ΦVKεM×NK-x∈ＲN1－2εd‖x‖1≤‖Φx‖1≤d‖x‖18dΦ1ε。ＲIP1ＲIP。ＲIP1ＲIP。ＲIP。2．3ＲIPDonoho26。Tropp27BasisPursuitBP、OrthogonalMatchingPursuitOMP09137。Donoho26。5Ψμμ1μ=maxi≠j〈ΨiΨj〉μ1K=maxΛ=KjΛ∑i∈Λ〈ΨiΨj{〉91μ≥N－M/N－1M槡10。xx=ψs11ΦΘ=ΦΨ‖s‖0＜121+1μΘ12Θ。ＲIPＲauhut282ＲIP。2μμ1ＲICδKδK≤μ1K－1≤K－1·μ13。13ＲIP。2．4StＲIP/UStＲIPＲICＲIPCalderbankStＲIPUStＲIP24StＲIP/UStＲIPStＲIP/UStＲIP。6ΦM×NK-x∈ＲN1－δ1－ε‖x‖2≤‖Φx/M‖2≤1+ε‖x‖214ΦKεδ-StＲIP。StＲIPUStＲIP。7M×NΦKεδ-StＲIP151－δββ∈ＲNΦα=Φβ15ΦKεδ-UStＲIP。StＲIP/UStＲIPη-StＲIP-able。8η-StＲIP-able0＜η＜1Φ。1Φ。∑Nj=1ΦjaΦjb=0a≠b16∑Nj=1Φja=017ja、b。2Φ“”Φj″aj″∈12…Njj'xΦj″a=Φj'aΦja183j∈2…N∑xΦja2≤M2－η19241～3StＲIP/UStＲIP。η-StＲIP-ableChirp16、Bose-Chaudhuri-Hocquenghem24。StＲIP/UStＲIP。ＲIP。Spark29、30SparkSpark。。3、。3．13．1．1Candes2K≤OMlogNＲIP18K-。0、1/nΦij～N01/M20i、ji、j。3．1．2ＲIP。1/2Φij=1槡/MP1=1/2－1槡/MP2=1/{22131、19111－2exp－c1MＲIP。ＲIP。32、2、33。ＲIP34。3．23．2．1Xu224。A1A2。A1A2。A1NxA2My。M≤NA1、A2CCij=1ij0{22i=12…Mj=12…N。4kε-Fig．4kε-expandergraph3CKε-4VA1A2|A1|=N|A2|=MA1A2。A1dSA1|S|≤KNSNS＞1－ε|S|。Jarfarpour251≤K≤N/2Kε-dMd=OlgN/K/εM=OKlgN/K/ε2{23CK-ＲIP1。3．2．2Devore35。pFpFpFpF01…p－1。p×pEEp2E。r0＜r＜pPrrPr=Qt=a0+a1t+…+antran∈F24Prpr+1Q∈PrQF→FEt→QtQt=Et*25t*t。E0001…0p－11011…1p－1p－10p－11…p－1p－126EtQt1Ep2×1vQvQp1p1pr+1p2×pr+1。Devore35K＜p/r+1ＲICδK=K－1r/pＲIP。3．2．3。Nam36OpticalOrthogonalCodeOOCBrickell37Nam36OOCOOC。9nωλOOCnvi0≤i≤n－1。ωτ∈0n－1θvivjτ≤λτ=0i=j27θsisjτ=∑n－1t=0vitvjtτ28n。GGnωωn。a=att∈01…n－1t∈Gat=1at=0a∈nω1OOC。OOC1S0-1vi0≤i≤n－1nωλOOCvinSB。2v×vv=ω+δ0≤δ≤ωHB1H0v0n×vnSBe。3D=1/槡ωBe。36DO1/槡ωK-xK=OM/logN1－N－1。Bose-Chaudhuri-Hocquenghem38、29137Chirp16、39、Ｒeed-Muller24、Berlekamp-Justesen40Low-DensityParity-CheckLDPC41。4。Do42。、、。4．143。±1g=g1g2…gnu29U=unun－1…u2u1u1un…u3u2um－1um－2…um29Bajwa44PuM≥K3lnN/K3KＲICδ3K∈01/3ＲIP。Chirps44。4．2ＲIP、。。1930ΦM×N。ΦjDistinctBlockDiagonalDBDＲepeatBlockDiagonalＲBD。Armin19ＲIP。、46、47ＲIP。4．3。Amini38。4VM×N1VpμVWp×N2ZM×N1N2μZ≤maxμVμW。5ViWi。5Fig．5Nestedmatrices436、48。5。5．1GramElad49ΘGramΦΨ。μΘ=maxi≠j〈ΘiΘj〉31ΘΘiΘiGramΞΞ=ΘTΘ32ΞΞΞijμmaxΘ=maxΞiji≠j。ΞΞΞij'=γΞijΞij≥thγsignΞijth＞Ξij≥γthΞijΞij＜γ{th333911γth。Ξ'Θ'|Θ'－ΦΨ|2FΦ'。49Elad。EladΞ50。32Ξ0ΞΞ=ΨTΦTΦΨ=I3434ΨΨTΦTΦΨΨT=ΨΨT35ΨΨTU＇ΛU＇T=ΨΨTΓ=ΦU＇minΓ‖ΛΓTΓΛ－Λ‖2F36ΓΦ=ΓU＇T。36。Gram51、52。Gram。5．2Gram。53K-SVD-。1Ψ。2ΨGramΦ。3ΘOMP。4K-SVDΨΦ。54、55。。61ＲIPＲIP、J-ＲＲIP。2、、。3。4。。。7、、、、。、、。、、、。Ｒeferences1CANDESEJＲOMBEＲGJ．Quantitativerobustuncertaintyprinci-plesandoptimallysparsedecompositionsJ．FoundationofCom-putationalMathematics200662227－254．2CANDESEJＲOMBEＲGJKTAOT．Ｒobustuncertaintyprinci-plesexactsignalreconstructionfromhighincompletefrequencyin-formationJ．IEEE