端木春江 肖艷麗

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

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

中圖分類(lèi)號(hào)：TN919.81文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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)壓縮目的的新理論，其基本思想是：只要信號(hào)本身或者信號(hào)在某個(gè)變換域上是稀疏的或可壓縮的，那么就可以用一個(gè)與變換域不相關(guān)的測(cè)量矩陣將變換域的高維信號(hào)投影到一個(gè)低維空間上，然后通過(guò)求解一個(gè)優(yōu)化問(wèn)題就能夠從少量的投影系數(shù)中以較高的概率成功或近似地重構(gòu)出原信號(hào)。在該理論框架下，采樣速率不依賴(lài)于信號(hào)帶寬，而取決于信號(hào)本身的結(jié)構(gòu)和內(nèi)容。該理論的基本框架如圖1所示。

圖1壓縮感知理論框架

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

（1.1）

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

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

（1.2）

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

s.t.φx=y（1.3）

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

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

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

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

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

s.t. (2.1)

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

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

(2.2)

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

(2.3)

(2.4)

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

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

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

其具體步驟如下：

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

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

③ 更新原子支撐集φ∧；

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

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

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

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

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

i,j∈J (2.5）

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

其算法的基本步驟是：

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

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

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

④ 更新原子支撐集φ∧；

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

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

2.3 子空間追蹤（SP）算法

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

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

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

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

③ 更新原子支撐集φ∧；

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

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

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

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

CoSaMP算法的具體步驟：

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

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

③ 更新原子支撐集φ∧；

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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