壓縮感知重構(gòu)匹配類算法分析

端木春江 肖艷麗

摘要： 壓縮感知理論是一種利用信號的稀疏性或可壓縮性而把采樣與壓縮融為一體的新理論體系，它成功地克服了傳統(tǒng)理論中采樣數(shù)據(jù)量大、資源浪費(fèi)嚴(yán)重等問題。該理論的研究方向主要包括信號的稀疏表示、測量矩陣的設(shè)計(jì)和信號的重構(gòu)算法。其中信號的重構(gòu)算法是該理論中的關(guān)鍵部分，也是近年來研究的熱點(diǎn)。本文主要對匹配追蹤類重構(gòu)算法作了詳細(xì)介紹，并通過仿真實(shí)驗(yàn)結(jié)果對這些算法進(jìn)行了對比和分析。

關(guān)鍵詞： 壓縮感知； 稀疏信號； 重構(gòu)算法； 匹配追蹤類壓縮感知算法

中圖分類號：TN919.81文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228（2012）04-15-03

A survey of reconstruction algorithms based on matching in compressive sensing

Duanmu Chunjiang, Xiao Yanli

（Zhejiang Normal University， School of Mathematics， Physics， and Information Engineering, Jinhua， Zhejiang 321004， China）

Abstract：The compressive sensing theory is a recent proposed theory, which can utilize the sparse and compressive characteristics of signals to combine the sampling and compression processes into only one procedure. It overcomes the shortcomings of large sampling data and significant waste of resource in traditional theories. The research areas in compressive sensing mainly include the sparse representation of signals, the design of measurement matrix, and signal reconstruction algorithms. The reconstruction algorithm is the key component of this new theory and is the focus of recent research. In this paper, the reconstruction algorithms, which use matching and tracking techniques, are described in details. Simulations of these algorithm are also conducted to compare and analyze these algorithms.

Key words： compressive sensing, sparse signal, reconstruction algorithm, compress sensing algorithms based on matching

1 CS（壓縮感知）背景知識(shí)

壓縮感知理論[1-4]是一種能夠在采樣的同時(shí)實(shí)現(xiàn)壓縮目的的新理論，其基本思想是：只要信號本身或者信號在某個(gè)變換域上是稀疏的或可壓縮的，那么就可以用一個(gè)與變換域不相關(guān)的測量矩陣將變換域的高維信號投影到一個(gè)低維空間上，然后通過求解一個(gè)優(yōu)化問題就能夠從少量的投影系數(shù)中以較高的概率成功或近似地重構(gòu)出原信號。在該理論框架下，采樣速率不依賴于信號帶寬，而取決于信號本身的結(jié)構(gòu)和內(nèi)容。該理論的基本框架如圖1所示。

圖1壓縮感知理論框架

信號的可稀疏性是壓縮感知理論的基礎(chǔ)和前提。只有選擇合適的基來表示信號，才能保證信號的稀疏度，從而保證信號的精確重構(gòu)。假設(shè)給定一組基（設(shè)為標(biāo)準(zhǔn)正交基ψ），如果一個(gè)長度為N的信號x可以用ψ中K個(gè)基向量線性表示，那么有：

（1.1）

則稱x為K階稀疏信號。其中系數(shù)，由此可以看出，x和s是對同一信號的兩種等價(jià)描述形式，x為信號時(shí)域形式，s為信號在ψ域的變換形式。

當(dāng)我們用一個(gè)已知的測量矩陣來采樣未知的稀疏信號x時(shí)，則可得到M維的線性測量值y=RM。

（1.2）

其中，是M×N維的矩陣，稱作傳感矩陣。對于測量值y，可以看成是s關(guān)于傳感矩陣的測量值。當(dāng)傳感矩陣滿足RIP（約束等距條件）[5]時(shí)，可以通過求解問題(1.2)的逆問題先求出稀疏系數(shù)s，然后由式(1.1)解出x，從而將x從M維的觀測向量y中正確地恢復(fù)出來。信號稀疏重構(gòu)問題的最直接有效方法是通過一個(gè)類似l0范數(shù)的最優(yōu)化問題來重構(gòu)原始信號x，即：

s.t.φx=y（1.3）

其中是重構(gòu)出的信號。

通過上述分析可知，壓縮傳感理論的研究主要包括三個(gè)方面：信號的稀疏表示、測量矩陣的設(shè)計(jì)和信號的重構(gòu)算法。信號的重構(gòu)算法是壓縮傳感理論當(dāng)中相當(dāng)關(guān)鍵的一部分，其算法主要有兩類：一類是匹配追蹤類重構(gòu)算法，主要是求解l0范數(shù)的最小化問題，主要包括正交匹配追蹤(OMP)算法[6]、正則化正交匹配追蹤（ROMP）算法[7]、子空間追蹤（SP）算法[8]、壓縮抽樣匹配追蹤（CoSaMP）算法[9]；另一類是凸松弛類算法，它是把l0范數(shù)最小化直接轉(zhuǎn)化為l1范數(shù)最小化，并通過凸優(yōu)化方法求解，主要包括基追蹤算法[10]、梯度追蹤算法[11]、迭代硬閾值算法[12]等。下面主要對匹配追蹤類重構(gòu)算法進(jìn)行具體的介紹和比較分析。

2 CS匹配追蹤類重構(gòu)算法

匹配追蹤類重構(gòu)算法主要是運(yùn)用貪婪算法思想來解決l1范數(shù)問題。其基本思想是在每一次的迭代過程中，從過完備原字庫里（即測量矩陣φ）選擇與信號最匹配的原子來進(jìn)行稀疏逼近并求出余量，然后繼續(xù)選出與信號余量最為匹配的原子，并把它們放在不斷更新的原子支撐集φ∧中，依次類推，經(jīng)過數(shù)次迭代，該信號便可以用這些原子進(jìn)行線性表示。

在允許一定重構(gòu)誤差存在的情況下，l0范數(shù)最小化求解模型為式(2.1)。

s.t. (2.1)

其中：s為信號x的稀疏變換域形式，ε是一個(gè)較小的常數(shù)。

在匹配追蹤類算法中，對于相關(guān)系數(shù)u的計(jì)算，是通過余量r與測量矩陣φ（）中各個(gè)原子之間內(nèi)積的絕對值來求解的，如式(2.2)：

(2.2)

然后采用最小二乘法進(jìn)行求解信號逼近值以及余量的更新值rnew：

(2.3)

(2.4)

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

OMP算法是對MP(匹配追蹤)算法的一種改進(jìn)。該算法仍然沿用了MP算法中的原子選擇準(zhǔn)則，即從原子集合φ中選擇和觀測信號或迭代余量最為匹配的原子。除此之外，OMP算法需要將已選擇的原子運(yùn)用Gram-Schmidt正交化方法進(jìn)行處理，然后再將信號投影在這些正交原子構(gòu)成的空間上，從而得到信號在各個(gè)已選原子上的分量和迭代余量?；谶@種正交性處理，OMP算法不會(huì)重復(fù)地選擇原子，因此經(jīng)過有限次（K次）迭代后就能夠收斂到稀疏解，從而大大降低了迭代次數(shù)。正是由于這種原子正交化處理的加入，加大了OMP算法的計(jì)算量，使得信號重構(gòu)時(shí)間遠(yuǎn)遠(yuǎn)長于匹配追蹤算法，所以對于一些大規(guī)模信號，OMP算法可能無法使用。

另外，OMP的重構(gòu)算法是在迭代次數(shù)已知的條件下重構(gòu)的，這種使迭代過程強(qiáng)制停止的方法使得OMP算法需要大量的線性測量來保證其重構(gòu)精度。OMP算法以貪婪迭代的方法選擇出列，使得在每次迭代中選擇的列與當(dāng)前的冗余向量最大程度地相關(guān)，然后從測量向量中減去相關(guān)部分并反復(fù)迭代，直至迭代次數(shù)達(dá)到稀疏度K后強(qiáng)制停止。

其具體步驟如下：

① 初始余量r0=y，迭代次數(shù)n=1，信號稀疏度為K，索引值集合；

② 用式(2.2)計(jì)算相關(guān)系數(shù)u，并找出u中最大值對應(yīng)的索引值m，存入索引集合中，即；

③ 更新原子支撐集φ∧；

④ 應(yīng)用式(2.3)得到，同時(shí)用式(2.4)對余量r進(jìn)行更新；

⑤ 若，令r=rnew，n=n+1，轉(zhuǎn)步驟②，否則，停止迭代。

2.2 正則化正交匹配追蹤（ROMP）算法

ROMP算法解決了OMP算法對感知矩陣要求比較嚴(yán)格這一問題。文獻(xiàn)中所提出的ROMP算法對所有滿足RIP條件的矩陣和所有能夠準(zhǔn)確估計(jì)出稀疏度的信號都可以精確重構(gòu)，并且重建速度較快。

對于K-稀疏的信號重構(gòu)問題，ROMP算法和OMP算法的不同之處主要是在于進(jìn)行了兩次原子的選擇。首先它和OMP算法一樣采用相關(guān)性原則進(jìn)行原子的一次篩選，然后通過求余量r與測量矩陣φ中各個(gè)原子內(nèi)積的絕對值，來計(jì)算相關(guān)系數(shù)u，并按照此方法將篩選出的K個(gè)原子的索引值存到候選索引集J中以進(jìn)行原子的二次篩選。對于原子的二次篩選，ROMP算法主要是采用了正則化過程，因此它被叫做正則化正交匹配追蹤算法。其方法是根據(jù)式(2.5)將J中索引值所對應(yīng)原子的相關(guān)系數(shù)分成若干組：

i,j∈J (2.5）

然后選擇能量最大的一組相關(guān)系數(shù)所對應(yīng)的原子索引值存入g0中，同時(shí)將其原子存入更新支撐集φ∧中。該正則化過程可以使得ROMP算法最多經(jīng)過K次迭代便可以得到一個(gè)原子數(shù)小于2K的支撐集φ∧用于精確重構(gòu)信號，對于沒有選入支撐集的原子，此正則化過程則能夠保證它們的能量一定遠(yuǎn)小于被選入原子的能量，從而提高了信號的重構(gòu)可靠性。經(jīng)過一定的迭代次數(shù)得到用于信號重構(gòu)的支撐集φ∧后，再采用最小二乘法進(jìn)行信號逼近及余量更新。

其算法的基本步驟是：

① 設(shè)初始余量r0=y，迭代次數(shù)n=1，信號稀疏度為K，索引值集合；

② 用式(2.2)計(jì)算相關(guān)系數(shù)u，并找出u中最大值對應(yīng)的索引值m，存入索引集合中，即；

③ 對J中索引值所對應(yīng)原子的相關(guān)系數(shù)進(jìn)行正則化，并將結(jié)果存入集合g0中，同時(shí)保證該集合中原子的相關(guān)系數(shù)必須滿足式(2.5)；

④ 更新原子支撐集φ∧；

⑤ 應(yīng)用式(2.3)得到，同時(shí)用式(2.4)對余量進(jìn)行更新；

⑥ 若候選集的原子個(gè)數(shù)不小于2k個(gè)，則停止迭代，否則，令r=rnew，n=n+1，轉(zhuǎn)步驟②。

2.3 子空間追蹤（SP）算法

SP算法是一種存在或不存在噪聲干擾的情況下都可以用于稀疏信號重構(gòu)的方法。這一算法與OMP類算法相比具有更低的計(jì)算復(fù)雜度。分析顯示，在無噪聲情況下，對于由帶有一個(gè)常量參數(shù)的受限等距矩陣所提供的任意稀疏信號，SP算法都可以精確恢復(fù)原信號；存在噪聲或信號不是嚴(yán)格稀疏時(shí)，SP算法可以通過加倍測量數(shù)和信號干擾能量常量的方法，來確定重構(gòu)均方差的上界。

SP算法的基本思想是在貪婪算法的基礎(chǔ)上借用回溯的思想，在每一次迭代過程中混合一個(gè)簡單的方法來重新估計(jì)所有候選者的可信賴性，這主要體現(xiàn)在原子的選擇方式上。該算法與OMP算法不同的是從原子庫中選擇多個(gè)較相關(guān)的原子后再剔除部分原子，保證每次迭代時(shí)支撐集φ∧中有K個(gè)原子，因而候選集合中最多不會(huì)超過2K個(gè)原子，每次剔除的數(shù)目最多也不會(huì)超過K個(gè)。該算法的具體步驟如下：

① 設(shè)初始余量r0=y，迭代次數(shù)n=1，信號稀疏度為K，索引值集合；

② 用式（2.2）計(jì)算相關(guān)系數(shù)u，并找出u中K最大值對應(yīng)的索引值m0,m1…mk，將其存入索引集合中，即；

③ 更新原子支撐集φ∧；

④ 應(yīng)用式(2.3)得到，同時(shí)用式(2.4)對余量進(jìn)行更新；

⑤ 若候選集中的原子個(gè)數(shù)大于2k個(gè)，則停止迭代，否則，令r=rnew，n=n+1，轉(zhuǎn)步驟②。

2.4 壓縮抽樣匹配追蹤（CoSaMP）算法

Needell等人提出的CoSaMP算法也可以很好地進(jìn)行信號重構(gòu)。它和SP算法一樣也是在貪婪算法的基礎(chǔ)上結(jié)合了組合算法中的回溯思想，在每一次迭代過程中，重新評估所有候選項(xiàng)的可能性。不同的是，該算法是在每次迭代后支撐集中就有2K個(gè)原子，因而保證了候選集合中最多不會(huì)超過3K個(gè)原子，同時(shí)剔除的原子數(shù)目最多不會(huì)超過K個(gè)。這種從原字庫中選擇多個(gè)較相關(guān)的原子同時(shí)再剔除部分原子的方法，提高了該算法的效率。

CoSaMP算法的具體步驟：

① 設(shè)初始余量r0=y，迭代次數(shù)n=1，信號稀疏度為K，索引值集合；

② 用式(2.2）計(jì)算相關(guān)系數(shù)u，并找出u中2K最大值對應(yīng)的索引值m0，m1…m2k-1，m2k，將其存入索引集中，即；

③ 更新原子支撐集φ∧；

④ 應(yīng)用式(2.3)得到，同時(shí)用式(2.4)對余量進(jìn)行更新；

⑤ 若候選集中的原子個(gè)數(shù)大于3k個(gè)，則停止迭代；否則，令r=rnew，n=n+1，轉(zhuǎn)步驟②。

3 實(shí)驗(yàn)結(jié)果和分析

由于信號在不同基變換下的稀疏度不同，從而影響到恢復(fù)原始圖像的質(zhì)量。在本文中，為了在同等條件下客觀地反應(yīng)上述算法的重構(gòu)性能，我們采用大小為256×256的Lena圖像如（圖1所示為原始圖像）作為測試圖像，然后采用離散余弦變換（圖2所示為稀疏變換DCT）作為稀疏變換以及正態(tài)隨機(jī)矩陣（圖3所示為測量矩陣）作為測量矩陣，以M/N=1/2的采樣速率，稀疏度k估計(jì)為測量值的1/4，分別應(yīng)用OMP算法、SP算法、CoSaMP算法進(jìn)行圖像的重建，重構(gòu)圖像分別如圖4、5、6所示：

圖1.原始圖像 圖2.稀疏變換 圖3.測量矩陣

圖4.OMP算法重構(gòu)的圖像圖5. SP算法重構(gòu)的圖像

圖6.CoSaMP算法重構(gòu)的圖像

通過上述圖像恢復(fù)的仿真結(jié)果，我們可以看出OMP算法恢復(fù)的圖像質(zhì)量明顯優(yōu)于CoSaOMP算法和SP算法。

4 結(jié)束語

壓縮感知理論是一種全新的采樣壓縮理論，其中信號的重構(gòu)算法是壓縮感知中比較關(guān)鍵的一部分，它的關(guān)鍵在于如何從低維信號恢復(fù)出高維信號。本文對于已有的經(jīng)典的機(jī)遇匹配類的重構(gòu)算法作了具體的介紹和實(shí)驗(yàn)仿真，描述了這些算法的具體過程和優(yōu)缺點(diǎn)，并通過仿真實(shí)驗(yàn)對它們進(jìn)行了實(shí)際恢復(fù)效果的比較。

參考文獻(xiàn)：

[1] Donoho D L.Compressed sensing[J].IEEE Transactions on Iformation Theory,2006.52(4):1289~1306

[2] Candes E,Tao T.Decoding by linear programming[J].IEEE Transactions on Information Theory,2005.51(12):4203~4215

[3] Candes E,Romberg J and Tao T.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory,2006.52(2):489~509

[4] Candes E,Tao T.Tear-optimal signal recovery from random projections:Universal encoding strategies[J].IEEE Transactions on Information Theory,2006.52(12):5406~5425

[5] 姚遠(yuǎn),劉鵬,王輝,等.基于稀疏矩陣存儲(chǔ)的狀態(tài)表壓縮算法[J].計(jì)算機(jī)應(yīng)用,2010.30(8):2157~2160

[6] Tropp J A,Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEE Transactions on Information Theory，2007.53(12)：4655~4666

[7] Needell D，Vershynin R．Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit［J］.Foundations of Computational Mathematics，2009.9 (3)：317~334

[8] Dai W，Mllenkovic O．Subspace pursuit for compressive sensing

signal reconstruction［J］．IEEE Transactions on Information Theory，2009.55(5)：2230~2249

[9] Needell D，Tropp J A．CoSaMP：Iterative signal recovery from

incomplete and inaccurate samples［J］．Applied and Computational Harmonic Analysis，2009.26(3)：301~321

[10] S S Chen，D L Donoho，M A Saunders，etc．Atomic

decomposition by basis pursuit［J］．SIAM Journal of Scientific Computing，1998.20(1)：33~61

[11] Blumensath T，Davies M E．Gradient pursuits[J]．IEEE Transactions on Signal Processing，2008.56(6)：2370~2382

[12] Blumensath T，Davies M E．Iterative hard thresholding for compressed sensing ［J］．Applied and Computational Harmonic Analysis，2009.27(3)：265~274