基于漸進添邊的準循環(huán)壓縮感知時延估計算法?

冷雪冬 王大鳴 巴斌 王建輝

(解放軍信息工程大學(xué)信息系統(tǒng)工程學(xué)院,鄭州 450001)

基于漸進添邊的準循環(huán)壓縮感知時延估計算法?

冷雪冬?王大鳴 巴斌 王建輝

(解放軍信息工程大學(xué)信息系統(tǒng)工程學(xué)院,鄭州 450001)

(2016年12月15日收到;2017年2月3日收到修改稿)

針對時延估計問題中壓縮感知類算法現(xiàn)有測量矩陣需要大量數(shù)據(jù)存儲量的問題,提出了一種基于漸進添邊的準循環(huán)壓縮感知時延估計算法,實現(xiàn)了稀疏測量矩陣條件下接收信號時延的準確估計.該算法首先建立壓縮感知與最大似然譯碼之間的理論橋梁,然后推導(dǎo)基于低密度奇偶校驗碼的測量矩陣的設(shè)計準則,引入漸進添邊的思想構(gòu)造具有準循環(huán)結(jié)構(gòu)的稀疏測量矩陣,最后利用正交匹配追蹤算法正確估計出時延.對本文算法的計算復(fù)雜度與測量矩陣的數(shù)據(jù)存儲量進行理論分析.仿真結(jié)果表明,所提算法在測量矩陣維數(shù)相同的條件下正確重構(gòu)概率高于高斯隨機矩陣和隨機奇偶校驗測量矩陣,相比于隨機奇偶校驗矩陣,在數(shù)據(jù)存儲量相等的條件下,以較少的計算復(fù)雜度代價得到了重構(gòu)概率的較大提高.

時延估計,壓縮感知,測量矩陣,漸進添邊

1 引 言

時延估計［1]問題是無線定位技術(shù)［2]中備受關(guān)注的研究熱點,壓縮感知(compressed sensing,CS)理論［3]在2004年提出后被廣泛應(yīng)用于圖像還原［4]、角度估計［5]中.在時延估計問題中,同樣可以將信號到達時間稀疏化來構(gòu)造信號的時域稀疏模型［6],從而利用CS理論對接收信號進行重構(gòu).CS理論的核心問題是信號的重構(gòu)問題,針對重構(gòu)算法的研究和改進一直是CS理論的研究重點,然而要提高信號的正確重構(gòu)概率,僅僅研究魯棒性強、普適性高的重構(gòu)算法是不夠的.由于測量矩陣在重構(gòu)信號的過程中具有至關(guān)重要的作用,針對測量矩陣的研究在近兩年成為該領(lǐng)域的研究熱點.現(xiàn)有的測量矩陣主要分為兩類,即隨機測量矩陣和確定性測量矩陣.隨機測量矩陣［7]包括高斯隨機矩陣、托普利茲矩陣、隨機伯努利矩陣、局部哈達碼矩陣和局部傅里葉矩陣等.這一類測量矩陣的性能存在瓶頸:首先,由于測量矩陣的數(shù)據(jù)往往是冗余的,因此隨機數(shù)的生成與存儲對硬件提出了很高的要求;其次,隨機矩陣只能在統(tǒng)計意義上以高概率滿足約束等距性(restricted isometry property,RIP)準則［8],即不能確保任意一個隨機矩陣都滿足正確重構(gòu)的必要條件.

為了解決隨機測量矩陣的數(shù)據(jù)存儲量冗余問題并對其性能進行確定性分析,很多新的方法被應(yīng)用于確定性測量矩陣的研究之中.文獻[9]中的測量矩陣從有限域出發(fā),根據(jù)多項式的系數(shù)構(gòu)造測量矩陣,在二維圖像的重構(gòu)過程中性能優(yōu)于高斯隨機矩陣.但該方法構(gòu)造的測量矩陣復(fù)雜度受維度影響較大.文獻[10]定義了測量矩陣的Welch界,并據(jù)此構(gòu)建了最大Welch界等式矩陣,取得了較好的重構(gòu)效果.但該矩陣只能在特定條件下構(gòu)造,應(yīng)用的普適性不高.2012年,文獻[11]將測量矩陣與信道編碼(channel coding,CC)理論有機地結(jié)合到一起,提出了基于低密度奇偶校驗(low density parity check,LDPC)碼的確定性測量矩陣,實現(xiàn)了稀疏測量矩陣條件下對圖像的正確恢復(fù).但在生成LDPC碼測量矩陣時所采用的隨機選擇非零元素位置的方法,有一定概率產(chǎn)生具有短環(huán)結(jié)構(gòu)的測量矩陣,增加迭代次數(shù)導(dǎo)致重構(gòu)性能的魯棒性差.文獻[12,13]基于有限域生成兩類LDPC測量矩陣,在圖像的恢復(fù)中得到了較好的效果.但是該方法并沒有考慮到LDPC碼所具有的特定結(jié)構(gòu),導(dǎo)致構(gòu)造復(fù)雜度較高.

本文提出了一種基于漸進添邊(progressive edge-growth,PEG)的準循環(huán)CS時延估計算法,基于PEG思想所構(gòu)造的LDPC測量矩陣不僅具有準循環(huán)結(jié)構(gòu),且對應(yīng)的因子(Tanner)圖中具有最大的環(huán)數(shù).在稀疏重構(gòu)的過程中利用正交匹配追蹤(orthogonal matching pursuit,OMP)算法［14]得到多徑時延的無偏估計.通過仿真實驗將本文算法與高斯隨機測量矩陣、隨機LDPC測量矩陣進行對比,并對這三種測量矩陣的存儲數(shù)據(jù)量以及計算復(fù)雜度進行分析,實驗結(jié)果體現(xiàn)了本文所提出算法的優(yōu)越性.

2 數(shù)學(xué)模型

2.1CS理論模型

在利用CS理論對時延進行估計的過程中,設(shè)X是長度為N的時域稀疏信號,通過線性測量后得到長度為M的觀測信號Y∈RM,W表示測量誤差.信號的觀測向量模型為

其中HCS是測量矩陣,矩陣維度為M×N,對信號的時延進行估計的過程就是通過Y對X進行重構(gòu)的過程.當W=0時,該問題是精確信號重構(gòu)問題;當W?0時,該問題為信號估計問題.由于X是稀疏信號,重構(gòu)的數(shù)學(xué)表達式為

對(2)式進行求解得到接收信號的時延估計.由于(2)式的求解是一個NP-Hard［15]問題,可以將其轉(zhuǎn)化為?1范數(shù)的線性規(guī)劃問題,

在解決(3)式的?1范數(shù)問題時,常用的算法為OMP算法、基追蹤(basic pursuit,BP)算法等.這類算法通過迭代來估計向量X.OMP算法的核心步驟為:在第k次迭代中,將Y正交地投影到HCS的每一列(原子)上,

挑選出Yk最大值所對應(yīng)的原子存入并根據(jù)(5)式計算殘差rk,如果|rk|＜ 10?5則迭代結(jié)束,反之迭代繼續(xù)進行.迭代結(jié)束后中原子在HCS的相對位置即對應(yīng)時延的估計值.

通過對現(xiàn)有重構(gòu)算法的分析,HCS在估計過程中起至關(guān)重要的作用.無論是稀疏信號還是信號中含有噪聲的偽稀疏信號,在“合適”的測量矩陣的測量下均能準確地恢復(fù)出信號.根據(jù)文獻[16],“合適”的測量矩陣需要滿足RIP準則、零空間性(null-space property,NSP)準則［17]等條件.由于NSP準則是正確重構(gòu)的充要條件,且有助于構(gòu)造與CC理論相結(jié)合的測量矩陣,下面對測量矩陣的NSP準則進行推導(dǎo).

定義a為任意實向量,對于實數(shù)域R上的N列矩陣HCS,定義其R維零空間為NullspR(HCS)={a∈RN|HCS.a=0}.令S? I(HCS),其中I(HCS)為HCS的列向量集合,如果對于任意非負常數(shù)C∈R≥0,零空間上所有向量v∈NullspR(HCS)都滿足(6)式時,

稱HCS滿足NSP準則,表示為HCS∈NSPR≤(S,C);當v滿足(7)式時,

稱HCS滿足嚴零空間特性(strict null-space property,S-NSP)準則,表示為HCS∈NSPR＜(S,C).當HCS滿足NSP準則時,稀疏信號可以通過HCS成功重構(gòu).

2.2CC理論模型

在CC理論中,對于任何一個無記憶信道,假設(shè)傳輸碼字A在有限域N2∈{0,1}上取值,接收碼字為B,在傳輸過程中傳輸A接收B的概率為PB|A(B|A). 編碼準則基于線性二進制碼γCC,令的生成矩陣.那么A可以由GCC和信息向量ε編碼產(chǎn)生,即A=GCC.ε(mod2).采用最大似然譯碼(maximum likelihood decoding,MLD),根據(jù)B對A進行譯碼的數(shù)學(xué)模型為

通過求解(9)式實現(xiàn)對傳輸碼字的譯碼.在第3部分將對MLD的原理進行進一步分析,并推導(dǎo)出MLD與CS理論測量矩陣之間的聯(lián)系.

3 基于PEG的準循環(huán)CS時延估計算法

3.1MLD與CS的理論橋梁

根據(jù)對數(shù)函數(shù)的單調(diào)性,maxPB|A(B|A′)可以轉(zhuǎn)化為

定義對數(shù)函數(shù)比率為

由于Ai∈{0,1},因此對數(shù)函數(shù)可以表示為

根據(jù)(10)式,(9)式可以表示為如下形式:

由于線性函數(shù)的最值點位于凸集的極值點,(11)式可以表示為

其中conv(γCC)表示γCC在Rn空間上對應(yīng)的凸集.(12)式是一個線性規(guī)劃問題,但是其計算復(fù)雜度隨碼長的增加而指數(shù)性增加.(12)式可以通過對其約束的松弛集最優(yōu)化來求解,即

其中HCC是校驗矩陣,?(HCC)是conv(γCC)的松弛集,滿足?(HCC)? conv(γCC).定義HCC的基本圓錐ψ(HCC)為滿足(14)式的向量ρ的集合,

其中I(HCC)是HCC列向量的集合,J(HCC)是HCC行向量的集合.根據(jù)文獻[11]可知,約束于?(HCC)的正確譯碼概率等同于約束于ψ(HCC)的正確譯碼概率,且當ψ(HCC)中的向量ρ滿足(15)式時,MLD能夠正確譯碼,

(15)式與S-NSP準則的表達式一致,即可以將MLD與CS理論聯(lián)系在一起.

當HCS僅在有限域N2∈{0,1}上取值時,如果HCS滿足S-NSP準則,那么HCS也滿足基本圓錐正確譯碼的條件.因此對于任意一個給定的二進制矩陣HCS,當HCS在MLD中具有較好的性能時,將HCS作為測量矩陣對信號進行重構(gòu)也同樣具有著極好的性能,CS理論與MLD的理論橋梁如圖1所示.LDPC矩陣已經(jīng)被證明在CC模型中具有能夠逼近香農(nóng)限的性能,因此基于LDPC碼對測量矩陣進行確定性構(gòu)建能夠提高正確重構(gòu)出時延的概率.

圖1 CS與MLD的理論連接橋梁圖Fig.1.The theoretical bridge graph between the CS theory and the MLD theory.

3.2基于LDPC碼的測量矩陣設(shè)計準則

LDPC碼是一類具有線性碼特性的分組碼,定義碼長為n的LDPC碼的監(jiān)督矩陣滿足每行的非零元素,即行重為ωi,每一列的非零元素,即列重為ωj,這一類碼可以稱為(n,ωj,ωi)規(guī)則低密度校驗碼.由于其校驗矩陣中僅包含少量的非零項,即LDPC碼具有稀疏性.例如一個(8,2,4)的LDPC碼監(jiān)督矩陣如(16)式所示:

H的每一列具有2個非零向量,每一行具有4個非零向量,根據(jù)(16)式可知其對應(yīng)的監(jiān)督方程為

將這四個監(jiān)督方程的約束關(guān)系分別記為Z1,Z2,Z3,Z4,碼元的約束關(guān)系可以表示為LDPC碼的Tanner圖,如圖2所示.

圖2 (8,2,4)的規(guī)則LDPC碼的因子圖Fig.2.Tanner graph of the regular(8,2,4)LDPC code.

圖2中,實心節(jié)點稱為校驗節(jié)點,與監(jiān)督方程的約束關(guān)系相對應(yīng),空心節(jié)點稱為變量節(jié)點,與LDPC碼的碼元相對應(yīng).變量節(jié)點與校驗節(jié)點的連線表示在監(jiān)督方程的第i個約束關(guān)系Zi中包含LDPC碼中第j個碼元xj.如果從一個節(jié)點出發(fā),不經(jīng)過重復(fù)的路線,能回到起始節(jié)點,則所經(jīng)過的節(jié)點與路線可以構(gòu)成一個環(huán),其中連線的數(shù)目即環(huán)的長度.如Z1→x2→Z3→x6→Z1是一個長度為4的環(huán).Tanner圖不但是研究LDPC碼的一個重要工具,而且是一個重要的性能指標.在稀疏重構(gòu)的過程中,采用LDPC碼測量矩陣對信號正確重構(gòu)的前提是節(jié)點之間傳遞信息統(tǒng)計獨立,而當LDPC碼的Tanner圖中有環(huán)存在時,意味著從某一節(jié)點發(fā)送的信息經(jīng)過環(huán)回路的傳遞后回到發(fā)送節(jié)點,導(dǎo)致了發(fā)送節(jié)點信息的疊加,影響了重構(gòu)的準確性.然而對于有限長度的測量矩陣而言,其LDPC碼的長度是有限的,環(huán)的存在必不可少,而短環(huán)的存在更會增加迭代次數(shù),導(dǎo)致重構(gòu)性能差.因此在設(shè)計過程中,在給定測量矩陣維度的情況下,應(yīng)基于環(huán)數(shù)最大的原則設(shè)計基于LDPC碼的測量矩陣.

3.3基于PEG思想的準循環(huán)LDPC測量矩陣的構(gòu)造

文獻[18]中首次利用隨機構(gòu)造的LDPC碼監(jiān)督矩陣作為測量矩陣,實現(xiàn)了接收信號角度的正確重構(gòu),該方法構(gòu)建的測量矩陣雖然具有稀疏特性,降低了存儲空間,但是碼長趨近于無窮大,因此通常僅具有理論分析意義,而且隨機構(gòu)造的LDPC碼由于其結(jié)構(gòu)不可控制,有一定概率生成存在短環(huán)結(jié)構(gòu)的測量矩陣,從而導(dǎo)致不能精確重構(gòu)出信號.

本文針對此問題進行改進,首先引入PEG算法的思想,通過展開Tanner圖,連接距離最遠的變量節(jié)點和校驗節(jié)點的方式,令Tanner圖的環(huán)數(shù)最大化,構(gòu)造出環(huán)數(shù)最大的基矩陣;然后基于循環(huán)結(jié)構(gòu)對基矩陣進行擴展,得到具有準循環(huán)結(jié)構(gòu)的LDPC碼測量矩陣.

本文構(gòu)造矩陣維度為M×N,列重為ωj的測量矩陣的步驟為:

2)任意選擇一個變量節(jié)點xj,連接Tanner圖中連線最少的校驗節(jié)點Zi,將這條連線稱為xj的邊,記做

3)為xj添加其他邊,以xj為父節(jié)點將Tanner圖展開到深度l,如果其擴展樹上第l層校驗節(jié)點集合且第l+1層校驗節(jié)點的補集則將xj與中連線最少的校驗節(jié)點相連;

4)重復(fù)步驟3,添加完畢所有與xj相連的邊集合;

5)重復(fù)步驟2—4,添加完畢所有變量節(jié)點集合X={x0,x1,...,xt?1},構(gòu)造出維度為c×t的基矩陣Q,其中Q中1代表非零循環(huán)子矩陣,0代表全零矩陣;

6)根據(jù)Q和(18)式計算Q中每個元素的循環(huán)移位次數(shù)矩陣P,

其中z表示每一行中第z+1個“1”元素出現(xiàn)的相對位置,pij={0,1,...,L?1,∞}表示將矩陣R的每一行向右移位pij位,移位后得到循環(huán)置換矩陣;

7)根據(jù)矩陣Q和P,用循環(huán)置換矩陣和全零矩陣分別代替Q中的“1”元素和“0”元素,擴展后得到測量矩陣HCS.

3.4基于PEG的準循環(huán)CS時延估計算法步驟

根據(jù)上述推導(dǎo),可以將稀疏重構(gòu)時延估計問題中基于矩陣循環(huán)群LDPC碼的估計算法歸納為如下步驟:

1)利用3.3節(jié)中的設(shè)計算法構(gòu)造循環(huán)LDPC碼測量矩陣HCS;

2)通過測量矩陣得到接收信號Y,利用2.1節(jié)中的OMP算法,根據(jù)(4)式,經(jīng)過k次迭代選取原子;

3)根據(jù)HCS與τ的對應(yīng)關(guān)系得到時延估計值

4 仿真實驗

本文研究的是CS類時延估計算法,為驗證本文算法的實用性與魯棒性,采用蒙特卡羅實驗將本文算法與高斯隨機測量矩陣和隨機LDPC測量矩陣進行對比分析.

仿真一假設(shè)接收信號的Lp=5,到達時間分別為 τ1=200 ns, τ2=400 ns, τ3=600 ns,τ4=800 ns,τ5=1000 ns,分別在SNR=10和0 dB的條件下采用本文算法進行m=200的仿真實驗.其中測量矩陣維度為64×512,列重ωj=8,得到時延的估計值,如圖3(a)和圖3(b)所示.可以看出本文算法在稀疏測量矩陣的條件下能夠得到時延的無偏估計,如圖3(a)所示.且在低信噪比(SNR=0 dB)條件下,根據(jù)第三條徑的局部放大圖可以看出本文算法依舊能夠正確估計出時延,如圖3(b)所示,對于噪聲具有較好的魯棒性.

圖3 不同信噪比條件下五條徑的時延估計值分布圖(a)SNR=10 dB條件下本文算法五條徑的時延估計值;(b)SNR=0 dB條件下本文算法五條徑的時延估計值(內(nèi)插圖為第三條徑時延估計值的局部放大圖)Fig.3.Distribution of time delay estimation of 5 path under di ff erent SNR conditions:(a)Time delay estimation of 5 path under the condition of SNR=10 dB by the algorithm in this paper;(b)time delay estimation of 5 path under the condition of SNR=0 dB by the algorithm in this paper(the interior illustration is the local magni fi cation for time delay estimation of the third path).

仿真二在測量矩陣維度相同(維度為64×512),SNR=10 dB的條件下,將本文算法與高斯隨機測量矩陣和隨機LDPC測量矩陣進行對比,分別繪制這三種算法的正確重構(gòu)概率隨多徑數(shù)目變化的曲線,結(jié)果如圖4所示.可以看出,當Lp≤8時,三種算法的正確重構(gòu)概率沒有區(qū)別,當Lp＞8時,本文算法與隨機LDPC測量矩陣的正確重構(gòu)概率高于高斯隨機測量矩陣.本文算法由于引入PEG算法的思想,相比于隨機LDPC測量矩陣減少了Tanner圖中短環(huán)的數(shù)量,因此在Lp較大時,具有更勝一籌的性能.

圖4 不同算法正確重構(gòu)概率隨多徑數(shù)目變化對比圖Fig.4.The variation of the probability of correct reconstruction with the number of multipath contrast of di ff erent algorithms.

仿真三在不同測量矩陣維度,SNR=10dB的條件下進行仿真,分別繪制本文算法在維度為64×512,64×1024,128×1024時正確重構(gòu)概率隨多徑數(shù)目變化的曲線,仿真結(jié)果如圖5所示.可以看出在仿真條件一定的條件下,128×1024維的測量矩陣有著最好的重構(gòu)效果.因此正確重構(gòu)概率的下降過程隨測量矩陣維度的增加而滯后.

圖5 不同矩陣維度條件下本文算法正確重構(gòu)概率隨多徑數(shù)目變化對比圖Fig.5.The variation of the probability of correct reconstruction with the number of multipath contrast of di ff erent matrix dimensions.

仿真四在矩陣維度為64×512,SNR=10 dB的條件下,根據(jù)(19)式,計算本文算法中測量矩陣的相關(guān)值.

其中‖.‖2為向量的?2范數(shù).本文算法中測量矩陣的相關(guān)值隨列重的變化如圖6所示,可以看出相關(guān)值隨列重的增加而減小.根據(jù)文獻[19],可知測量矩陣相關(guān)值越小,重構(gòu)精度越高.根據(jù)表1可知列重的增加會導(dǎo)致存儲空間與計算復(fù)雜度的增加,因此為平衡重構(gòu)精度與存儲空間及計算復(fù)雜度之間的關(guān)系,本文算法中測量矩陣的列重取值設(shè)置為8.

圖6 本文算法測量矩陣相關(guān)值隨列重變化示意圖Fig.6.The variation of the measurement matrix correlation value with the column weight of the algorithm in this paper.

5 存儲空間與計算復(fù)雜度分析

假設(shè)測量矩陣的維度為M×N,隨機LDPC測量矩陣與本文測量矩陣的列重均為ωj.由于高斯隨機測量矩陣中的每個元素均為隨機數(shù),因此高斯隨機測量矩陣的存儲空間為M×N,LDPC類測量矩陣的每行僅有ωj個元素取值為1,其余元素為0,因此LDPC類測量矩陣的存儲空間為N×ωj.

在采用CS算法估計時延的過程中,計算復(fù)雜度分成兩部分,即測量矩陣的生成與信號的重構(gòu).在采用OMP算法重構(gòu)信號的過程中,計算復(fù)雜度主要包括兩部分:計算相關(guān)值u,復(fù)雜度為O(MN);更新余量,復(fù)雜度為O(3M+2),為正確重構(gòu)全部時延,算法需經(jīng)過Lp次迭代.高斯隨機測量矩陣只需要生成維度為M×N的隨機數(shù),因此算法復(fù)雜度為

由于隨機LDPC測量矩陣在生成過程中,在每一列隨機選取ωj個非零元素,因此算法復(fù)雜度為

生成測量矩陣的復(fù)雜度為O(2ct+2).

表1列出了三種算法計算復(fù)雜度與存儲空間的對比.本文算法相比于高斯隨機測量矩陣降低了存儲空間,與隨機LDPC測量矩陣相比,在存儲空間相同的條件下,以較小復(fù)雜度的代價得到了性能的較大提升.

表1 算法計算復(fù)雜度與存儲空間對比表Table 1.The comparison of the algorithm complexity and storage space.

6 結(jié) 論

在時延估計問題中,現(xiàn)有基于LDPC碼的測量矩陣具有在少量數(shù)據(jù)存儲量的條件下較好的估計性能,但在測量矩陣的生成過程中,由于隨機選擇非零元素位置,導(dǎo)致Tanner圖中短環(huán)的出現(xiàn),影響重構(gòu)效果.針對該問題,本文首先引入了PEG算法有效減少了Tanner圖中短環(huán)的存在,然后基于準循環(huán)結(jié)構(gòu)構(gòu)造測量矩陣,實現(xiàn)了少量數(shù)據(jù)量條件下無偏時延估計.在相同多徑數(shù)目的條件下比高斯隨機測量矩陣和隨機LDPC測量矩陣正確重構(gòu)概率更高.同時給出了數(shù)據(jù)存儲量與計算復(fù)雜度分析,仿真結(jié)果表明該算法性能優(yōu)越、穩(wěn)定可靠.

[1]Zhang Q F,Huang J G,Xie Y Q 1995Acta Acust.20 211(in Chinese)[張群飛,黃建國,謝一清 1995聲學(xué)學(xué)報20 211]

[2]Li J 2011Electron.Meas.Technol.34 73(in Chinese)[李劍 2011電子測量技術(shù) 34 73]

[3]Donoho D L 2006IEEE Trans.Inform.Theory52 1289

[4]Ning F L,He B J,Wei J 2013Acta Phys.Sin.62 174212(in Chinese)[寧方立,何碧靜,韋娟 2013物理學(xué)報 62 174212]

[5]Shen Z B,Dong C X,Huang L,Zhao G Q 2014J.Electron.Inform.Technol.36 2935(in Chinese)[沈志博,董春曦,黃龍,趙國慶2014電子與信息學(xué)報36 2935]

[6]Leng X D,Ba B,Lu Z Y,Wang D M 2016Acta Phys.Sin.65 210701(in Chinese)[冷雪冬,巴斌,逯志宇,王大鳴2016物理學(xué)報65 210701]

[7]Wang Q,Li J,Shen Y 2013Acta Electron.Sin.41 2041(in Chinese)[王強,李佳,沈毅2013電子學(xué)報 41 2041]

[8]Candes E J,Tao T 2005IEEE Trans.Inform.Theory51 4203

[9]DeVore R A 2007J.Complexity23 918

[10]Xia P F,Zhou S L,Giannakis G B 2005IEEE Trans.Inform.Theory51 1900

[11]Dimakis A G,Smarandache R,Vontobel P O 2012IEEE Trans.Inform.Theory58 3093

[12]Xia S T,Liu X J,Jiang Y 2015IEEE Trans.Signal Process.63 1017

[13]Mohades A,Tadaion A A 2016IET Signal Process10 168

[14]Elad M 2008IEEE Trans.Signal Process.55 5695

[15]Hochba D S 1997ACM Sigact News28 40

[16]Tillmann A M,Pfetsch M E 2014IEEE Trans.Inform.Theory60 1248

[17]Gao Y,Peng J G,Yue S G,Zhao Y 2015J.Function Spaces205 579853

[18]Sun J M 2016Modern Radar38 46(in Chinese)[孫晶明2016現(xiàn)代雷達38 46]

[19]Dang K,Ma L H,Tian Y,Zhang H W,Ru L,Li X B 2015J.Xidian Univ.42 186(in Chinese)[黨骙,馬林華,田雨,張海威,茹樂,李小蓓 2015西安電子科技大學(xué)學(xué)報(自然科學(xué)版)42 186]

PACS:07.50.Qx,07.05.Kf,84.40.Ua,89.70.EgDOI:10.7498/aps.66.090703

A quasi-cyclic compressed sensing delay estimation algorithm based on progressive edge-growth?

Leng Xue-Dong?Wang Da-Ming Ba Bin Wang Jian-Hui

(The PLA Information Engineering University,Zhengzhou 450001,China)

15 December 2016;revised manuscript

3 February 2017)

Time delay estimation(TDE)is a hot research topic in wireless location technology.Compressed sensing(CS)theory has been widely applied to image reconstruction and direction of arrival estimation since it was proposed in 2004.The sparse model can be constructed in time domain for estimating the time delay by using the CS theory.The measurement matrix plays a crucial role in the processing of signal reconstruction which is the core problem of CS theory.Therefore the research in the measurement matrix has becomes a hotspot in recent years.The existing measurement matrix is mainly divided into two categories,i.e.,random measurement matrix and deterministic measurement matrix.The performance of random measurement matrix has bottlenecks.Firstly,because of the redundant measurement matrix data,the generation and storage of the random number put forward a high requirement for hardware.Secondly the random matrix can only satisfy the restricted isometry property in a statistical sense.The research of the deterministic measurement matrix is of great value under this background.The parity check matrix of low density parity check(LDPC)code has good performance in CS theory.However,the method of randomly selecting non-zero element position has a certain probability to generate a measurement matrix with a short loop structure during generating LDPC code measurement matrix.The robustness of the reconstruction performance decreases with the increase of iteration times.

A novel quasi-cyclic CS algorithm based on progressive edge-growth is constructed to estimate the time delay.The purpose of this article is to deal with the need to store a large number of data in existing measurement matrix during time delay,by using the CS theory.The algorithm presented here can achieve TDE in a high precision.First,the theoretical bridge between CS and the maximum likelihood decoding is established.And the design criterion of measurement matrix based on the LDPC code is derived.The sparse measurement matrix with quasi-cyclic structure is constructed by introducing the idea of progressive edge-growth.Finally,the orthogonal matching pursuit algorithm is used to estimate the time delay.Furthermore,the computational complexity of the algorithm and the data storage of the measurement matrix are analyzed theoretically.Simulations show that the correct reconstruction probability of the proposed approach is higher than those of the Gauss random matrix and random LDPC matrix under the same dimension.Compared with the random LDPC matrix,the proposed method can improve performance at the expense of less complexity under the condition of the same data storage.

time delay estimation,compressed sensing,measurement matrix,progressive edge-growth

10.7498/aps.66.090703

?國家自然科學(xué)基金(批準號:61401513)資助的課題.

?通信作者.E-mail:lengxuedong@outlook.com

*Project supported by the National Natural Science Foundation of China(Grant No.61401513).

?Corresponding author.E-mail:lengxuedong@outlook.com