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

（1.延安大學(xué) 西安創(chuàng)新學(xué)院，陜西 西安710100；2.延安大學(xué) 物理與電子信息學(xué)院，陜西 延安 716000）

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

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

（1.延安大學(xué) 西安創(chuàng)新學(xué)院，陜西 西安710100；2.延安大學(xué) 物理與電子信息學(xué)院，陜西 延安 716000）

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

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

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

1　壓縮感知理論

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

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

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

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

2　分段正交匹配追蹤算法及其優(yōu)化

2.1正交匹配追蹤算法OMP

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

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

2.2分段正交匹配追蹤StOMP算法及其優(yōu)化

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

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

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

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

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

3　實驗與結(jié)果

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

圖1　不同稀疏度下StOMP及其優(yōu)化對比

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

4　結(jié)束語

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

［1］程濤,朱國賓,劉玉安.壓縮感知中高斯矩陣的優(yōu)化研究［J］.計算機應(yīng)用研究,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］.自動化學(xué)報,2011，37（12）:1413-1421.

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

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

［7］姚遠,梁志毅.基于壓縮感知信號重建的自適應(yīng)空間正交匹配追蹤算法［J］.計算機科學(xué),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—），男，河南桐柏人，碩士研究生，講師。研究方向：現(xiàn)代信號處理、系統(tǒng)軟件開發(fā)和嵌入式系統(tǒng)設(shè)計。