龐影影

摘要：由于傳統(tǒng)的信號(hào)處理技術(shù)對(duì)信號(hào)頻率的限制，越來(lái)越不能滿足日益增長(zhǎng)的信號(hào)需求，因而一種新的信號(hào)處理技術(shù)—壓縮感知技術(shù)被提出。壓縮感知技術(shù)由于其打破了奈奎斯特采樣定理對(duì)信號(hào)采樣頻率的限制因而被廣泛應(yīng)用于信號(hào)處理方面，而壓縮感知技術(shù)的關(guān)鍵部分就是重構(gòu)算法的運(yùn)用，本文主要介紹基于壓縮感知的幾種重構(gòu)算法，并且比較各個(gè)算法的優(yōu)缺點(diǎn)，從而為今后的運(yùn)用提供有利的指導(dǎo)。

關(guān)鍵詞：壓縮感知；MP算法；OMP算法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）23-0153-02

1引言

壓縮感知（Compressive Sensing）[1，2]技術(shù)是信號(hào)處理領(lǐng)域提出的一種新的信號(hào)處理技術(shù)，由D. Donoho（美國(guó)科學(xué)院院士）、E. Candes及華裔科學(xué)家陶哲軒等人提出。奈奎斯特采樣定理在進(jìn)行A/D信號(hào)的轉(zhuǎn)換過(guò)程表明：當(dāng)采樣信號(hào)的頻率大于信號(hào)2倍帶寬時(shí)，經(jīng)過(guò)采樣后的數(shù)字信號(hào)才能保留了原始信號(hào)中的完整信息。由于壓縮感知表明：如果信號(hào)在某一個(gè)正交空間是稀疏性的，就可以以較低的頻率即遠(yuǎn)低于2倍帶寬的頻率來(lái)采樣該信號(hào)，并有很大可能來(lái)精確的重構(gòu)該信號(hào)，從而打破了奈奎斯特采樣定理，因此在現(xiàn)代信號(hào)處理領(lǐng)域展現(xiàn)出突出的優(yōu)勢(shì)和廣闊的前景。

2壓縮感知與恢復(fù)算法

2.1 壓縮感知理論

壓縮感知理論一般分為三部分：

2.1.1信號(hào)的稀疏表示

信號(hào)的稀疏性可以表示為進(jìn)行采樣和重構(gòu)的信號(hào)本身能是被壓縮的，或者在某些稀疏變換基下是稀疏的，實(shí)際中大部分信號(hào)均具有這種特性，因此信號(hào)的稀疏表示就是將信號(hào)轉(zhuǎn)變?yōu)樗鼈兊南∈栊问?。比較常見的稀疏轉(zhuǎn)換基有快速傅里葉變換基（FFT）、離散余弦變換基（DCT）、Curvelet基、Gabor基以及冗余字典[3]等。

2.1.2觀測(cè)矩陣的設(shè)計(jì)

假定有一稀疏信號(hào)X，理論上可以用X的M個(gè)線性測(cè)量精確重構(gòu)X，其中，通常情況下方程具有無(wú)窮解，因此提出了唯一解的充要條件就是：觀測(cè)矩陣[4，5]要滿足有限等距準(zhǔn)則（Restricted Isometry Property， RIP）即等效求解為

[x=arg minx0 s.t. y=Θx] （1）

由于上式是NP問題，計(jì)算求解復(fù)雜度高，因此提出了恢復(fù)算法即重構(gòu)算法。

2.1.3重構(gòu)算法的選擇

對(duì)重構(gòu)算法的比較主要從算法精確重構(gòu)的概率，重構(gòu)算法的運(yùn)行時(shí)間，以及重構(gòu)信號(hào)與原始信號(hào)的相對(duì)誤差這幾方面。而一般重構(gòu)算法可分為三大類：貪婪算法、凸優(yōu)化算法以及綜合算法，其中貪婪算法計(jì)算復(fù)雜度低，所需采樣點(diǎn)少，運(yùn)算速度快，適用于小規(guī)模信號(hào)重構(gòu)，在本文中將著重比較貪婪算法中的幾種重構(gòu)算法。

2.2 貪婪迭代重構(gòu)算法的比較

2.2.1 MP算法（匹配追蹤算法）

MP算法：MP算法是一種貪心算法，就是從每次迭代的測(cè)量矩陣中選擇一個(gè)與信號(hào)X最匹配的原子，構(gòu)建成稀疏逼近，從而求出信號(hào)殘差，繼續(xù)選擇與求得的信號(hào)殘差最匹配的原子，經(jīng)過(guò)多次迭代，信號(hào)X就可以由這些原子的線性和以及最后的殘差值來(lái)表示出來(lái)。而且如果殘差值在較小的范圍內(nèi)可忽略，信號(hào)X就可以由這些原子的線性組合來(lái)表示，但如果殘差值在已選擇的原子上進(jìn)行垂直投影結(jié)果是非正交性的，這樣就會(huì)導(dǎo)致迭代結(jié)果不是最優(yōu)的，算法的迭代次數(shù)不是最少的，因而使得收斂需要更多次的迭代，使得算法的重構(gòu)效率變低，在此基礎(chǔ)上我們提出了OMP算法。

2.2.2 OMP算法（正交匹配追蹤算法）

OMP算法相比較MP算法優(yōu)勢(shì)在于：在分解過(guò)程中，每一步都將選擇的原子正交化，從而保證選擇原子的最優(yōu)，減少了算法的迭代次數(shù)，使得算法的收斂速度更快。

其中MP算法與OMP算法原子的選擇并沒有變化，都是在每次迭代過(guò)程中，找到與殘差最相關(guān)的一個(gè)原子放入原子集合中，但是當(dāng)測(cè)量矩陣為高斯隨機(jī)矩陣時(shí)，對(duì)一個(gè)信號(hào)X，它的信號(hào)長(zhǎng)度為n，稀疏度為k，OMP算法精確重構(gòu)原始信號(hào)的概率很大，而且運(yùn)算的時(shí)間復(fù)雜度很低，由于OMP算法對(duì)測(cè)量信號(hào)滿足的要求較高，重構(gòu)時(shí)精度較低，使得對(duì)于選擇的測(cè)量矩陣的要求也比較高。OMP算法的運(yùn)算步驟如下：

輸入：觀測(cè)向量，觀測(cè)矩陣，原始信號(hào)的稀疏度K

輸出：重構(gòu)信號(hào)

1）初始化殘差 ，索引集為空集，迭代次數(shù)t=1。

2）找出殘差r和傳感矩陣的列積中最大值所對(duì)應(yīng)的腳標(biāo)。

3）更新索引矩陣與原子集{}，記錄找到的傳感矩陣中的 重建原子集合。

4）由最小二乘法得到。

5）更新殘差，t=t+1。

6）判斷迭代停止條件，若滿足，則停止迭代，若不滿足，則重復(fù)步驟2。

在OMP算法的基礎(chǔ)上，又提出了StOMP算法。

2.2.3 StOMP算法（分段正交匹配追蹤算法）

StOMP算法是OMP算法的改進(jìn)算法，它是將迭代過(guò)程劃分為幾個(gè)階段進(jìn)行。在每次迭代時(shí)選擇的是一組原子，因此運(yùn)算速度比OMP快。而且運(yùn)算時(shí)并不需要輸入原始信號(hào)的稀疏度K，因而相比OMP有獨(dú)到的優(yōu)勢(shì)。

3總結(jié)

近年來(lái)，隨著信息領(lǐng)域的不斷發(fā)展，對(duì)于信號(hào)的精密程度的要求也越來(lái)越高，然而傳統(tǒng)的信號(hào)處理技術(shù)越來(lái)越不能滿足人們的需要，因此壓縮感知理論應(yīng)運(yùn)而生，在本文中主要介紹了壓縮感知理論的幾種重構(gòu)算法，為今后實(shí)際運(yùn)用提供借鑒，由于壓縮感知現(xiàn)階段只是理論部分，實(shí)際應(yīng)用并不廣泛，因此對(duì)于壓縮感知的實(shí)際應(yīng)用還有很長(zhǎng)的道路探索。

參考文獻(xiàn)：

[1] 李樹濤，魏丹.壓縮感知綜述[J].自動(dòng)化學(xué)報(bào)，2009.

[2] 陳明生，王時(shí)文，馬韜，吳先良.基于壓縮感知的目標(biāo)頻空電磁散射特性快速分析[J].物理學(xué)報(bào)，2014.

[3] 張春梅，尹忠科，肖明霞.基于冗余字典的信號(hào)超完備表示和稀疏分解[J].科學(xué)通報(bào)，2006.

[4] 付強(qiáng)，李瓊.壓縮感知中測(cè)量矩陣的研究[J].應(yīng)用技術(shù)與研究，2011.

[5] 李小波.基于壓縮感知的測(cè)量矩陣研究[D].北京：北京交通大學(xué)碩士學(xué)論文，2010.