一種自適應(yīng)的弱選擇壓縮采樣匹配追蹤算法

陳秋芳，祖興水，李寶清（1.中國科學院 上海微系統(tǒng)與信息技術(shù)研究所，無線傳感網(wǎng)與通信重點實驗室，上海　201800；2.中國科學院 上海微系統(tǒng)與信息技術(shù)研究所 微系統(tǒng)技術(shù)國防科技重點實驗室，上?！?01800；3.中國科學院大學 北京　100049）

一種自適應(yīng)的弱選擇壓縮采樣匹配追蹤算法

陳秋芳1，3，祖興水1，3，李寶清1，2
（1.中國科學院 上海微系統(tǒng)與信息技術(shù)研究所，無線傳感網(wǎng)與通信重點實驗室，上海201800；2.中國科學院 上海微系統(tǒng)與信息技術(shù)研究所 微系統(tǒng)技術(shù)國防科技重點實驗室，上海201800；3.中國科學院大學 北京100049）

針對實際中未知稀疏度信號的重建問題，提出了一種自適應(yīng)的弱選擇壓縮采樣匹配追蹤算法。該算法將自適應(yīng)思想、弱選擇思想與CoSaMP算法相結(jié)合，在預(yù)選階段后利用限制性弱選擇策略對候選集進行二次篩選，通過雙迭代閾值自適應(yīng)地調(diào)整最終支撐集的原子數(shù)，并結(jié)合若干可靠性驗證條件，保證算法的正確有效進行。MATLAB仿真結(jié)果表明，在相同的實驗條件下，本算法可以有效地重建稀疏信號，同時具有較低的運算量，整體性能較優(yōu)。

壓縮感知；重建算法；自適應(yīng)；弱選擇；壓縮采樣

隨著信息技術(shù)的飛速發(fā)展，人們對信息的需求量與日劇增。然而，傳統(tǒng)的遵循Nyqusit采樣定理的信號采樣方式造成了資源的嚴重浪費。2006年，Candes、Tao等人提出了壓縮感知（Compressed Sensing/Sampling，CS）理論［1-4］，嘗試將信號采樣和數(shù)據(jù)壓縮合二為一。它突破了傳統(tǒng)奈奎斯特采樣定理的限制，降低了信號測量的成本和對硬件設(shè)施的壓力。

壓縮感知的核心問題是采用重建算法從低維的測量樣本中高概率地恢復(fù)出原始的高維數(shù)據(jù)。已經(jīng)提出的信號重建算法包括基追蹤算法（Basis Pursuit，BP）［5］和匹配追蹤算法（Matching Pursuit，MP）［6］等，而 MP及其后續(xù)改進算法因重建復(fù)雜度較低得到了廣泛的應(yīng)用。正交匹配追蹤（Orthogonal Matching Pursuit，OMP）算法［7］每次迭代只得到支撐集的一個原子，效率較低。Needell等人提出了正則化正交匹配追蹤（Regularized Orthogonal Matching Pursuit，ROMP）算法［8］和壓縮采樣匹配追蹤（Compressive Sampling Matching Pursuit，CoSaMP）算法［9］。ROMP利用正則化過程實現(xiàn)原子的快速、有效選擇，重建效率較高。CoSaMP引入了回溯的思想，重建復(fù)雜度較低。以上各算法雖然重構(gòu)速度較快，但都需要信號稀疏度K作為輸入條件，而在實際中K往往是未知的，若K估計不合適會造成重構(gòu)結(jié)果不穩(wěn)定。

分段正交匹配追蹤（Stagewise Orthogonal Matching Pursuit，StOMP）算法［10］、分段弱正交匹配追蹤（Stagewise Weak Matching Pursuit，SWOMP）算法［11］和稀疏度自適應(yīng)匹配追蹤（Sparsity Adaptive Matching Pursuit，SAMP）算法［12］都擺脫了對稀疏度的依賴。

1　稀疏表示和壓縮感知

設(shè)x是大小為N×1的原始信號。現(xiàn)實中我們感興趣的信號一般本身并不稀疏，但在某個變換域是ψ稀疏的，記為稀疏表示模型x=ψθ。其中，ψ是大小為N×N的稀疏矩陣，θ（N× 1）為K稀疏的展開系數(shù)向量，即θ只有K個非零項。

用一個與稀疏矩陣ψ不相關(guān)的M×N維觀測矩陣Φ實現(xiàn)壓縮觀測：y=Φx。其中，y是大小為M×1的觀測向量，一般有K＆lt;＆lt;M＆lt;＆lt;N。此時，y=Φψθ，令傳感矩陣AM×N=Φψ，A的列向量｛aj，j=1，2，…，N｝作為原子，則有：y=Aθ。文中要解決的問題可以用以下最小l0范數(shù)問題描述：

通過式（1）得到原始信號稀疏表示的系數(shù)估計θ?后，根據(jù)式?=ψ?就可以重構(gòu)出x。然而，利用l0范數(shù)求稀疏解屬于NPHard問題，計算復(fù)雜度高。l1范數(shù)求解屬于凸優(yōu)化的線性規(guī)劃問題，因此經(jīng)?？紤]將l0范數(shù)等價為l1范數(shù)求解。文獻［13］表明：當傳感矩陣滿足約束等距特性（Restricted Isometry Property，RIP）條件時，就能通過求解范數(shù)最小化問題精確重構(gòu)稀疏信號x。研究發(fā)現(xiàn)［14］，當M≥cKlog（N/K）（c是一個很小的常數(shù)）時，若以高斯隨機矩陣作為測量矩陣，傳感矩陣A以極大概率滿足RIP性質(zhì)。

2　自適應(yīng)的弱選擇壓縮采樣匹配追蹤算法

2.1正交匹配追蹤及其改進算法

在正交匹配追蹤中，殘差總是與已經(jīng)選擇過的原子正交的，意味著已經(jīng)選擇過的原子不會被選擇兩次，結(jié)果會在有限的幾步收斂。但是，OMP算法每次迭代只選擇與殘差最相關(guān)的一列，重構(gòu)效率非常低，因此研究人員開始提出每次迭代可選擇多個原子的改進算法。

CoSaMP算法每次迭代時先選擇2K個原子作為初始候選集，然后合并當前支撐集中的K個原子組成最終候選集，之后利用回溯思想按照一定規(guī)則逐步剔除候選集中的部分原子，最終保留最匹配的K個原子用于信號重構(gòu)。從以上過程看出，必須適當估計信號稀疏度K才能進一步精確重建信號。此外，固定數(shù)目的原子選擇方式也未能充分體現(xiàn)不同迭代殘差與觀測矩陣中各原子相關(guān)性的差異，在篩選中必定會造成預(yù)選浪費，影響算法的重構(gòu)精度。

SWOMP算法引入了原子的弱選擇標準，門限設(shè)置為：Th=α·max（u），α是門限參數(shù)。將相關(guān)系數(shù)不小于Th的原子的索引值并入候選集中，則完成了一次原子的弱選擇。弱選擇標準使算法重構(gòu)效果不受稀疏度的影響，并能更靈活地挑選原子，提升重構(gòu)效果和穩(wěn)定性。

SAMP算法也不需要知道信號的稀疏度K。該算法將同一個迭代過程分成多個階段，通過轉(zhuǎn)換階段不斷增加支撐集的大小從而逐漸逼近信號實際稀疏度K，直至滿足迭代終止條件。該算法具有較高的重構(gòu)概率，缺點是分階段迭代造成了重構(gòu)時間較長。算法需要選取合適的初始步長，本文算法和SAMP算法相同，采用式（2）來設(shè)定初始步長［15］：

綜上所述，采用回溯思想的CoSaMP算法雖然重構(gòu)效率高，但需要以稀疏度作為先驗信息，原子選取方式不靈活，重構(gòu)精度不太高。據(jù)此，引入SWOMP算法的弱選擇原則和SAMP算法的自適應(yīng)思想可以克服CoSaMP算法的以上缺點。改進算法不需要信號的稀疏度先驗信息，可以根據(jù)弱選擇方法和自適應(yīng)過程自動調(diào)整所選原子數(shù)來重建未知稀疏度的信號。

2.2自適應(yīng)弱選擇壓縮采樣匹配追蹤算法

算法具體步驟如下：

輸入：觀測向量y，傳感矩陣A，門限參數(shù)α

初始化：迭代次數(shù)i=1，殘差r0=y，步長s=M/［1lb（N）］，階段stage=1，則初始支撐集大小L=s，算法的最大迭代次數(shù)取為測量數(shù)M，支撐集Λ0為空集。

現(xiàn)迭代執(zhí)行如下步驟：

1）利用u=|AT·rt-1|計算相關(guān)系數(shù)u，將u中2L個最大值對應(yīng)A的索引值構(gòu)成集合J0；

2）選擇集合J0中索引值對應(yīng)原子相關(guān)系數(shù)大于門限Th= α·max（u）的值，將這些值對應(yīng)A的索引值構(gòu)成集合J；

3）合并索引集合，令C=Λi-1∪J，Ai=Ai-1∪aj（for all j∈J）；

4）求y=Aiθi的最小二乘解Ai）-1ATiy。從θ?i中選出絕對值最大的L項記為θ?iL，對應(yīng)A中的列記為AiL，對應(yīng)A的索引值記為F；

5）更新殘差rnew=y-AiL（ATiLAiL）-1ATiLy；

6）如果殘差rnew＆lt;ε1則令Λi=F，并停止迭代進入步驟7）；如果‖rnew-ri-1‖≤ε2，更新階段stage=stage+1，更新步長L=s· stage，返回步驟1）；若前面兩個條件都不滿足，則令Λi=F，ri= rnew，i=i+1，如果i＞M則停止迭代進入步驟7），否則轉(zhuǎn)至步驟1）繼續(xù)迭代；

對于以上算法步驟，有兩點需要詳細說明：

①在步驟2）侯選集的二次篩選中，SWOMP中門限參數(shù)α的取值范圍一般為0＆lt;α≤1，本文算法采用限制性弱選擇策略，只取的較優(yōu)值，選擇過程見下文MATLAB仿真實驗。

②步驟6）中，ε1是控制迭代次數(shù)的閾值，ε2是控制階段轉(zhuǎn)換的閾值，雙閾值可以保證算法具有較好的重建精度。當殘差能量小于ε1時停止迭代。根據(jù)經(jīng)驗，ε1選擇為1e-6。當時，表示沒有新的原子被加入支撐集，說明L需要更新以滿足重建要求。

為了使算法能夠正確有效地進行，文中還加入了兩個可靠性驗證條件，簡述如下：

①步驟4）中求最小二乘解時，必須滿足矩陣Ai的行數(shù)大于列數(shù)，即是列滿秩矩陣，否則將不可逆。因此，當行數(shù)小于列數(shù)時，提前結(jié)束循環(huán)，并給賦值為0。

②因為采用了弱選擇過程對原子進行二次篩選，因此索引集C的大小可能小于L，此時步驟4）中直接令F=C即可。

3　MATLAB仿真實驗結(jié)果對比及分析

為了驗證本文算法的重構(gòu)性能，通過MATALB處理平臺進行性能測試，并與已有的OMP、CoSaMP、SWOMP和SAMP算法進行對比分析，處理器是Intel Core i5-4300U。實驗中選用一維高斯隨機矩陣作為測量矩陣，單位矩陣作為稀疏矩陣，原始信號長度。

3.1弱選擇門限參數(shù)的限定

α的范圍是0.1～1，每隔0.1取一個值。K的范圍是5～40，每隔5取一個值?，F(xiàn)繪制門限參數(shù)α取10個測量值時，測量數(shù)M與重構(gòu)成功概率的關(guān)系曲線。繪制結(jié)果共7幅圖，當K= 25時，測量數(shù)M與重構(gòu)成功概率關(guān)系曲線如圖1所示。

圖1　α取不同值時信號重構(gòu)成功概率與測量數(shù)M的關(guān)系

從圖1可以看出，選擇不同的參量重構(gòu)效果存在一定的差異。總體上講取0.4，0.5，0.6時效果較好。觀察K取其他值時另外6幅圖，可得到相同的結(jié)論。因此，本文算法的輸入?yún)?shù)α的取值范圍限制為0.4，0.5，0.6。后文沒有特別說明時，α默認取為0.5。

3.2本文算法單次重構(gòu)效果

取測量數(shù)M=128，稀疏度K=25，某次運行結(jié)果如圖2所示。

圖2　單次重構(gòu)時本文算法的原始信號和重構(gòu)信號比較

可以看出，本文算法對一維原始信號的重建效果很好，重構(gòu)誤差較小，在量級。

3.3不同算法重構(gòu)性能對比和分析

圖3給出了當稀疏度K=25時，測量數(shù)M與重構(gòu)成功概率關(guān)系曲線。信號重構(gòu)成功是指重構(gòu)信號與原始信號的誤差的絕對值小于某一閾值，在此取為1e-6。由圖可以看出，信號重構(gòu)成功概率隨著測量次數(shù)M的增大而增大。當M較小時5種算法重建效果都比較差，但是隨著壓縮比的不斷增加，本文算法的重構(gòu)成功概率相對OMP、CoSaMP和SWOMP算法提高很多，并略高于SAMP算法，本文算法和SAMP算法能穩(wěn)定重建信號所需的采樣點數(shù)均較少。該圖說明了在稀疏度相同時，本文算法具有較優(yōu)的重構(gòu)概率。

圖3　稀疏度K=25時重構(gòu)成功概率與測量數(shù)M的關(guān)系

圖4給出了當測量數(shù)M=128時，稀疏度K與重構(gòu)成功概率關(guān)系曲線。由圖可以看出，信號重構(gòu)成功概率隨著稀疏度K的增大而減小，并且本文算法遠優(yōu)于OMP、CoSaMP和SWOMP算法，在稀疏度較大時依然能精確重構(gòu)信號，具有最佳的重構(gòu)概率，而SAMP算法重構(gòu)概率整體略低于本文算法。該圖說明了在壓縮比相同時，本文算法具有較優(yōu)的重構(gòu)概率。

圖4　測量數(shù)M=128時重構(gòu)成功概率與稀疏度K的關(guān)系

圖5給出了當測量數(shù)M=128時，稀疏度K與運行時間關(guān)系曲線。本文算法因為迭代次數(shù)增加而導(dǎo)致運算時間整體略超過CoSaMP和SWOMP算法，但遠小于OMP和SAMP算法。該圖說明了在壓縮比相同時本文算法具有比較少的重構(gòu)時間。

通過以上各實驗結(jié)果，綜合各種算法的優(yōu)劣勢對比結(jié)果可知，本文所提出的算法是一種具有精確重構(gòu)性能且重建復(fù)雜度較低的算法。

圖5　測量數(shù)M=128時平均運行時間關(guān)系與稀疏度K的關(guān)系

4　結(jié)　論

本文在分析和總結(jié)已有壓縮感知重建算法特點的基礎(chǔ)上，提出了一種自適應(yīng)的弱選擇壓縮采樣匹配追蹤算法。該算法同時結(jié)合了SAMP算法重構(gòu)概率高、SWOMP算法不需要輸入稀疏度且原子選擇方式靈活和CoSaMP算法重構(gòu)復(fù)雜度低的優(yōu)點。仿真結(jié)果表明，在相同條件下，本文算法的重構(gòu)效果優(yōu)于OMP、SWOMP和CoSaMP算法，略優(yōu)于SAMP算法，且其重構(gòu)復(fù)雜度較低，且遠低于SAMP算法，說明本文算法是一種重建質(zhì)量較優(yōu)的壓縮感知重建算法，具有較高的實用性。

［1］Candes E J，Tao T.Decoding by linear programming［J］.IEEE Transactions on Information Theory，2005，51（12）:4203-4215.

［2］Donoho D L.Compressed sensing［J］.IEEE Transactions on Information Theory，2006，52（4）:1289-1306.

［3］Candes E J，Tao T.Near-optimal signal recovery from random projections:universal encoding strategies［J］.IEEE Transactions on Information Theory，2006，52（12）:5406-5425.

［4］Candes E J，Romberg J，Tao T.Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information［J］.IEEE Transactions on Information Theory，2006，52（2）:489-509.

［5］Chen S S，Donoho D L，Saunders M A.Atomic decomposition by basis pursuit［J］.SIAM journal on Scientific Computing，1998，20（1）:33-61.

［6］Mallat S G，Zhang Z.Matching pursuits with time-frequency dictionaries［J］.IEEE Transactions on Signal Processing，1993，41（12）:3397-3415.

［7］Tropp J，Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit［J］.IEEE Transactions on Information Theory，2007，53（12）:4655-4666.

［8］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.

［9］Needell D，Tropp J A.CoSaMP:Iterative signal recovery from incomplete and inaccurate samples［J］.Applied and Computational Harmonic Analysis，2009，26（3）:301-321.

［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（2）:1094-1121.

［11］Blumensath T，Davies M E.Stagewise weak gradient pursuits ［J］.IEEE Transactions on Signal Processing，2009，57（11）: 4333-4346.

［12］Do T T，Gan L，Nguyen N，et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing［C］.2008 42ndAsilomarConferenceonSignals，Systemsand Computers，2008:581-587.

［13］Candes E J，Romberg J，Tao T.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information［J］.IEEE Transactions on Information Theory，2006，52（2）:489-509.

［14］Baraniuk R G.Compressive sensing［J］.IEEE signal processing magazine，2007，24（4）:118-121.

［15］高睿，趙瑞珍，胡紹海.基于壓縮感知的變步長自適應(yīng)匹配追蹤重建算法［J］.光學學報，2010（6）:1639-1644.

【相關(guān)參考文獻鏈接】

高鍵，張凱.基于云模型自適應(yīng)算法的船舶航向控制［J］.2015，23 （10）:36-38.

朱艷，李建禎.基于自適應(yīng)混沌粒子群算法的推力分配研究［J］. 2015，23（13）:75-78.

席東河，王林生，劉明黎，等.基于ATT7037AU的新型自適應(yīng)智能用電控制終端設(shè)計［J］.2015，23（13）:82-85.

熊淦輝，黎沛堅，徐俊林，等.基于自適應(yīng)匹配模型的停電管理系統(tǒng)設(shè)計與應(yīng)用［J］.2015，23（16）:160-163.

王坤.互動多媒體圖片自適應(yīng)大小的研究與實現(xiàn)［J］.2015，23 （18）:69-71.

荊海霞，李洪義.基于主動時間反轉(zhuǎn)的水下目標自適應(yīng)聚焦研究［J］.2015，23（24）:179-182.

朱宗明，姜占才.小波遞歸最小二乘語音自適應(yīng)增強［J］.2016，24（1）:69-72.

黃業(yè)文，楊榮領(lǐng)，鄺神芬.基于貝葉斯決策的自適應(yīng)p-持續(xù)CSMA協(xié)議［J］.2016，24（1）:73-76.

郭璐，黃鶴，杜凱，黃鶯，等.DSP環(huán)境下新的變步長LMS自適應(yīng)濾波算法［J］.2016，24（1）:135-137.

劉桂辛.改進的自適應(yīng)卡爾曼濾波算法［J］.2016，24（2）:48-51.

鄭建英，于占東.磁懸浮球系統(tǒng)的自適應(yīng)反演滑模控制［J］. 2016，24（2）:76-78.

樊潤潔.基于全局魯棒滑模PMSM自適應(yīng)模糊控制［J］.2016，24 （4）:84-86.

An adaptive weak-selection compressive sampling pursuit algorithm

CHEN Qiu-fang1，3，ZU Xing-shui1，3，LI Bao-qing1，2
（1.Key Laboratory of Wireless Sensor Networks and Communication，Shanghai Institute of Microsystem and Information Technology，CAS，Shanghai 201800，China；2.Key Laboratory of National Defense for Science and Technology on Microsystem，Shanghai Institute of Microsystem and Information Technology，CAS，Shanghai 201800，China 3.University of Chinese Academy of Sciences，Beijing 100049，China）

This paper proposed an adaptive weak-selection compressive sampling pursuit algorithm to reconstruct signals with unknown sparsity in practice.The algorithm combines adaptive idea and weak-selection idea with the CoSaMP algorithm.It adopts limited weak-selection strategy to realize the second selecting of the atoms in the candidate set after the pre-selection stage，and then adaptively adjust the number of atoms in the final support set through double-threshold.We also incorporate some reliability demonstration conditions to the algorithm to ensure the correctness and effectiveness.The simulation results on MATLAB show that our algorithm can get better reconstruction performances and can run fast under the same conditions，which has a better overall performance.

compressed sensing；reconstruction algorithms；adaptive；weak selection；compressive sampling

TN914.3

A

1674－6236（2016）11-0150-04

2015-12-31稿件編號：201512325

微系統(tǒng)技術(shù)國防科技重點實驗室基金項目（9140C18010214XXXX）

陳秋芳（1990—），女，河南商丘人，碩士。研究方向：壓縮感知和稀疏表示。