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

黃 同，李娣娜，邵思飛，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ǔ)上，為了進(jìn)一步減少算法迭代次數(shù)，提高重構(gòu)精度，提出了基于互相關(guān)向量的自適應(yīng)極限因子選取和迭代結(jié)束條件重設(shè)的優(yōu)化方法。通過MATLAB編程實(shí)驗(yàn)，在隨機(jī)給定稀疏度為K的測試數(shù)據(jù)條件下，優(yōu)化后的算法較StOMP算法迭代次數(shù)減少1-2次，重構(gòu)精度提升約1%，魯棒性增加，而運(yùn)行時(shí)間開銷相差無幾。

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

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

1　壓縮感知理論

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

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

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

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

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

2.1正交匹配追蹤算法OMP

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

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

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

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

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

分段正交匹配追蹤算法的單次迭代過程是：首先，m=m+ 1,通過內(nèi)積運(yùn)算，將投影到Θ的每一個(gè)向量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；再然后，將余項(xiàng)投影到ui（i∈Im）上，得到，由于由新的余量與ui（i∈ Im）正交，所以；最后，如果不滿足停止條件（即新余量極微小）或者（即原子下標(biāo)過多），則循環(huán)執(zhí)行單次迭代。否則，迭代結(jié)束。設(shè)共迭代了M次，此時(shí)有

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

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

3　實(shí)驗(yàn)與結(jié)果

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

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

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

4　結(jié)束語

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

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

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

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

［7］姚遠(yuǎn),梁志毅.基于壓縮感知信號(hào)重建的自適應(yīng)空間正交匹配追蹤算法［J］.計(jì)算機(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稿件編號(hào)：201507033

陜西省教育廳科研計(jì)劃項(xiàng)（14JK2170）

黃 同（1980—），男，河南桐柏人，碩士研究生，講師。研究方向：現(xiàn)代信號(hào)處理、系統(tǒng)軟件開發(fā)和嵌入式系統(tǒng)設(shè)計(jì)。