基于壓縮感知和分段正交匹配追蹤StOMP算法的優化

黃 同，李娣娜，邵思飛，2

（1.延安大學 西安創新學院，陜西 西安710100；2.延安大學 物理與電子信息學院，陜西 延安 716000）

基于壓縮感知和分段正交匹配追蹤StOMP算法的優化

黃 同1，李娣娜1，邵思飛1，2

（1.延安大學 西安創新學院，陜西 西安710100；2.延安大學 物理與電子信息學院，陜西 延安 716000）

在分析分段正交匹配追蹤StOMP算法迭代過程中多原子匹配方法的基礎上，為了進一步減少算法迭代次數，提高重構精度，提出了基于互相關向量的自適應極限因子選取和迭代結束條件重設的優化方法。通過MATLAB編程實驗，在隨機給定稀疏度為K的測試數據條件下，優化后的算法較StOMP算法迭代次數減少1-2次，重構精度提升約1%，魯棒性增加，而運行時間開銷相差無幾。

壓縮感知；正交匹配追蹤算法；分段正交匹配追蹤算法；StOMP

在基于奈奎斯特采樣定理的傳統信號處理體系中，信號必須首先采樣，然后進行壓縮等后續處理。采樣數據往往非常龐大，但大量數據相關性很高，造成資源的極大浪費。壓縮感知（Compressed Sensing,CS）理論指出，如果信號是稀疏的或者在某個基下可稀疏化，那么用少量的觀測值就可以保持信號的結構和相關信息，這樣用于精確重構信號的采樣數量可以極大降低，相當于壓縮和采樣同步完成。正交匹配追蹤算法（Orthogonal Matching Pursuit algorithm,OMP）作為重構算法之一，因計算復雜度低，重建速度快得到了廣泛應用，但信號重建質量有待提高，為此，人們提出了很多改進算法，文中在分段正交匹配追蹤算法（Segmented Orthogonal Matching Pursuit algorithm,StOMP）的基礎上通過實驗，提出進一步的改進思路。

1　壓縮感知理論

壓縮感知基于信號的稀疏性，以遠低于奈奎斯特采樣率的速率對信號進行非自適應的測量采集。稀疏分解、隨機測量和重構算法是壓縮感知的3個關鍵［1］，稀疏分解和隨機測量屬于信號的壓縮，重構算法是它的逆過程，相當于解壓縮，與稀疏分解方法和隨機測量矩陣直接相關。

信號的在稀疏基Ψ上的稀疏分解是壓縮感知應用的基礎，除了離散余弦變換、離散傅里葉變換、離散小波變換等經典的稀疏化方法外，冗余字典下的稀疏分解逐漸成為新的熱點。冗余字典是過完備的，字典中的冗余函數稱為原子，它用原子取代了基函數。

測量矩陣Φ′（M×N M＜N）是隨機測量的關鍵，既直接影響正向壓縮，也影響反向重構。在將原非稀疏信號X（N×1）進行稀疏分解，得到稀疏系數X′（N×1）后，需要通過矩陣乘法的形式采樣得到M個觀測值Y，并保證能重構出稀疏基Ψ下等價的稀疏系數向量X′或者長度為N的信號X。鑒于此，測量矩陣的構造必須遵循一定的法則，具備一定的特性。Candès提出的約束等距性（Restricted Isometry Property,RIP）指出，要想使信號完全重構，必須保證測量矩陣不會把兩個不同的稀疏度為K的信號映射到同一個采樣集合中［2］。Donoho也從定性和定量的角度給出測量矩陣要滿足3個特性［3］：1）由測量矩陣的列向量組成的子矩陣的最小奇異值必須大于一定的常數；2）測量矩陣的列向量體現某種類似噪聲的獨立隨機性；3）滿足稀疏度的解是滿足1范數最小的向量。目前，常用的測量矩陣主要有高斯隨機矩陣、伯努利矩陣、傅立葉隨機矩陣、哈達瑪矩陣和一致球矩陣等。

重構算法是恢復原始信號的必需過程。從數學上講，信號重建問題就是尋找欠定方程組的最簡單解的問題，目前壓縮感知的重構算法主要包括貪婪算法和凸優化算法兩大類。貪婪算法［4］主要包括匹配追蹤算法、正交匹配追蹤算法、分段正交匹配追蹤算法、補空間匹配追蹤算法等，它們的本質是通過反復的遞歸過程，實現信號的最佳逼近。凸優化算法［5］主要包括梯度投影法、基追蹤法、最小角度回歸法等,它們的本質是把0范數放寬到1范數通過線性規劃求解。貪婪算法計算復雜度低，重建速度快，但是信號重建質量有待提高；凸優化算法信號重建質量較高，但是計算復雜度高，重建速度慢。

2　分段正交匹配追蹤算法及其優化

2.1正交匹配追蹤算法OMP

正交匹配追蹤算法和匹配追蹤算法 （Matching Pursuit algorithm,MP）總體類似，它是在每一次的迭代過程中，從冗余字典（即感知矩陣Φ）里選擇與信號最匹配的原子（列）,經過Gram-Schmidt正交化后，再將信號在這些正交原子構成的空間上投影，得到信號在各個已選原子上的分量和余量，然后采用相同方法，經過數次迭代選出與信號各次余量最為匹配的原子，所選原子均需要滿足一定條件，余量隨著分解過程迅速減小直至迭代結束［6］。由于遞歸過程中對己選原子集進行了正交化，保證了迭代的最優性，相比匹配追蹤算法，減少迭代次數，收斂效果更好。

正交匹配追蹤算法以貪婪迭代的方法選擇Φ的列，使得在每次迭代中所選擇的列與當前的冗余向量最大程度地相關，從測量向量中減去相關部分并反復迭代，直到迭代次數達到稀疏度K，迭代停止。

2.2分段正交匹配追蹤StOMP算法及其優化

正交匹配追蹤方法利用Gram-Schmidt正交化過程將投影方向正交化，從而提高了追蹤的效率，但是其正交化過程引入了新的計算開銷，特別是對于圖像信號，計算量仍然巨大。2006年Donoho進一步提出了每次匹配追蹤時選出的是多個匹配原子而不是單個原子的分段正交匹配追蹤算法［7］，該算法將OMP算法進行一定程度的簡化，降低了稀疏分解精度，提高了計算速度。

設Φ=｛gr｝r∈Θ是由Θ個（Θ＞N）范數為1的向量構成的冗余字典。該字典包含N個線性無關的向量，這N個向量構成長度為N的信號空間CN的一個基。設f為待處理信號，m為第次迭代（即當前迭代次數），為余量，為極限因子。初始時m=0，下標集合Im=I0=φ。

分段正交匹配追蹤算法的單次迭代過程是：首先，m=m+ 1,通過內積運算，將投影到Θ的每一個向量gr∈Θ上，引入極限因子tm，找到滿足極限因子條件的原子的下標集Im=｛i:≥tm，r∈Θ｝，也即得到了滿足條件的所有原子；其次，與上一次迭代得到了原子下標集合Im-1合并，從而更新所選的原子下標集合Im=Im∪Im-1；然后，利用Gram-Schmidt正交化方法將這組原子正交化，并定義正交化后的向量為ui：ui=grup，i∈Im；再然后，將余項投影到ui（i∈Im）上，得到，由于由新的余量與ui（i∈ Im）正交，所以；最后，如果不滿足停止條件（即新余量極微小）或者（即原子下標過多），則循環執行單次迭代。否則，迭代結束。設共迭代了M次，此時有

從上述迭代過程可以看出，StOMP算法是在冗余字典中尋找一個較優的正交基進行分解，但是StOMP算法每次匹配追蹤時選出的是多個匹配原子而不是單個原子，不是信號的最佳表示，降低了稀疏分解的精度，提高了計算速度，相當于將OMP算法進行一定程度的簡化。

另外，StOMP算法中引入的極限因子一般是預設定的數值，相當于迭代閾值，它對稀疏分解的精度相當敏感，如果設定不當，不僅分解速度受到極大影響，同時稀疏分解和重構精度均大幅降低，甚至完全無法重構。為了克服這個問題，優化StOMP算法性能，經過實驗提出了基于余量向量和基向量gr的互相關向量的自適應極限因子選取方法和迭代結束條件重設，取得良好效果。

3　實驗與結果

在MATLAB R2014a（8.3.0.532）下編寫StOMP及其優化算法程序，冗余字典（即感知矩陣Φ）使用伯努利矩陣，實驗信號f為長度N=256的一維信號，該信號中的隨機位置上有K （K＜N）個服從標準正態分布的非零實數，其余全部為0。依次設定K取值為10、20、30、40、50、60、70、80、90、100時，對照StOMP及其優化算法在迭代次數、選出原子數目、計算速度和重構精度（相對誤差）上的差異，實驗結果如圖1所示。

圖1　不同稀疏度下StOMP及其優化對比

從實驗結果可以看出StOMP優化算法較StOMP算法，在運行時間略微提高的情況下，迭代次數進一步減少，重構精度有較好提升；另外，由于采用基于互相關向量的極限因子，算法的魯棒性也得到提高。

4　結束語

分段正交匹配追蹤StOMP算法因選出的是多個匹配原子而不是單個原子，減少了迭代次數，相當于OMP算法進行了一定程度的簡化。StOMP算法進一步優化后，通過實驗，在運行時間開銷基本增長不大的情況下，增加了算法魯棒性，重構精度得到提高。未來，可考慮構造自適應冗余字典，進一步提高算法性能。

［1］程濤,朱國賓,劉玉安.壓縮感知中高斯矩陣的優化研究［J］.計算機應用研究,2014,31（12）:3599-3602.

［2］Candès E J,Wakin M B.An Introduction to Compressive Sampling［J］.IEEE Signal Processing Magazine,2008,25（2）:21-30.

［3］DONOHO D.Compressed sensing［J］.IEEE Transactions on In formation Theory,2006,52（4）:1289-1306.

［4］方紅,楊海蓉.貪婪算法與壓縮感知理論［J］.自動化學報,2011，37（12）:1413-1421.

［5］戴瓊海,付長軍,季向陽.壓縮感知研究［J］.計算機學報,2011, 34（3）:3425-3434.

［6］王燕霞,張弓.一種改進的用于稀疏表示的正交匹配追蹤算法［J］.信息與電子工程,2012,10（5）:579-583.

［7］姚遠,梁志毅.基于壓縮感知信號重建的自適應空間正交匹配追蹤算法［J］.計算機科學,2012,39（10）:50-53.

Optimization of segmented orthogonal matching pursuit StOMP algorithm based on compressed sensing

HUANG Tong1，LI Di-na1，SHAO Si-fei1，2
（1.Innovation College of Yan'an University，Xi'an 710100,China；2.College of Physics and Electronic Information Yan'an University，Yan'an 716000,China）

In order to further reduce the number of iterations of segmented orthogonal matching pursuit（StOMP）algorithm and improve the reconstruction accuracy,propose optimization methods of adaptive limit factor selection based on cross-correlation vector and iteration ending condition reset through the analysis of multi atom matching method in the iterative process of StOMP algorithm.MATLAB programming experiment in random test data with given sparse degree k,show that the optimized algorithm reduce iterations 1-2 times,improve reconstruction accuracy by about 1%,increase the robustness than the original StOMP algorithm,while time consumption is almost the same.

compressed sensing；orthogonal matching pursuit algorithm；segmented orthogonal matching pursuit algorithm；StOMP

TN911.72

A

1674－6236（2016）13-0018-03

2015-07-03稿件編號：201507033

陜西省教育廳科研計劃項（14JK2170）

黃 同（1980—），男，河南桐柏人，碩士研究生，講師。研究方向：現代信號處理、系統軟件開發和嵌入式系統設計。