李雪晴 丁佳靜 武雪姣

摘? 要：在基于壓縮感知的信號(hào)重構(gòu)問題中，有一類常見情況——未知信號(hào)稀疏度。針對(duì)此類情況，提出稀疏度自適應(yīng)分段正交匹配追蹤（Sparsity Adaptive Stagewise Orthogonal Matching Pursuit，SAStOMP）算法，該算法將自適應(yīng)思想、變步長迭代思想與分段正交思想相結(jié)合，在未知信號(hào)稀疏度的情況下，自適應(yīng)地選擇支撐集原子的個(gè)數(shù)，最終實(shí)現(xiàn)信號(hào)的精確重構(gòu)。仿真結(jié)果表明，針對(duì)長度為256位的原始信號(hào)，該算法重建效果優(yōu)于正交匹配追蹤算法、正則化正交匹配追蹤算法和分段正交匹配追蹤算法等。

關(guān)鍵詞：壓縮感知;信號(hào)重建算法;稀疏度自適應(yīng);分段正交匹配追蹤

中圖分類號(hào)：TP391? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：Aiming at the reconstruction of unknown signal sparsity in compressed sensing，this paper proposes a new compression sensing signal reconstruction algorithm of SAStOMP （Sparsity Adaptive Stagewise Orthogonal Matching Pursuit）.The algorithm combines the ideas of self-adaptation，variable step size iteration and piecewise orthogonal design，in the case of unknown signal sparsity，selects adaptively the number of atoms of the support set ，finally realizes the accurate reconstruction of signals.Simulation results show that the proposed algorithm is superior to OMP，ROMP and StOMP for the original signals of 256 digits.

Keywords：compressed sensing;signal reconstruction algorithm;sparsity adaptive;stagewise orthogonal matching pursuit

1? ?引言（Introduction）

壓縮感知（Compressed Sensing，CS）技術(shù)之所以能夠利用較低維度的觀測(cè)值去重構(gòu)較高維度的信號(hào)，在于充分利用了信號(hào)的稀疏性和可壓縮性[1]。研究CS理論，主要側(cè)重于三方面：信號(hào)的稀疏表示、觀測(cè)矩陣的設(shè)計(jì)，以及信號(hào)的重建算法。其中，信號(hào)重建算法是決定信號(hào)是否可以準(zhǔn)確重構(gòu)的關(guān)鍵步驟，其目的在于利用觀測(cè)值去高精度地重構(gòu)真實(shí)值，當(dāng)然觀測(cè)值的維度遠(yuǎn)遠(yuǎn)小于真實(shí)值。信號(hào)重構(gòu)算法主要包括以下三類：組合優(yōu)化類、凸優(yōu)化類和貪婪迭代類[2]。貪婪迭代類算法往往運(yùn)行速度較快，算法流程清晰?，F(xiàn)有的貪婪迭代算法有匹配追蹤（Matching Pursuit，MP）[3]、正交匹配追蹤（Orthogonal Matching Pursuit，OMP）[4]、分段正交匹配追蹤（Stagewise Orthogonal Matching Pursuit，StOMP）[5]、正則化正交匹配追蹤（Regularized Orthogonal Matching Pursuit，ROMP）[6]、壓縮采樣匹配追蹤（Compressive Sampling Matching Pursuit，CoSaMP）[7]和子空間追蹤（Subspace Pursuit，SP）[8]。但是，貪婪迭代算法對(duì)待重構(gòu)信號(hào)都有一個(gè)要求——稀疏度確定且已知，但事實(shí)上，真正的實(shí)際應(yīng)用中，稀疏度通常不是先驗(yàn)知識(shí)[9]。針對(duì)以上問題，本文在StOMP框架下，結(jié)合SAMP中稀疏度自適應(yīng)的特點(diǎn)[10]，提出稀疏度自適應(yīng)分段正交匹配追蹤算法（SAStOMP），該算法主要用于稀疏度未知情況下的信號(hào)重構(gòu)。

2? ?壓縮感知理論（Compressed sensing）

在對(duì)信號(hào)進(jìn)行重建時(shí)，能否運(yùn)用壓縮感知理論在于確定該信號(hào)是否具有稀疏性，我們知道，每個(gè)一維信號(hào)，都可以用N×1維基向量線性表示。為了簡化問題，假設(shè)基向量為規(guī)范正交向量，使用N×N的基矩陣，信號(hào)x可以被表示為：

在該式中：S是投影系數(shù)構(gòu)成的N×1維列向量。X是在時(shí)域或空間域的表示，Ψ為N×N維變換基，S是在Ψ域的表示。當(dāng)信號(hào)可以僅被K個(gè)基向量線性表示時(shí)，則稱信號(hào)x為K-稀疏。作為壓縮感知理論的前提，稀疏性是實(shí)際很多信號(hào)不具有的，不能運(yùn)用壓縮感知理論進(jìn)行壓縮采樣，這會(huì)限制壓縮感知的發(fā)展。為了讓信號(hào)都具有這一性質(zhì)，先對(duì)信號(hào)進(jìn)行某種變換，使其具有稀疏性，之后就可對(duì)信號(hào)進(jìn)行采樣壓縮和信號(hào)重構(gòu)。設(shè)計(jì)一個(gè)與變換基不相關(guān)的觀測(cè)矩陣Φ，注意該矩陣的維度為M×N（M

上式中的Θ是恢復(fù)矩陣，維度為M×N。觀測(cè)矩陣Φ為已知矩陣，本文中分別取高斯隨機(jī)矩陣、伯努利矩陣、部分傅里葉矩陣為參考進(jìn)行實(shí)驗(yàn)分析。

3 稀疏度自適應(yīng)分段正交匹配追蹤算法（Algorithm for sparsity adaptive stagewise orthogonal matching pursuit）

正交匹配追蹤算法是壓縮感知理論中較為經(jīng)典的算法，算法簡單，重構(gòu)效果尚可，但是這種算法每次只從觀測(cè)矩陣中選取1個(gè)最佳原子，即選取殘差最小的原子加入集合，這種算法重構(gòu)準(zhǔn)確度的增加是以犧牲迭代次數(shù)為代價(jià)的，當(dāng)信號(hào)量激增時(shí)，整個(gè)重構(gòu)的效率顯然會(huì)大大降低。接下來介紹StOMP算法，與OMP算法不同，StOMP算法在每次迭代中會(huì)選出多個(gè)原子，選取原子的個(gè)數(shù)是由提前設(shè)定的閾值決定的，之后在每次迭代中更新原子集合，最終找到最優(yōu)解。顯然，StOMP算法的重構(gòu)效率要比OMP算法高得多，下面介紹StOMP算法的流程與步驟[11]：

（1）初始?xì)埐?，?jì)數(shù)器s=1。

（2）計(jì)算內(nèi)積 。?

（3）可以通過設(shè)定軟閾值來產(chǎn)生相應(yīng)集合，其中：為噪聲水平，為;θ為閾值參數(shù)，取值范圍為[2，3]。

（4）更新支撐集：，并利用最小二乘法計(jì)算支撐集上的逼近系數(shù)向量，。

（5）更新殘差（余量）。

（6）檢查終止條件：若s>10或者，（其中為誤差容限），算法終止并將作為最終輸出。否則，執(zhí)行并轉(zhuǎn)到步驟（2） 。

StOMP算法每次迭代選取多個(gè)原子，大大提高了重構(gòu)的效率，但該算法也存在以下不足之處：

（1）因?yàn)镾tOMP算法在每次迭代過程中，選擇的是根據(jù)閾值劃分出的原子集合，而不是最優(yōu)原子，所以與OMP算法相比較，準(zhǔn)確度大大降低。

（2）在上文中已經(jīng)提到，選取原子的個(gè)數(shù)是由提前設(shè)定的閾值決定的，在實(shí)際應(yīng)用中，閾值往往不太容易確定。

（3）無論是OMP算法還是StOMP算法，都需要確定待重構(gòu)信號(hào)的稀疏性，但在實(shí)際的應(yīng)用中，不同來源的信號(hào)的稀疏度往往是未知的且很難確定。

考慮到OMP算法和StOMP算法的優(yōu)缺點(diǎn)，本文結(jié)合SAMP算法[12]的自適應(yīng)思想，提出一種改進(jìn)的稀疏度自適應(yīng)的壓縮感知算法。改進(jìn)的算法無須明確待重構(gòu)信號(hào)的稀疏度，而是在迭代過程中一步步去逼近真實(shí)的稀疏度K，最終實(shí)現(xiàn)信號(hào)重構(gòu)。算法流程如下[12，13]：

輸入：M×N的傳感矩陣A=ΦΨ;N×1維觀測(cè)向量y;迭代次數(shù)S，默認(rèn)為10;門限參數(shù)ts，默認(rèn)為2.5;步長ST。

輸出：信號(hào)稀疏表示系數(shù)估計(jì);殘差。

（1）初始化：，，，，。

（2）計(jì)算（即計(jì)算，1≤j≤N），選擇u中L個(gè)最大值，將這些值對(duì)應(yīng)A的列序號(hào)j構(gòu)成集合（列序號(hào)集合），選擇u中大于門限的值，將這些值對(duì)應(yīng)A的列序號(hào)j構(gòu)成集合（列序號(hào)集合）。

（3）令，;若（即無新列被選中），則停止迭代進(jìn)入第（8）步。

（4）求的最小二乘解：。

（5）從中選出絕對(duì)值最大的L項(xiàng)記為，對(duì)應(yīng)的的L列記為，對(duì)應(yīng)的A的列序號(hào)記為，記集合。

（6）更新上一步驟所得殘差，使得。

（7）如果則停止迭代進(jìn)入第（8）步;如果，則更新步長L=L+ST，返回第（2）步繼續(xù)進(jìn)行迭代;否則，如果t≤S停止迭代進(jìn)入第（8）步，否則返回第（2）步繼續(xù)迭代。

（8）重構(gòu)所得在處有非零項(xiàng)，其值分別為最后一次迭代所得。

綜上，SAStOMP算法將分階段正交化思想，以及自適應(yīng)思想相結(jié)合，在提高重構(gòu)效率的同時(shí)保證了信號(hào)重構(gòu)的準(zhǔn)確度。

4 實(shí)驗(yàn)結(jié)果及分析（Experimental results and analysis）

為了檢驗(yàn)本文算法的正確性和有效性，將本文改進(jìn)的算法與OMP算法、ROMP算法，以及StOMP算法進(jìn)行比較。本文涉及的實(shí)驗(yàn)在華碩Y481C筆記本（4GB DDR3內(nèi)存，i7-3573）上，通過MATLAB R2014a仿真完成。當(dāng)觀測(cè)矩陣為高斯隨機(jī)矩陣、伯努利矩陣和部分傅立葉矩陣時(shí)，信號(hào)準(zhǔn)確重建概率分別如圖1、圖2、圖3所示。

從圖1可以看出，當(dāng)信號(hào)長度為256位，觀測(cè)值集合為128位，觀測(cè)矩陣為高斯矩陣時(shí)，改進(jìn)的SAStOMP算法明顯優(yōu)于OMP算法、ROMP算法、StOMP算法。當(dāng)稀疏度接近45時(shí)，OMP算法和StOMP算法信號(hào)準(zhǔn)確重構(gòu)的概率急劇下降，改進(jìn)的SAStOMP算法仍能100%精確重構(gòu)信號(hào)。當(dāng)稀疏度接近55時(shí)，OMP算法和StOMP算法幾乎不能重構(gòu)信號(hào)，而改進(jìn)的SAStOMP算法性能良好，準(zhǔn)確重構(gòu)信號(hào)的概率接近65%。

從圖2可以看出，當(dāng)信號(hào)長度為256位，觀測(cè)值集合為128位，觀測(cè)矩陣為伯努利矩陣時(shí)，改進(jìn)的SAStOMP算法依然明顯優(yōu)于OMP算法、ROMP算法、StOMP算法。隨著稀疏度不斷增加，信號(hào)精確重構(gòu)概率基本趨勢(shì)與觀測(cè)矩陣為高斯矩陣的情況相同。

從圖3可以看出，當(dāng)信號(hào)長度為256位，觀測(cè)值集合為128位，觀測(cè)矩陣為傅立葉矩陣時(shí)，改進(jìn)的SAStOMP算法僅次于經(jīng)典的OMP算法，明顯優(yōu)于ROMP算法和StOMP算法。

經(jīng)過仿真實(shí)驗(yàn)和上述實(shí)驗(yàn)結(jié)果分析，綜合來說，本文提出的算法不需要信號(hào)稀疏度作為先驗(yàn)知識(shí)，表現(xiàn)出的性能整體優(yōu)于經(jīng)典的OMP算法、ROMP算法和StOMP算法，具有良好的實(shí)用價(jià)值。

5? ?結(jié)論（Conclusion）

本文提出了SAStOMP算法，該算法不需要稀疏度K作為先驗(yàn)知識(shí)，彌補(bǔ)了貪婪迭代類算法的最大不足。MATLAB實(shí)驗(yàn)仿真結(jié)果表明，改進(jìn)的SAStOMP算法優(yōu)于OMP、ROMP和StOMP算法，提高了信號(hào)稀疏度較大時(shí)重構(gòu)信號(hào)的準(zhǔn)確度。

參考文獻(xiàn)（References）

[1] Zhou C，Gu Y，Zhang Y D，et al.Compressive sensing-based coprime array direction-of-arrival estimation[J].Iet Communications，2017，11（11）：1719-1724.

[2] 唐朝偉，王雪鋒，杜永光.一種稀疏度自適應(yīng)分段正交匹配追蹤算法[J].中南大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，47（3）：784-792.

[3] Chen C H，Tsai C R，Liu Y H，et al.Compressive Sensing （CS） Assisted Low-Complexity Beamspace Hybrid Precoding for Millimeter-Wave MIMO Systems[J].IEEE Transactions on Signal Processing，2017，65（6）：1412-1424.

[4] Nouasria H，Et-Tolba M.Sensing matrix based on Kasami codes for compressive sensing[J].IET Signal Processing，2018，12（8）：1064-1072.

[5] 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（2）：1094-1121.

[6] Needell D，Vershynin R.Signal Recovery From Incomplete and Inaccurate Measurements Via Regularized Orthogonal Matching Pursuit[J].IEEE Journal of Selected Topics in Signal Processing，2010，4（2）：310-316.

[7] Needell D，Tropp J A.Tropp，J.A.：CoSaMP：iterative signal recovery from incomplete and inaccurate samples[J].Applied & Computational Harmonic Analysis，2008，26（3）：301-321.

[8] Dai W，Milenkovic O.Subspace Pursuit for Compressive Sensing Signal Reconstruction[J].IEEE Transactions on Information Theory，2009，55（5）：2230-2249.

[9] 吳迪，王奎民，趙玉新，等.分段正則化正交匹配追蹤算法[J].光學(xué)精密工程，2014，22（5）：1395-1402.

[10] sfs DO T T，GAN L，NGUYEN N，et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C].Proceedings of the Asilomar Conference on Signals，Systems and Computers.Pacific Grove，CA：IEEE Computer Society，2008：581-587.

[11] onoho D L，Tsaig Y，DroriI，Starck J L.Sparsesolution of underdetermined linear equations by stagewise orthogonal matchingpursuit[J].IEEE Transactions on InformationTheory，2012，58（2）：1094-1121.

[12] Thong T.Do，Lu Gan，NamNguyen，et al.Sparsityadaptive matching pursuit algorithm for practical compressed sensing[C].AsilomarConference on Signals，Systems，andComputers，Pacific Grove，California，2008，10：581-587.

[13] 楊成，馮巍，馮輝，等.一種壓縮采樣中的稀疏度自適應(yīng)子空間追蹤算法[J].電子學(xué)報(bào)，2010，38（8）：1914-1917.