一種壓縮感知詞典快速構造方法

張 業，李 佳

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

一種壓縮感知詞典快速構造方法

張 業，李 佳

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

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

壓縮感知；量測詞典；感知詞典；貪婪算法

0 引言

壓縮感知理論是最近幾年信號處理領域新發展起來的熱點研究方向。如果信號是稀疏信號，壓縮感知理論可以通過其非自適應線性投影精確恢復原信號。壓縮感知減小了稀疏信號的量測量并在諸多領域得到廣泛的研究[1-3]。

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

實質上，信號的恢復與詞典的“優劣”密切相關。通常用相關系數或者RIP(Restricted Isometry Property)[7-8]常數的大小來描述詞典“優劣”，相關系數小的詞典或者RIP常數小的詞典可以有效提高信號恢復算法性能。因此，相關系數或RIP常數已成為諸多詞典構造算法的標準。

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

1 壓縮感知基本理論

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

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

(1)

l0最小問題是一個數學上的NP難題，因此直接求解此問題不現實。在量測矩陣滿足一定條件下，l0最小問題與l1最小問題等價[6-7]。此后，基于l1最小問題求解算法不斷涌現。

貪婪算法為解l0最小問題次優算法，盡管其性能不及基于求解l1最小問題的線性規劃算法，但由于其計算量小而得到廣泛應用。無論是l1與l0最小問題等價，還是各種恢復算法性能，都與量測詞典性質相關,相關系數常用來衡量量測詞典優劣。

定義1：對于單位化量測詞典Φ∈Rm×n，相關系數和積累相關系數定義為：

(2)

(3)

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

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

(4)

此下限被稱為Welch界。滿足相關系數達到Welch界矩陣成為Grassmannian框架[14]。

文獻[9]提出感知詞典概念，對于量測詞典Φ∈Rm×n，存在感知詞典Ψ∈Rm×n，使得

〈ψi,φi〉>>〈ψi,φj〉，對于1≤i,j≤n，i≠j,

(5)

式中，ψi和ψj分別為詞典Ψ的第i列和第j列。文獻[6]同時提出了交叉相關系數感念。

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

(6)

(7)

2 量測與感知詞典構造方法

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

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

(8)

(9)

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

①H= ‖H′-G‖F，s.t.H′∈H；

②G= ‖G′-H‖F，s.t.G′∈G。

上述過程一直循環至終止條件滿足。

下面解決上述方法涉及問題。對于步驟①問題，文獻[12]給出如下結論：

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

(10)

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

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

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

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

(11)

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

H=SVD，

(12)

G′=SVmD，

(13)

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

基于上述討論，本文所提出的感知詞典與量測詞典構造算法如下：

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

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

(14)

3 仿真分析

利用計算機仿真分析比較Schnass算法[9]、詞典構造算法[10-11]與本文算法。算法仿真中，高斯隨機矩陣作為初始化詞典，算法終止條件常數為ε=10-5，每一實驗重復500次。

圖1給出了詞典行數為128時，構造不同列數詞典的交叉相關系數比較。可以看出，在交叉相關系數方面，詞典構造算法和本文算法都優于Schnass的算法，同時本文算法略優于詞典構造算法。

圖1 各種詞典列數所得到的交叉相關系數

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

圖2 OMP算法重建高斯稀疏信號性能比較

圖3 OMP算法重建0-1稀疏信號性能比較

選擇行數為128，圖4比較了構造不同列數詞典時，詞典構造算法和本文算法消耗時間。2種算法都應用于Matlab7.10.0.軟件，WindowsXP系統，計算機配置為雙核2.6GHzCUP，1.96G內存。從圖4可以看出，本文算法耗時要遠低于詞典構造算法，大約僅為后者的1/30。

圖4 構造不同列數詞典算法耗時

詞典構造算法由于通過文獻[17-18]中方法解決大量的非線性優化問題而增加了計算量，相比之下本文算法在保持了詞典構造算法的性能同時，降低了計算量。

4 結束語

利用交互投影算法，本文提出一種構造感知詞典和量測詞典方法，所構造的詞典具有小的交叉相關系數而且可以改進OMP算法性能。相比于詞典構造算法，本文的算法在保持了其優秀性能的同時，降低了計算量，在效率方面提高了約30倍。

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

[2] 石光明,劉丹華,高大華,等.壓縮感知理論及其研究進展[J].電子學報,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] 王 強，李 佳，沈 毅.壓縮感知中確定性測量矩陣構造算法綜述[J].電子學報,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]李 佳,王 強,沈 毅,等.壓縮感知中測量矩陣與重建算法的協同構造[J].電子學報,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

張 業，李 佳.一種壓縮感知詞典快速構造方法[J].無線電通信技術,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

河北省重大科技成果轉化專項項目(14040322Z)

張 業(1984—)，男,工程師，主要研究方向：數字信號處理、計算機網絡及信息系統。李 佳(1986—)，男,工程師，主要研究方向：數字信號處理、認知無線電、稀疏優化算法。

TN911

A

1003-3114(2017)03-30-4