沈子鈺，褚杭柯，唐川雁

（杭州電子科技大學(xué) 通信工程學(xué)院，浙江 杭州 310018）

0 引 言

傳統(tǒng)采樣定理要求采樣頻率是信號(hào)帶寬的2倍以上，從而保證采樣所得信號(hào)不失真。因此，在處理超寬帶信號(hào)時(shí)，就會(huì)面臨許多困難。壓縮感知（Compressive Sensing，CS）[1]是一種新的稀疏信號(hào)采樣和重建理論。該理論中，信號(hào)采樣和壓縮能同時(shí)完成，使得系統(tǒng)能夠低于奈奎斯特采樣頻率采樣，降低了系統(tǒng)的數(shù)據(jù)采樣和儲(chǔ)存成本，適合應(yīng)用于超寬帶通信系統(tǒng)。Jose[2]是最早研究壓縮感知應(yīng)用于超寬帶的學(xué)者之一。文獻(xiàn)[2]中提到了兩種超寬帶稀疏信號(hào)的表示方式，一種用時(shí)域稀疏字典來(lái)表示，即單位矩陣，一種用多徑分集字典來(lái)表示，能夠更加稀疏地表示超寬帶信號(hào)，因此被更多采用。但是，多徑分集字典由超寬帶脈沖波形位移產(chǎn)生，相鄰原子之間的相關(guān)性較高，在使用匹配追蹤算法時(shí)，會(huì)對(duì)原子的正確選擇造成一定干擾。壓縮采樣匹配追蹤（Compressive Sampling Matching Pursuit，CoSaMP）[3]算法、稀疏度自適應(yīng)匹配追蹤（Sparsity Adaptive Matching Pursuit，SAMP）[4]算法和正則化正交匹配 追 蹤（Regularized Orthogonal Matching Pursuit，ROMP）[5]算法，每次迭代都會(huì)選取多個(gè)原子，使得選取相鄰原子的可能性加大而產(chǎn)生誤選。廣義正交匹配追蹤（Generalized Orthogonal Matching Pursuit，GOMP）[6]每次迭代選擇L個(gè)原子，L被稱為迭代步長(zhǎng)。L越大，GOMP發(fā)生原子誤選的可能性越高。正交匹配追蹤（Orthogonal Matching Pursuit，OMP）算法[7]由于每次迭代只選擇一個(gè)原子，所以重構(gòu)精度沒(méi)有明顯降低。但是，OMP的迭代次數(shù)過(guò)多，需要大量計(jì)算時(shí)間，所以L在一定范圍內(nèi)時(shí)，GOMP更加適合應(yīng)用于超寬帶通信。

本文在GOMP算法的基礎(chǔ)上，針對(duì)超寬帶信號(hào)稀疏表示的特點(diǎn)做出改進(jìn)，盡可能避免一定區(qū)間范圍內(nèi)同時(shí)選擇多個(gè)原子。仿真實(shí)驗(yàn)表明，本文算法能夠在運(yùn)算時(shí)間接近GOMP的情況下，獲得更高的重構(gòu)精度。而相對(duì)于OMP而言，本文算法能在保證重構(gòu)精度的同時(shí)，有效節(jié)省運(yùn)算時(shí)間。

1 壓縮感知理論

壓縮感知理論指出：假設(shè)信號(hào)x∈Rn在n×n維的稀疏字典下可以被稀疏表示，稀疏度k＜n，通過(guò)m×n維的測(cè)量矩陣Φ隨機(jī)采樣后得到m(k＜m＜n)維的觀測(cè)向量y為：

其中Θ稱作傳感矩陣，向量α是信號(hào)x在稀疏字典Ψ下的稀疏表示。由于m＜n，通過(guò)觀測(cè)向量y和測(cè)量矩陣Φ無(wú)法直接求信號(hào)x，所以將其轉(zhuǎn)化成如下最優(yōu)化問(wèn)題：

其中，||α||0表示α的l0范數(shù)。式（2）中的優(yōu)化問(wèn)題是一個(gè)NP-Hard問(wèn)題，通常在傳感矩陣滿足約束等距性質(zhì)（Restricted Isometry Property，RIP）[8]的條件下，將式（2）中l(wèi)0范數(shù)優(yōu)化問(wèn)題轉(zhuǎn)化為如式（3）所示的l1范數(shù)優(yōu)化問(wèn)題：

通過(guò)相關(guān)重構(gòu)算法，如OMP算法、基追蹤（Basis Pursuit，BP）算法[9]和迭代硬閾值（Iterative Hard Thresholding，IHT）算法[10]等，就可以利用已知的觀測(cè)向量y和傳感矩陣Θ求得稀疏表示向量α，再進(jìn)而求出信號(hào)x。

2 超寬帶信號(hào)的快速匹配追蹤算法

2.1 算法分析

首先介紹多徑分集字典。脈沖超寬帶信號(hào)經(jīng)過(guò)多條不同時(shí)延和衰落的路徑到達(dá)接收機(jī)，接收信號(hào)就由這些分量組合而成。稀疏字典的設(shè)計(jì)應(yīng)該盡可能考慮和利用被稀疏表示信號(hào)的結(jié)構(gòu)與特征。所以，文獻(xiàn)[2]提出了一種稀疏表示基，即：

其中n∈{1,2,…N}，p(t)表示超寬帶發(fā)射脈沖波形，τ表示理論上的采樣時(shí)間間隔。若N表示一次觀測(cè)的總采樣點(diǎn)數(shù)，則一次觀測(cè)的總時(shí)長(zhǎng)為T=Nτ。接收信號(hào)在此稀疏字典下可表示為：

其中，K既代表信號(hào)多徑的數(shù)目，也代表信號(hào)x的稀疏度，{α(nl)}為各個(gè)多徑分量的幅值。超寬帶信號(hào)占用的帶寬極寬，具有高多徑分辨率，可認(rèn)為多徑分量重疊的概率很小，且只有一小部分的多徑分量幅值較大。因此，超寬帶信號(hào)在該稀疏字典下可以被稀疏表示，且相對(duì)于時(shí)域稀疏字典，這種表示方法的結(jié)果更加稀疏。

目前，關(guān)于壓縮感知應(yīng)用于超寬帶的研究中，大多數(shù)采用了多徑分集字典作為稀疏矩陣。因?yàn)槎鄰椒旨值湎啾扔跁r(shí)域稀疏字典，更能充分利用脈沖超寬帶信號(hào)的稀疏性。使用時(shí)域稀疏字典時(shí)，無(wú)論采用何種重構(gòu)算法，重構(gòu)精度都比較低。因此，實(shí)際應(yīng)用中采用時(shí)域稀疏字典是不可行的。

然而，在使用多徑分集字典時(shí)，CoSaMP、SAMP、ROMP均出現(xiàn)了較大誤差，原因是多徑分集字典的相鄰原子相關(guān)性很高，匹配追蹤類算法采用內(nèi)積的絕對(duì)值大小作為原子篩選的標(biāo)準(zhǔn)。正確原子相鄰的位置的內(nèi)積絕對(duì)值往往也較大，若一次迭代中選擇很多原子，那么在匹配追蹤的原子篩選過(guò)程中容易選擇正確原子的相鄰原子，從而產(chǎn)生誤選。

文章第3節(jié)的圖1可以看出，隨著GOMP迭代步長(zhǎng)的增大，重構(gòu)精度明顯下降。但是，當(dāng)字典為單位矩陣時(shí)，迭代步長(zhǎng)的增大并不會(huì)造成重構(gòu)精度明顯下降[6]。由此可以證明，多徑分集字典對(duì)迭代步長(zhǎng)較大的匹配追蹤算法會(huì)有一定影響，問(wèn)題的根本原因是正確原子的相鄰原子與殘差的內(nèi)積值較大，致使其容易在同一次迭代中被選中。解決這一問(wèn)題的辦法是在匹配原子的過(guò)程中盡量避免同一次迭代選中相鄰原子?；谶@樣的目的，本文提出了一種算法，使得同一次迭代所選原子保持一定距離。若只選擇正確的原子，再經(jīng)過(guò)正交化處理，那么下一次迭代中殘差與其相鄰原子的內(nèi)積值會(huì)明顯減小，從而可以有效降低誤選的可能性。

此外，本文算法將GOMP的迭代停止條件改為||rt-rt-1||2/||rt-1||2＜ε或者滿足t＞K，其中t代表迭代次數(shù)的序號(hào)，rt代表第t次迭代后的殘差，K是允許的最大迭代次數(shù)，ε為常數(shù)。也就是說(shuō)，當(dāng)殘差的相對(duì)變化率小于一定數(shù)值時(shí)，認(rèn)為匹配追蹤已經(jīng)完成。該條件增強(qiáng)了算法的自適應(yīng)性，在信號(hào)稀疏度不明確的條件下也能使用該算法。

2.2 算法步驟

GOMP的計(jì)算復(fù)雜度比OMP低，在步長(zhǎng)L不大時(shí)，其重構(gòu)精度甚至略微優(yōu)于OMP，所以顯然更適合應(yīng)用在超寬帶的高速通信中。本文在GOMP的基礎(chǔ)上，針對(duì)算法的不足作出改進(jìn)，使得在算法復(fù)雜度沒(méi)有明顯提高的前提下提高重構(gòu)精度，使算法更具有應(yīng)用價(jià)值。

下面是本文提出算法的具體步驟：

輸入：感知矩陣Θ=ΦΨ，觀測(cè)向量y，每次迭代選取的原子個(gè)數(shù)L，最大迭代次數(shù)K；

（1）初始化：殘差r0=y，已選原子索引集合Λ0=?，已選原子集合A0=?，迭代次數(shù)t=1；

（2）計(jì)算 uj=|〈rt-1,Θj〉|，j∈ {1,2,…N}表示 Θ中各原子（列向量）的序號(hào)和u中各元素的序號(hào)；

（3）按照向量u各元素的值從大到小依次選擇對(duì)應(yīng)序號(hào)的原子。在此過(guò)程中，若某原子與任意已被選中原子的序號(hào)之差的絕對(duì)值小于S，則該原子被舍棄，直到L個(gè)原子被選中，再進(jìn)行下一步；

（4）將這L個(gè)原子對(duì)應(yīng)的序號(hào)構(gòu)成集合J，Λt=Λt∪ J，At=At∪ θJ，θj代表第 j個(gè)原子；

（5）利用最小二乘法計(jì)算被選原子對(duì)應(yīng)的系數(shù) αt=(At)-1y；

（6）更新殘差rt=y-At(At)-1y；

（7）t=t+1，如果||rt-rt-1||2/||rt-1||2＜ε或者滿足t＞K，則進(jìn)行下一步；否則返回第2步繼續(xù)迭代；

（8）根據(jù)被選原子的系數(shù)αt和稀疏矩陣Ψ，可以得到原始信號(hào)x=Ψαt；

輸出：原始信號(hào)x。

3 仿真與分析

本文通過(guò)仿真實(shí)驗(yàn)驗(yàn)證算法的性能。選取原始信號(hào)為IEEE802.15.3a CM1模型下1 024×1的脈沖超寬帶多徑信號(hào)，測(cè)量矩陣為M×1 024的高斯隨機(jī)矩陣，M為觀測(cè)點(diǎn)數(shù)，本文算法中S的取值為3，ε取值為0.1。參照文獻(xiàn)[2]中的評(píng)價(jià)標(biāo)準(zhǔn)：若重構(gòu)誤差小于原始信號(hào)能量的1%，即||y-＜0.01||，則認(rèn)為信號(hào)被成功重構(gòu)。本文采用信號(hào)重構(gòu)成功的概率作為重構(gòu)精度的衡量指標(biāo)。仿真環(huán)境為Intel i5-5200U CPU，8G RAM，Windows 10 64位操作系統(tǒng)，采用Matlab 2016b仿真。

圖1和圖2分別表示迭代步長(zhǎng)L從1變化到15過(guò)程中，GOMP算法和本文算法運(yùn)行時(shí)間和重構(gòu)精度的對(duì)比，其中稀疏字典都采用多徑分集稀疏字典。

圖1 兩種算法運(yùn)行時(shí)間與迭代步長(zhǎng)的關(guān)系

圖2 兩種算法重構(gòu)成功的概率與迭代步長(zhǎng)的關(guān)系

由圖1和圖2可得以下結(jié)論：（1）本文算法與GOMP算法的計(jì)算復(fù)雜度相近，迭代次數(shù)是影響整體計(jì)算復(fù)雜度的最主要因素。相比OMP算法（即GOMP算法L=1時(shí)），GOMP和本文算法在計(jì)算復(fù)雜度上有明顯優(yōu)勢(shì)。（2）當(dāng)隨機(jī)采樣點(diǎn)數(shù)為256時(shí)，本文算法在迭代步長(zhǎng)L=4時(shí)成功重構(gòu)信號(hào)的概率最大，GOMP算法在L=3時(shí)成功重構(gòu)的概率最大。相比于OMP算法和GOMP算法，本文算法在重構(gòu)精度和計(jì)算復(fù)雜度兩個(gè)方面都有一定優(yōu)勢(shì)。（3）當(dāng)?shù)介L(zhǎng)過(guò)大時(shí)，GOMP和本文算法的重構(gòu)精度都會(huì)下降，但顯然本文算法受到的影響更小，所以同等精度要求下，本文算法可以選擇更大的迭代步長(zhǎng)。

表1為觀測(cè)點(diǎn)數(shù)M不同的情況下，不同重構(gòu)算法成功重構(gòu)原始信號(hào)的概率。分別檢測(cè)OMP算法、GOMP算法（L=3、L=6）以及本文算法（L=3、L=6）在稀疏字典為多徑分集字典的情況下成功重構(gòu)的概率。各種情況均重復(fù)10 000次，最后得到如表1所示的統(tǒng)計(jì)結(jié)果。從表1的數(shù)據(jù)中可以看出，當(dāng)要求重構(gòu)成功概率為1時(shí)，OMP和本文算法（L=3）所需的觀測(cè)點(diǎn)數(shù)M最少，但本文算法運(yùn)行時(shí)間約是OMP的1/3。GOMP需要的觀測(cè)點(diǎn)數(shù)最多，不利于降低采樣率，也增加了重構(gòu)所需的時(shí)間，說(shuō)明本文算法相比OMP和GOMP具有更佳的性能。在實(shí)際應(yīng)用中，可以根據(jù)需求選擇合適的步長(zhǎng)，從而在滿足采樣率和重構(gòu)精度要求的前提下節(jié)省算法的運(yùn)行時(shí)間。

表1 不同M取值下各算法重構(gòu)成功的概率

4 結(jié) 語(yǔ)

本文介紹了用于稀疏表示超寬帶信號(hào)的多徑分集字典，分析了CoSaMP、GOMP等算法出現(xiàn)原子誤選的原因，并針對(duì)OMP和GOMP兩種算法在超寬帶應(yīng)用中的不足作出改進(jìn)，限制被選原子之間的序號(hào)差，減少原子誤選的發(fā)生，彌補(bǔ)多徑分集字典的不足，從而選擇更大的迭代步長(zhǎng)。仿真實(shí)驗(yàn)證明，

該算法在運(yùn)行時(shí)間和重構(gòu)精度兩個(gè)方面都獲得了一定改善。

參考文獻(xiàn)：

[1] Donoho D L.Compressed Sensing[J].IEEE Transactions on Information Theory,2012,52(04)：1289-1306.

[2] Paredes J L,Arce G R,Wang Z.Ultra-Wideband Compressed Sensing：Channel Estimation[J].IEEE Journal of Selected Topics in Signal Processing,2007,1(03)：383-395.

[3] Needell D,Tropp J A.CoSaMP：Iterative Signal Recovery from Incomplete and Inaccurate Samples[J].Applied &Computational Harmonic Analysis,2008,26(03)：301-321.

[4] Do T T,Lu G,Nguyen N,et al.Sparsity Adaptive Matching Pursuit Algorithm for Practical Compressed Sensing[C].Signals,Systems and Computers,2009：581-587.

[5] Needell D,Vershynin R.Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit[J].Foundations of Computational Mathematics,2009,9(03)：317-334.

[6] Jian W,Kwon S,Shim B.Generalized Orthogonal Matching Pursuit[J].IEEE Transactions on Signal Proces sing,2012,60(12)：6202-6216.

[7] Pati Y C,Rezaiifar R,Krishnaprasad P S.Orthogonal Matching Pursuit：Recursive Function Approximation with Applications to Wavelet Decomposition[C].Signals,Systems and Computers,2002：40-44.

[8] Donoho D L,Huo X.Uncertainty Principles and Ideal Atomic Decomposition[J].IEEE Transactions on Information Theory,2002,47(07)：2845-2862.

[9] Chen S S,Donoho D L,Saunders M A.Atomic Decomposition by Basis Pursuit[J].Siam Review,2001,43(01)：129-159.

[10] Donoho D L,Tsaig Y,Drori I,et al.Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit[J].IEEE Transactions on Information Theory,2012,58(02)：1094-1121.