冷雪冬 王大鳴 巴斌 王建輝

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

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

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

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

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

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

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

1 引 言

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

為了解決隨機(jī)測(cè)量矩陣的數(shù)據(jù)存儲(chǔ)量冗余問(wèn)題并對(duì)其性能進(jìn)行確定性分析,很多新的方法被應(yīng)用于確定性測(cè)量矩陣的研究之中.文獻(xiàn)[9]中的測(cè)量矩陣從有限域出發(fā),根據(jù)多項(xiàng)式的系數(shù)構(gòu)造測(cè)量矩陣,在二維圖像的重構(gòu)過(guò)程中性能優(yōu)于高斯隨機(jī)矩陣.但該方法構(gòu)造的測(cè)量矩陣復(fù)雜度受維度影響較大.文獻(xiàn)[10]定義了測(cè)量矩陣的Welch界,并據(jù)此構(gòu)建了最大Welch界等式矩陣,取得了較好的重構(gòu)效果.但該矩陣只能在特定條件下構(gòu)造,應(yīng)用的普適性不高.2012年,文獻(xiàn)[11]將測(cè)量矩陣與信道編碼(channel coding,CC)理論有機(jī)地結(jié)合到一起,提出了基于低密度奇偶校驗(yàn)(low density parity check,LDPC)碼的確定性測(cè)量矩陣,實(shí)現(xiàn)了稀疏測(cè)量矩陣條件下對(duì)圖像的正確恢復(fù).但在生成LDPC碼測(cè)量矩陣時(shí)所采用的隨機(jī)選擇非零元素位置的方法,有一定概率產(chǎn)生具有短環(huán)結(jié)構(gòu)的測(cè)量矩陣,增加迭代次數(shù)導(dǎo)致重構(gòu)性能的魯棒性差.文獻(xiàn)[12,13]基于有限域生成兩類(lèi)LDPC測(cè)量矩陣,在圖像的恢復(fù)中得到了較好的效果.但是該方法并沒(méi)有考慮到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測(cè)量矩陣不僅具有準(zhǔn)循環(huán)結(jié)構(gòu),且對(duì)應(yīng)的因子(Tanner)圖中具有最大的環(huán)數(shù).在稀疏重構(gòu)的過(guò)程中利用正交匹配追蹤(orthogonal matching pursuit,OMP)算法［14]得到多徑時(shí)延的無(wú)偏估計(jì).通過(guò)仿真實(shí)驗(yàn)將本文算法與高斯隨機(jī)測(cè)量矩陣、隨機(jī)LDPC測(cè)量矩陣進(jìn)行對(duì)比,并對(duì)這三種測(cè)量矩陣的存儲(chǔ)數(shù)據(jù)量以及計(jì)算復(fù)雜度進(jìn)行分析,實(shí)驗(yàn)結(jié)果體現(xiàn)了本文所提出算法的優(yōu)越性.

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

2.1CS理論模型

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

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

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

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

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

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

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

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

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

2.2CC理論模型

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

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

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

3.1MLD與CS的理論橋梁

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

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

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

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

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

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

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

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

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

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

LDPC碼是一類(lèi)具有線(xiàn)性碼特性的分組碼,定義碼長(zhǎng)為n的LDPC碼的監(jiān)督矩陣滿(mǎn)足每行的非零元素,即行重為ωi,每一列的非零元素,即列重為ωj,這一類(lèi)碼可以稱(chēng)為(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)式可知其對(duì)應(yīng)的監(jiān)督方程為

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

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

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

本文針對(duì)此問(wèn)題進(jìn)行改進(jìn),首先引入PEG算法的思想,通過(guò)展開(kāi)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)對(duì)基矩陣進(jìn)行擴(kuò)展,得到具有準(zhǔn)循環(huán)結(jié)構(gòu)的LDPC碼測(cè)量矩陣.

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

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

3)為xj添加其他邊,以xj為父節(jié)點(diǎn)將Tanner圖展開(kāi)到深度l,如果其擴(kuò)展樹(shù)上第l層校驗(yàn)節(jié)點(diǎn)集合且第l+1層校驗(yàn)節(jié)點(diǎn)的補(bǔ)集則將xj與中連線(xiàn)最少的校驗(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)的相對(duì)位置,pij={0,1,...,L?1,∞}表示將矩陣R的每一行向右移位pij位,移位后得到循環(huán)置換矩陣;

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

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

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

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

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

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

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

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

仿真一假設(shè)接收信號(hào)的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).其中測(cè)量矩陣維度為64×512,列重ωj=8,得到時(shí)延的估計(jì)值,如圖3(a)和圖3(b)所示.可以看出本文算法在稀疏測(cè)量矩陣的條件下能夠得到時(shí)延的無(wú)偏估計(jì),如圖3(a)所示.且在低信噪比(SNR=0 dB)條件下,根據(jù)第三條徑的局部放大圖可以看出本文算法依舊能夠正確估計(jì)出時(shí)延,如圖3(b)所示,對(duì)于噪聲具有較好的魯棒性.

圖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).

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

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

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

圖5 不同矩陣維度條件下本文算法正確重構(gòu)概率隨多徑數(shù)目變化對(duì)比圖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ì)算本文算法中測(cè)量矩陣的相關(guān)值.

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

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

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

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

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

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

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

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

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

6 結(jié) 論

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

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

[2]Li J 2011Electron.Meas.Technol.34 73(in Chinese)[李劍 2011電子測(cè)量技術(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)[沈志博,董春曦,黃龍,趙國(guó)慶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)[黨骙,馬林華,田雨,張海威,茹樂(lè),李小蓓 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

?國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào):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