基于壓縮感知的重構(gòu)算法研究

龐影影

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）23-0153-02

1引言

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

2壓縮感知與恢復算法

2.1 壓縮感知理論

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

2.1.1信號的稀疏表示

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入：觀測向量，觀測矩陣，原始信號的稀疏度K

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

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

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

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

4）由最小二乘法得到。

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

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

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

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

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

3總結(jié)

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

參考文獻：

[1] 李樹濤，魏丹.壓縮感知綜述[J].自動化學報，2009.

[2] 陳明生，王時文，馬韜，吳先良.基于壓縮感知的目標頻空電磁散射特性快速分析[J].物理學報，2014.

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

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

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