一種自適應的弱選擇壓縮采樣匹配追蹤算法

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

一種自適應的弱選擇壓縮采樣匹配追蹤算法

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

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

壓縮感知；重建算法；自適應；弱選擇；壓縮采樣

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

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

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

1　稀疏表示和壓縮感知

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

用一個與稀疏矩陣ψ不相關的M×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范數問題描述：

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

2　自適應的弱選擇壓縮采樣匹配追蹤算法

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

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

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

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

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

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

2.2自適應弱選擇壓縮采樣匹配追蹤算法

算法具體步驟如下：

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

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

現迭代執行如下步驟：

1）利用u=|AT·rt-1|計算相關系數u，將u中2L個最大值對應A的索引值構成集合J0；

2）選擇集合J0中索引值對應原子相關系數大于門限Th= α·max（u）的值，將這些值對應A的索引值構成集合J；

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

4）求y=Aiθi的最小二乘解Ai）-1ATiy。從θ?i中選出絕對值最大的L項記為θ?iL，對應A中的列記為AiL，對應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），否則轉至步驟1）繼續迭代；

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

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

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

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

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

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

3　MATLAB仿真實驗結果對比及分析

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

3.1弱選擇門限參數的限定

α的范圍是0.1～1，每隔0.1取一個值。K的范圍是5～40，每隔5取一個值。現繪制門限參數α取10個測量值時，測量數M與重構成功概率的關系曲線。繪制結果共7幅圖，當K= 25時，測量數M與重構成功概率關系曲線如圖1所示。

圖1　α取不同值時信號重構成功概率與測量數M的關系

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

3.2本文算法單次重構效果

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

圖2　單次重構時本文算法的原始信號和重構信號比較

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

3.3不同算法重構性能對比和分析

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

圖3　稀疏度K=25時重構成功概率與測量數M的關系

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

圖4　測量數M=128時重構成功概率與稀疏度K的關系

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

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

圖5　測量數M=128時平均運行時間關系與稀疏度K的關系

4　結　論

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

［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］高睿，趙瑞珍，胡紹海.基于壓縮感知的變步長自適應匹配追蹤重建算法［J］.光學學報，2010（6）:1639-1644.

【相關參考文獻鏈接】

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

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

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

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

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

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

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

黃業文，楊榮領，鄺神芬.基于貝葉斯決策的自適應p-持續CSMA協議［J］.2016，24（1）:73-76.

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

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

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

樊潤潔.基于全局魯棒滑模PMSM自適應模糊控制［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

微系統技術國防科技重點實驗室基金項目（9140C18010214XXXX）

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