一種壓縮感知詞典快速構(gòu)造方法

張 業(yè)，李 佳

(中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

一種壓縮感知詞典快速構(gòu)造方法

張 業(yè)，李 佳

(中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

提出一種基于交互投影方法的量測(cè)詞典和感知詞典構(gòu)造算法。將量測(cè)詞典和感知詞典的類Gram矩陣向理想Gram矩陣集合投影并得到投影矩陣，再將此矩陣向類Gram矩陣集合投影，此過程如此繼續(xù)直至滿足終止條件，可得到一對(duì)弱相關(guān)量測(cè)和感知詞典，其類Gram矩陣非主對(duì)角線元素接近或者達(dá)到Welch界。該算法采用一種新的向類Gram矩陣投影方法，可以極大地降低計(jì)算量,此算法得到的詞典可有效提高OMP算法性能。

壓縮感知；量測(cè)詞典；感知詞典；貪婪算法

0 引言

壓縮感知理論是最近幾年信號(hào)處理領(lǐng)域新發(fā)展起來的熱點(diǎn)研究方向。如果信號(hào)是稀疏信號(hào)，壓縮感知理論可以通過其非自適應(yīng)線性投影精確恢復(fù)原信號(hào)。壓縮感知減小了稀疏信號(hào)的量測(cè)量并在諸多領(lǐng)域得到廣泛的研究[1-3]。

壓縮感知理論主要涉及2個(gè)問題，一個(gè)是信號(hào)量測(cè)，另一個(gè)是信號(hào)恢復(fù)。對(duì)于信號(hào)量測(cè)，已有諸多類型量測(cè)詞典相繼被提出，比如部分傅里葉矩陣[4]、二值隨機(jī)矩陣[5]以及確定性測(cè)量矩陣[6]等。信號(hào)恢復(fù)問題已有多種算法提出，比如基于貪婪算法的OMP算法、線性規(guī)劃算法等。

實(shí)質(zhì)上，信號(hào)的恢復(fù)與詞典的“優(yōu)劣”密切相關(guān)。通常用相關(guān)系數(shù)或者RIP(Restricted Isometry Property)[7-8]常數(shù)的大小來描述詞典“優(yōu)劣”，相關(guān)系數(shù)小的詞典或者RIP常數(shù)小的詞典可以有效提高信號(hào)恢復(fù)算法性能。因此，相關(guān)系數(shù)或RIP常數(shù)已成為諸多詞典構(gòu)造算法的標(biāo)準(zhǔn)。

文獻(xiàn)[9]提出了感知詞典的概念并給出了感知詞典的構(gòu)造方法，此方法降低了交叉相關(guān)系數(shù)，可以提高OMP和Thresholding算法性能。文獻(xiàn)[10-11]提出了量測(cè)詞典和感知詞典構(gòu)造方法，其交叉相關(guān)系數(shù)進(jìn)一步減小，但解決線性約束最小二乘問題增加了計(jì)算量和復(fù)雜度。文獻(xiàn)[12]給出了基于交互投影方法的等角緊支框架構(gòu)造算法，對(duì)于部分維數(shù)矩陣其相關(guān)系數(shù)可達(dá)到Welch界，但對(duì)于大部分維數(shù)矩陣無法得到小相關(guān)系數(shù)矩陣。

1 壓縮感知基本理論

信號(hào)x∈Rn×1為k稀疏信號(hào)，即sup(x)≤k，sup(x)表示x中非零元素個(gè)數(shù)。Φ∈Rm×n為量測(cè)詞典且m<

min||x||0s.t.y=Φx,

(1)

l0最小問題是一個(gè)數(shù)學(xué)上的NP難題，因此直接求解此問題不現(xiàn)實(shí)。在量測(cè)矩陣滿足一定條件下，l0最小問題與l1最小問題等價(jià)[6-7]。此后，基于l1最小問題求解算法不斷涌現(xiàn)。

貪婪算法為解l0最小問題次優(yōu)算法，盡管其性能不及基于求解l1最小問題的線性規(guī)劃算法，但由于其計(jì)算量小而得到廣泛應(yīng)用。無論是l1與l0最小問題等價(jià)，還是各種恢復(fù)算法性能，都與量測(cè)詞典性質(zhì)相關(guān),相關(guān)系數(shù)常用來衡量量測(cè)詞典優(yōu)劣。

定義1：對(duì)于單位化量測(cè)詞典Φ∈Rm×n，相關(guān)系數(shù)和積累相關(guān)系數(shù)定義為：

(2)

(3)

式中，φi和φj分別為詞典Φ的第i列和第j列。

文獻(xiàn)[13]指出，當(dāng)μ<2k-1或者μ1(k-1) +μ1(k)<1時(shí)，l0最小化問題與l1最小化問題解相同，且基追蹤與OMP算法均可精確恢復(fù)稀疏信號(hào)。然而，由于量測(cè)詞典是冗余詞典(行數(shù)大于列數(shù))，其相關(guān)系數(shù)不可能為零，文獻(xiàn)[13]指出，對(duì)于冗余實(shí)詞典，當(dāng)n≤m(m-1)/2時(shí)，其相關(guān)系數(shù)存在下限為：

(4)

此下限被稱為Welch界。滿足相關(guān)系數(shù)達(dá)到Welch界矩陣成為Grassmannian框架[14]。

文獻(xiàn)[9]提出感知詞典概念，對(duì)于量測(cè)詞典Φ∈Rm×n，存在感知詞典Ψ∈Rm×n，使得

〈ψi,φi〉>>〈ψi,φj〉，對(duì)于1≤i,j≤n，i≠j,

(5)

式中，ψi和ψj分別為詞典Ψ的第i列和第j列。文獻(xiàn)[6]同時(shí)提出了交叉相關(guān)系數(shù)感念。

定義2：對(duì)于量測(cè)詞典Φ∈Rm×n和感知詞典Ψ∈Rm×n，如果〈ψi,φi〉=1，1≤i≤n，則交叉相關(guān)系數(shù)和交叉積累相關(guān)系數(shù)定義為:

(6)

(7)

2 量測(cè)與感知詞典構(gòu)造方法

本文利用交互投影方法構(gòu)造量測(cè)詞典與感知詞典。首先，定義類Gram矩陣集合G和理想Gram矩陣集合H如下[10]：

G={G=ΨTΦ、Φ,Ψ∈Rm×n，1≤i≤n}，

(8)

(9)

式中，類Gram矩陣集合實(shí)質(zhì)上為秩為m的矩陣集合，理想Gram矩陣集合為對(duì)角線元素絕對(duì)值為1，非對(duì)角線元素絕對(duì)值小于或等于Welch界矩陣集合。如果使量測(cè)詞典與感知詞典類Gram矩陣接近或成為理想Gram矩陣集合中的某一個(gè)矩陣，那么這對(duì)詞典交叉相關(guān)系數(shù)將接近或者達(dá)到Welch界。本文提出的詞典構(gòu)造算法旨在解決此問題,給定初始量測(cè)和感知詞典Φ和Ψ，類Gram矩陣為G=ΨTΦ，詞典構(gòu)造算法基本方法如下：

①H= ‖H′-G‖F(xiàn)，s.t.H′∈H；

②G= ‖G′-H‖F(xiàn)，s.t.G′∈G。

上述過程一直循環(huán)至終止條件滿足。

下面解決上述方法涉及問題。對(duì)于步驟①問題，文獻(xiàn)[12]給出如下結(jié)論：

定理3：對(duì)于給定的矩陣G，在集合H中存在矩陣H，其元素hij與矩陣G元素gij滿足關(guān)系：

(10)

則其Frobenius距離與矩陣G距離最短。

對(duì)于第2個(gè)問題，即如何在類Gram矩陣集合中尋找一矩陣使其與給定矩陣Frobenius距離最短,有以下結(jié)論。

定理4：對(duì)于給定矩陣H，對(duì)H進(jìn)行奇異值分解，即H=SVD，其中矩陣V為一對(duì)角矩陣且對(duì)角線元素(即矩陣H奇異值或特征值)按非增順序依次排列，令G=SVmD，其中Vm為一對(duì)角矩陣，前m個(gè)對(duì)角線元素為與V前m個(gè)對(duì)角線元素相同，其余對(duì)角線元素均為0。則矩陣G為集合G中與矩陣H的Frobenius距離最短矩陣。

證明：對(duì)于矩陣H和矩陣G′，令λ(H)與λ(G′)為矩陣H和矩陣G′特征值所構(gòu)成的向量，且特征值按非增順序排列。根據(jù)Wielandt-Hoffman定理[16]有：

(11)

上述等式成立當(dāng)且僅當(dāng)矩陣G′和矩陣H特征向量相等。如果矩陣H有如下分解：

H=SVD，

(12)

G′=SVmD，

(13)

式中，Vm為一對(duì)角矩陣，前m個(gè)對(duì)角線元素為與V前m個(gè)對(duì)角線元素相同，其余對(duì)角線元素均為0。證畢。

基于上述討論，本文所提出的感知詞典與量測(cè)詞典構(gòu)造算法如下：

輸入：高斯隨機(jī)單位化矩陣Φ；程序退出條件e．初始化：G=ΦTΦ．循環(huán)：第i(i≥1)個(gè)循環(huán)①H=‖H′-G‖F(xiàn)，s．t．H′∈H；②H=UΛV，Λ=diag(λ(H))；③G=UΛmV，ri=‖H-G‖F(xiàn)；④Λm=QTQ，Ψ=QUT，Φ=QV；⑤φi=φi/‖φi‖2，ψi=ψi/〈φi，ψi〉，1≤i≤n；⑥如果i≥2且ri-ri-1≤ε，退出；否則回到步驟①，i=i+1． 輸出：感知詞典Ψ和量測(cè)詞典Φ．

算法步驟⑤中，對(duì)于得到的感知詞典Ψ和量測(cè)詞典Φ按照以下步驟處理：

(14)

3 仿真分析

利用計(jì)算機(jī)仿真分析比較Schnass算法[9]、詞典構(gòu)造算法[10-11]與本文算法。算法仿真中，高斯隨機(jī)矩陣作為初始化詞典，算法終止條件常數(shù)為ε=10-5，每一實(shí)驗(yàn)重復(fù)500次。

圖1給出了詞典行數(shù)為128時(shí)，構(gòu)造不同列數(shù)詞典的交叉相關(guān)系數(shù)比較。可以看出，在交叉相關(guān)系數(shù)方面，詞典構(gòu)造算法和本文算法都優(yōu)于Schnass的算法，同時(shí)本文算法略優(yōu)于詞典構(gòu)造算法。

圖1 各種詞典列數(shù)所得到的交叉相關(guān)系數(shù)

圖2和圖3給出應(yīng)用3種算法構(gòu)造出的詞典OMP性能比較，量測(cè)詞典和感知詞典的大小選為128×256。由圖2可以看出，當(dāng)稀疏信號(hào)非零成分幅度符合均值為0、方差為1的高斯分布時(shí)，即高斯稀疏信號(hào)，OMP算法利用本文算法構(gòu)造出的詞典，能得到略高于其他詞典的重建性能。圖3顯示，當(dāng)稀疏信號(hào)非零成分幅度為1時(shí)，即0-1稀疏信號(hào)，利用本文算法構(gòu)造的詞典和詞典算法構(gòu)造的詞典OMP算法性能差不多。圖2和圖3同時(shí)表明，利用本文算法和詞典構(gòu)造算法構(gòu)造的詞典OMP性能都優(yōu)于利用Schnass算法構(gòu)造的詞典和高斯隨機(jī)詞典。

圖2 OMP算法重建高斯稀疏信號(hào)性能比較

圖3 OMP算法重建0-1稀疏信號(hào)性能比較

選擇行數(shù)為128，圖4比較了構(gòu)造不同列數(shù)詞典時(shí)，詞典構(gòu)造算法和本文算法消耗時(shí)間。2種算法都應(yīng)用于Matlab7.10.0.軟件，WindowsXP系統(tǒng)，計(jì)算機(jī)配置為雙核2.6GHzCUP，1.96G內(nèi)存。從圖4可以看出，本文算法耗時(shí)要遠(yuǎn)低于詞典構(gòu)造算法，大約僅為后者的1/30。

圖4 構(gòu)造不同列數(shù)詞典算法耗時(shí)

詞典構(gòu)造算法由于通過文獻(xiàn)[17-18]中方法解決大量的非線性優(yōu)化問題而增加了計(jì)算量，相比之下本文算法在保持了詞典構(gòu)造算法的性能同時(shí)，降低了計(jì)算量。

4 結(jié)束語(yǔ)

利用交互投影算法，本文提出一種構(gòu)造感知詞典和量測(cè)詞典方法，所構(gòu)造的詞典具有小的交叉相關(guān)系數(shù)而且可以改進(jìn)OMP算法性能。相比于詞典構(gòu)造算法，本文的算法在保持了其優(yōu)秀性能的同時(shí)，降低了計(jì)算量，在效率方面提高了約30倍。

[1]DonohoDL.CompressedSensing[J].IEEETrans.Inf.Theory，2006,52(4):1289-1306.

[2] 石光明,劉丹華,高大華,等.壓縮感知理論及其研究進(jìn)展[J].電子學(xué)報(bào),2009,37(5):1070-1081.

[3]CandesEJ.AnIntroductiontoCompressiveSampling：ASensing/samplingParadigmThatGoesAgainsttheCommonKnowledgeinDataAcquisition[J].IEEESignalProcess.Maga,2008,25(2):21-30.

[4]GilbertAC，GubaS.NearOptimalSparseFourierRepresentationsviaSampling[C]∥InProceedingsofthe34thAnnualACMSymposiumonTheoryofComputing.Quebec，Canada，2006：152-161.

[5]CandesEJ，TaoT.NearOptimalSignalRecoveryfromRandomProjections:UniversalEncodingStrategies[J].IEEETrans.Inf.Theory,2006,52(6):5406-5425.

[6] 王 強(qiáng)，李 佳，沈 毅.壓縮感知中確定性測(cè)量矩陣構(gòu)造算法綜述[J].電子學(xué)報(bào),2013,41(10):2014-2050.

[7]CandesEJ，TaoT.DecodingbyLinearProgramming[J].IEEETrans.Inf.Theory,2005,51(12):4203-4215.

[8]CandesEJ.TheRestrictedIsometryPropertyandItsImplicationsforCompressedSensing[J].C.R.Acad.Sci.Pairs，2008,346(9-10):589-592.

[9]SchnassK，VandergheynstP.DictionaryPreconditionforGreedyAlgorithms[J].IEEETrans.SignalProcess，2008，56(5):1994-2002.

[10]LiB，ShenY，LiJ.DictionariesConstructionUsingAlternatingProjectionMethodinCompressiveSensing[J].IEEESignalProcessLett，2011,18(11):663-666.

[11]李 佳,王 強(qiáng),沈 毅,等.壓縮感知中測(cè)量矩陣與重建算法的協(xié)同構(gòu)造[J].電子學(xué)報(bào),2013，41(1)：29-34.

[12]TroppJA.DesigningStructuredTightFramesviaanAlternatingProjectionMethod[J].IEEETrans.Inf.Theory，2005,51(1):188-209.

[13]TroppJA.GreedIsGood：AlgorithmicResultsforSparseApproximation[J].IEEETrans.Inf.Theory,2004,50(10)：2231-2242.

[14]WelchLR.LowerBoundontheMaximumCrossCorrelationofSignals[J].IEEETrans.Inf.Theory，1974，IT-20(3):397-399.

[15]StrohmerT，HeathRW.GrassmanianFrameswithApplicationstoCodingandCommunication[J].Appl.Comput.Harmon.Anal,2003,14(3):257-275.

[16]HornRA，JohnsonCR.MatrixAnalysis[M].Cambridge：CambridgeUniversityPress,1985.

[17]GillPE，MurrayW，WrightMH.PracticalOptimization[M].UK：AcademicPress,1981.

[18]ColemanTF，LiY.AReflectiveNewtonMethodforMinimizingaQuadraticFunctionSubjecttoBoundsonSomeoftheVariables[J].SIAMJ.Optim,1996,6(4)：1040-1058.

A Fast Dictionary Construction Algorithm in Compressive Sensing

ZHANG Ye，LI Jia

(The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China)

This paper presents a measurement and sensing dictionary construction algorithm in compressive sensing based on the alternating projection method.Gram-like matrix of measurement and sensing dictionaries is projected on the set of ideal Gram matrix，then the obtained matrix is projected on the set of Gram-like matrix.This procedure is repeated until the termination condition is met and a pair of measurement and sensing dictionaries will be obtained.The off diagonal entries of the Gram-like matrix reach or approach the Welch bound.The algorithm in this paper involves a novel method to project a matrix on the set of Gram-like matrix，which can reduce the computation amount.This algorithm improves the performance of greedy algorithm such as OMP.

compressive sensing；measurement dictionary；sensing dictionary；greedy algorithm

10.3969/j.issn.1003-3114.2017.03.07

張 業(yè)，李 佳.一種壓縮感知詞典快速構(gòu)造方法[J].無線電通信技術(shù),2017,43(3)：30-33.

[ZHANG Ye，LI Jia.A Fast Dictionary Construction Algorithm in Compressive Sensing [J].Radio Communications Technology，2017,43(3):30-33.]

2017-01-19

河北省重大科技成果轉(zhuǎn)化專項(xiàng)項(xiàng)目(14040322Z)

張 業(yè)(1984—)，男,工程師，主要研究方向：數(shù)字信號(hào)處理、計(jì)算機(jī)網(wǎng)絡(luò)及信息系統(tǒng)。李 佳(1986—)，男,工程師，主要研究方向：數(shù)字信號(hào)處理、認(rèn)知無線電、稀疏優(yōu)化算法。

TN911

A

1003-3114(2017)03-30-4