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

冷雪冬 王大鳴 巴斌 王建輝

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

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

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

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

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

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

時(shí)延估計(jì),壓縮感知,測量矩陣,漸進(jìn)添邊

1 引 言

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

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

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

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

2.1CS理論模型

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

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

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

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

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

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

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

稱HCS滿足NSP準(zhǔn)則,表示為HCS∈NSPR≤(S,C);當(dāng)v滿足(7)式時(shí),

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

2.2CC理論模型

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

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

3 基于PEG的準(zhǔn)循環(huán)CS時(shí)延估計(jì)算法

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ù)的最值點(diǎn)位于凸集的極值點(diǎn),(11)式可以表示為

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

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

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

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

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

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

3.2基于LDPC碼的測量矩陣設(shè)計(jì)準(zhǔn)則

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4基于PEG的準(zhǔn)循環(huán)CS時(shí)延估計(jì)算法步驟

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

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

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

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

4 仿真實(shí)驗(yàn)

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

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

圖3 不同信噪比條件下五條徑的時(shí)延估計(jì)值分布圖(a)SNR=10 dB條件下本文算法五條徑的時(shí)延估計(jì)值;(b)SNR=0 dB條件下本文算法五條徑的時(shí)延估計(jì)值(內(nèi)插圖為第三條徑時(shí)延估計(jì)值的局部放大圖)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的條件下,將本文算法與高斯隨機(jī)測量矩陣和隨機(jī)LDPC測量矩陣進(jìn)行對比,分別繪制這三種算法的正確重構(gòu)概率隨多徑數(shù)目變化的曲線,結(jié)果如圖4所示.可以看出,當(dāng)Lp≤8時(shí),三種算法的正確重構(gòu)概率沒有區(qū)別,當(dāng)Lp＞8時(shí),本文算法與隨機(jī)LDPC測量矩陣的正確重構(gòu)概率高于高斯隨機(jī)測量矩陣.本文算法由于引入PEG算法的思想,相比于隨機(jī)LDPC測量矩陣減少了Tanner圖中短環(huán)的數(shù)量,因此在Lp較大時(shí),具有更勝一籌的性能.

圖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的條件下進(jìn)行仿真,分別繪制本文算法在維度為64×512,64×1024,128×1024時(shí)正確重構(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)式,計(jì)算本文算法中測量矩陣的相關(guān)值.

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

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

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

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

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

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

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

6 結(jié) 論

在時(shí)延估計(jì)問題中,現(xiàn)有基于LDPC碼的測量矩陣具有在少量數(shù)據(jù)存儲量的條件下較好的估計(jì)性能,但在測量矩陣的生成過程中,由于隨機(jī)選擇非零元素位置,導(dǎo)致Tanner圖中短環(huán)的出現(xiàn),影響重構(gòu)效果.針對該問題,本文首先引入了PEG算法有效減少了Tanner圖中短環(huán)的存在,然后基于準(zhǔn)循環(huán)結(jié)構(gòu)構(gòu)造測量矩陣,實(shí)現(xiàn)了少量數(shù)據(jù)量條件下無偏時(shí)延估計(jì).在相同多徑數(shù)目的條件下比高斯隨機(jī)測量矩陣和隨機(jī)LDPC測量矩陣正確重構(gòu)概率更高.同時(shí)給出了數(shù)據(jù)存儲量與計(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é)報(bào)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é)報(bào) 62 174212]

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

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

[7]Wang Q,Li J,Shen Y 2013Acta Electron.Sin.41 2041(in Chinese)[王強(qiáng),李佳,沈毅2013電子學(xué)報(bào) 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)代雷達(dá)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é)報(bào)(自然科學(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é)基金(批準(zhǔn)號: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