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

2、 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

3、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 reconstructi

4、on algorithms, which論文發(fā)表專家 ED國學(xué)JK友志廁 www.qikanwang,netuse 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 al

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

6、度，從而保證信號的精確重構(gòu)。 假設(shè)給定一組基（設(shè)為標(biāo)準(zhǔn)正交基甲），如果一個長度為n的信號x 可以用甲中k個基向量線性表示，那么有：（1.1）論文發(fā)表專家 ED國學(xué)JK友志廁 www.qikanwang,net則稱X為k階稀疏信號。其中系數(shù)，由此可以看出，x和s是對 同一信號的兩種等價描述形式，X為信號時域形式，s為信號在甲 域的變換形式。當(dāng)我們用一個已知的測量矩陣來采樣未知的稀疏信號X時，則可 得到m維的線性測量值y=rm。(1.2)其中，是mXn維的矩陣，稱作傳感矩陣。對于測量值y，可以看 成是s關(guān)于傳感矩陣的測量值。當(dāng)傳感矩陣滿足rip (約束等距條 件)5時，可以通過求解問題(1.2)的

7、逆問題先求出稀疏系數(shù)s， 然后由式(1.1)解出X，從而將x從m維的觀測向量y中正確地恢復(fù) 出來。信號稀疏重構(gòu)問題的最直接有效方法是通過一個類似10范 數(shù)的最優(yōu)化問題來重構(gòu)原始信號X，即：s.t. 甲 X=y(1.3)其中是重構(gòu)出的信號。通過上述分析可知，壓縮傳感理論的研究主要包括三個方面：信 號的稀疏表示、測量矩陣的設(shè)計和信號的重構(gòu)算法。信號的重構(gòu)算 法是壓縮傳感理論當(dāng)中相當(dāng)關(guān)鍵的一部分，其算法主要有兩類：一 類是匹配追蹤類重構(gòu)算法，主要是求解10范數(shù)的最小化問題，主 要包括正交匹配追蹤(omp)算法6、正則化正交匹配追蹤(romp) 算法7、子空間追蹤(sp)算法8、壓縮抽樣匹配追蹤(co

8、samp) 算法9；另一類是凸松弛類算法，它是把l0范數(shù)最小化直接轉(zhuǎn)化論文發(fā)表專家 ED國學(xué)JK友志廁 www.qikanwang,net為11范數(shù)最小化，并通過凸優(yōu)化方法求解，主要包括基追蹤算法 10、梯度追蹤算法11、迭代硬閾值算法12等。下面主要對匹 配追蹤類重構(gòu)算法進行具體的介紹和比較分析。2 cs匹配追蹤類重構(gòu)算法匹配追蹤類重構(gòu)算法主要是運用貪婪算法思想來解決11范數(shù)問 題。其基本思想是在每一次的迭代過程中，從過完備原字庫里(即 測量矩陣？)選擇與信號最匹配的原子來進行稀疏逼近并求出余 量，然后繼續(xù)選出與信號余量最為匹配的原子，并把它們放在不斷 更新的原子支撐集？ A中，依次類推，經(jīng)

9、過數(shù)次迭代，該信號便可 以用這些原子進行線性表示。在允許一定重構(gòu)誤差存在的情況下，10范數(shù)最小化求解模型為式 (2.1)。s.t.(2.1)其中：s為信號x的稀疏變換域形式，是一個較小的常數(shù)。在匹配追蹤類算法中，對于相關(guān)系數(shù)u的計算，是通過余量r與 測量矩陣？()中各個原子之間內(nèi)積的絕對值來求解的，如式(2.2)：(2.2)然后采用最小二乘法進行求解信號逼近值以及余量的更新值rnew：(2.3)(2.4)論文發(fā)表專家 ED國學(xué)JK技志廁 www.qikanwang,net2.1正交匹配追蹤（omp）算法omp算法是對mp（匹配追蹤）算法的一種改進。該算法仍然沿用了 mp算法中的原子選擇準(zhǔn)則，即

10、從原子集合w中選擇和觀測信號或迭 代余量最為匹配的原子。除此之外，omp算法需要將已選擇的原子 運用gram-schmidt正交化方法進行處理，然后再將信號投影在這 些正交原子構(gòu)成的空間上，從而得到信號在各個已選原子上的分量 和迭代余量。基于這種正交性處理，omp算法不會重復(fù)地選擇原子， 因此經(jīng)過有限次（k次）迭代后就能夠收斂到稀疏解，從而大大降 低了迭代次數(shù)。正是由于這種原子正交化處理的加入，加大了 omp 算法的計算量，使得信號重構(gòu)時間遠遠長于匹配追蹤算法，所以對 于一些大規(guī)模信號，omp算法可能無法使用。另外，omp的重構(gòu)算法是在迭代次數(shù)已知的條件下重構(gòu)的，這種 使迭代過程強制停止的方法

11、使得omp算法需要大量的線性測量來保 證其重構(gòu)精度。omp算法以貪婪迭代的方法選擇出列，使得在每次 迭代中選擇的列與當(dāng)前的冗余向量最大程度地相關(guān)，然后從測量向 量中減去相關(guān)部分并反復(fù)迭代，直至迭代次數(shù)達到稀疏度k后強制 停止。其具體步驟如下：初始余量r0=y，迭代次數(shù)n=1，信號稀疏度為k，索引值集合；用式（2.2）計算相關(guān)系數(shù)u，并找出u中最大值對應(yīng)的索引值論文發(fā)表專家 ED國學(xué)JK技志廁 www.qikanwang,net 口，存入索引集合中，即；更新原子支撐集？ A；應(yīng)用式(2.3)得到，同時用式(2.4)對余量r進行更新；若，令r=rnew, n=n+1，轉(zhuǎn)步驟，否則，停止迭代。2.2

12、正則化正交匹配追蹤(romp)算法romp算法解決了 omp算法對感知矩陣要求比較嚴(yán)格這一問題。文 獻中所提出的romp算法對所有滿足rip條件的矩陣和所有能夠準(zhǔn) 確估計出稀疏度的信號都可以精確重構(gòu)，并且重建速度較快。對于k-稀疏的信號重構(gòu)問題，romp算法和omp算法的不同之處 主要是在于進行了兩次原子的選擇。首先它和omp算法一樣米用相 關(guān)性原則進行原子的一次篩選，然后通過求余量r與測量矩陣？中 各個原子內(nèi)積的絕對值，來計算相關(guān)系數(shù)u，并按照此方法將篩選 出的k個原子的索引值存到候選索引集j中以進行原子的二次篩 選。對于原子的二次篩選，romp算法主要是采用了正則化過程，因 此它被叫做正則

13、化正交匹配追蹤算法。其方法是根據(jù)式(2.5)將j 中索引值所對應(yīng)原子的相關(guān)系數(shù)分成若干組：i,jEj(2.5)然后選擇能量最大的一組相關(guān)系數(shù)所對應(yīng)的原子索引值存入g0 中，同時將其原子存入更新支撐集？A中。該正則化過程可以使得 romp算法最多經(jīng)過k次迭代便可以得到一個原子數(shù)小于2k的支撐 集？ A用于精確重構(gòu)信號，對于沒有選入支撐集的原子，此正則化論文發(fā)表專家 ED國學(xué)JK技志廁 www.qikanwang,net過程則能夠保證它們的能量一定遠小于被選入原子的能量，從而提 高了信號的重構(gòu)可靠性。經(jīng)過一定的迭代次數(shù)得到用于信號重構(gòu)的 支撐集？ A后，再采用最小二乘法進行信號逼近及余量更新。其算

14、法的基本步驟是：設(shè)初始余量r0=y，迭代次數(shù)n=1,信號稀疏度為k,索引值集合；用式(2.2)計算相關(guān)系數(shù)u,并找出u中最大值對應(yīng)的索引值 口，存入索引集合中，即；對j中索引值所對應(yīng)原子的相關(guān)系數(shù)進行正則化，并將結(jié)果 存入集合g0中，同時保證該集合中原子的相關(guān)系數(shù)必須滿足式；更新原子支撐集？ A；應(yīng)用式(2.3)得到，同時用式(2.4)對余量進行更新；若候選集的原子個數(shù)不小于2k個，則停止迭代，否則，令 r=rnew，n=n+1，轉(zhuǎn)步驟。2.3子空間追蹤(sp)算法sp算法是一種存在或不存在噪聲干擾的情況下都可以用于稀疏信號重構(gòu)的方法。這一算法與omp類算法相比具有更低的計算復(fù)雜 度。分析顯示

15、，在無噪聲情況下，對于由帶有一個常量參數(shù)的受限 等距矩陣所提供的任意稀疏信號，sp算法都可以精確恢復(fù)原信號； 存在噪聲或信號不是嚴(yán)格稀疏時，sp算法可以通過加倍測量數(shù)和信論文發(fā)表專家 ED國學(xué)JK友志廁 www.qikanwang,net 號干擾能量常量的方法，來確定重構(gòu)均方差的上界。sp算法的基本思想是在貪婪算法的基礎(chǔ)上借用回溯的思想，在每 一次迭代過程中混合一個簡單的方法來重新估計所有候選者的可 信賴性，這主要體現(xiàn)在原子的選擇方式上。該算法與omp算法不同 的是從原子庫中選擇多個較相關(guān)的原子后再剔除部分原子，保證每 次迭代時支撐集？A中有k個原子，因而候選集合中最多不會超過 2k個原子，每

16、次剔除的數(shù)目最多也不會超過k個。該算法的具體步 驟如下：設(shè)初始余量r0=y，迭代次數(shù)n=1，信號稀疏度為k，索引值集 合；用式(2.2)計算相關(guān)系數(shù)u，并找出u中k最大值對應(yīng)的索 引值m0,m1mk，將其存入索引集合中，即；更新原子支撐集？ A；應(yīng)用式(2.3)得到，同時用式(2.4)對余量進行更新；若候選集中的原子個數(shù)大于2k個，則停止迭代，否則，令 r=rnew，n=n+1，轉(zhuǎn)步驟。2.4壓縮抽樣匹配追蹤(cosamp)算法needell等人提出的cosamp算法也可以很好地進行信號重構(gòu)。它 和sp算法一樣也是在貪婪算法的基礎(chǔ)上結(jié)合了組合算法中的回溯 思想，在每一次迭代過程中，重新評估所有

17、候選項的可能性。不同 的是，該算法是在每次迭代后支撐集中就有2k個原子，因而保證論文發(fā)表專家 ED國學(xué)JK友志廁 www.qikanwang,net 了候選集合中最多不會超過3k個原子，同時剔除的原子數(shù)目最多 不會超過k個。這種從原字庫中選擇多個較相關(guān)的原子同時再剔除 部分原子的方法，提高了該算法的效率。cosamp算法的具體步驟：設(shè)初始余量r0=y，迭代次數(shù)n=1，信號稀疏度為k，索引值集 合；用式(2.2)計算相關(guān)系數(shù)u，并找出u中2k最大值對應(yīng)的索 引值m0，m1m2kT，m2k，將其存入索引集中，即;更新原子支撐集;應(yīng)用式(2.3)得到，同時用式(2.4)對余量進行更新；若候選集中的原

18、子個數(shù)大于3k個，則停止迭代；否則，令 r=rnew，n=n+1，轉(zhuǎn)步驟。3實驗結(jié)果和分析由于信號在不同基變換下的稀疏度不同，從而影響到恢復(fù)原始圖 像的質(zhì)量。在本文中，為了在同等條件下客觀地反應(yīng)上述算法的重 構(gòu)性能，我們采用大小為256X256的lena圖像如(圖1所示為原 始圖像)作為測試圖像，然后采用離散余弦變換(圖2所示為稀疏 變換dct)作為稀疏變換以及正態(tài)隨機矩陣(圖3所示為測量矩陣) 作為測量矩陣，以m/n=1/2的采樣速率，稀疏度k估計為測量值的 1/4，分別應(yīng)用omp算法、sp算法、cosamp算法進行圖像的重建， 重構(gòu)圖像分別如圖4、5、6所示：論文發(fā)表專家由國導(dǎo)氟友志網(wǎng)gw

19、ww.qikanwang,net圖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)典的機遇匹配類的重構(gòu)算法作了 具體的介紹和實驗仿真，描述了這些算法的具體過程和優(yōu)缺點，并 通過仿真實驗對它們進行了實際恢復(fù)效果的比較。參考文獻：donoho d pressed

20、 sensingj.ieee transactions on iformation theory,2006.52(4):12891306candes e,tao t.decoding by linear programmingj.ieee transactions on information theory,2005.51(12):42034215candes e,romberg j and tao t.robust uncertainty論文發(fā)表專家 ED國學(xué)JK技志廁 www.qikanwang,netprinciples:exact signal reconstruction from

21、highly incomplete frequency informationj.ieee transactions on information theory,2006.52(2):489509candes e,tao t.tear-optimal signal recovery from random projections:universal encoding strategiesj.ieee transactions on information theory,2006.52(12):54065425姚遠，劉鵬，王輝，等.基于稀疏矩陣存儲的狀態(tài)表壓縮算法 j.計算機應(yīng)用,2010.30

22、(8):21572160tropp j a,gilbert a c.signal recovery from random measurements via orthogonal matching pursuitj.ieee transactions on information theory， 2007.53(12): 46554666needell d， vershynin r. uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit j .foundations of computational mathematics,