李盈婷

（西南大學(xué)計算機與信息科學(xué)學(xué)院 軟件學(xué)院，重慶 400715）

壓縮感知理論及兩種貪婪算法詳解

李盈婷

（西南大學(xué)計算機與信息科學(xué)學(xué)院 軟件學(xué)院，重慶 400715）

壓縮感知理論使得采樣頻率與信號的內(nèi)容和結(jié)構(gòu)相關(guān)，在遠(yuǎn)低于Nyquist采樣定理的采樣頻率下對數(shù)據(jù)直接進(jìn)行壓縮采樣，為處理冗余數(shù)據(jù)做出了巨大貢獻(xiàn)。關(guān)于壓縮感知的基本理論，文章從信號的重構(gòu)算法、信號的稀疏基以及信號測量矩陣的設(shè)計3個方面詳細(xì)介紹。貪婪算法是重構(gòu)算法中效率最高的算法，文章介紹其最開始提出的比較經(jīng)典的兩種算法：匹配追蹤和正交匹配追蹤，并詳細(xì)給出了兩個算法的本質(zhì)思想、數(shù)學(xué)框架以及推導(dǎo)過程，也分析并證明了其收斂性。

壓縮感知；匹配追蹤；測量矩陣；正交匹配追蹤

Nyquist采樣定理是初始時信號處理的基本原理—它指出在采樣過程中只有用大于信號最高頻率兩倍的頻率進(jìn)行采樣，才能由采樣所獲得的信號精確重建出原信號。但是由于自然界的數(shù)據(jù)都存在局部低維結(jié)構(gòu)、周期性、對稱性等特點，傳統(tǒng)的固定采樣率的采樣方法必然存在大量的信息冗余，便會使硬件系統(tǒng)所需的采樣速率大大增加，而且也造成了信號帶寬的浪費。2006年，由Candes，Romberg, Tao和Donoho等人提出了壓縮感知理論（Compressed Sensing, CS），其核心思想就是把采樣與壓縮合并起來，對可稀疏表示的信號以較低的采樣率進(jìn)行壓縮采樣，并用與稀疏基不相干的測量矩陣將高維信號投影到一個低維空間上以獲得測量向量（即投影值），使用了較少的測量數(shù)據(jù)但實現(xiàn)了信號的精確重構(gòu)，達(dá)到了“少測量，巧計算”的目的。

1 壓縮感知理論

感知壓縮即采集較少的數(shù)據(jù)并從這些數(shù)據(jù)中解壓縮出大量原始信息，其先提條件：由于恢復(fù)原信號需要足夠多的對原信號的概要信息，因此采集到的少量數(shù)據(jù)中必須包含所需的全局信息，而且必須具有一種算法可以根據(jù)這些數(shù)據(jù)所包含的信息精確重建出原始信息。

1.1 信號的稀疏表示

時域內(nèi)的自然信號一般都不是稀疏的，因而直接對其進(jìn)行壓縮采樣勢必會造成硬件功率的浪費，但由于在某些變換域中可以將自然信號變?yōu)榭上∈璧模虼藟嚎s感知一般先通過某種變換域得到原始信號的稀疏表示，重構(gòu)時先重構(gòu)出原始信號的稀疏表示逼近值，再進(jìn)一步變換可得到原始信號的逼近值。設(shè)長度為N的信號X并用一組稀疏基= {,,…,}（為列向量）的線性組合來表示：

1.2 信號的測量矩陣

1.3 信號的重構(gòu)算法

壓縮感知理論的核心之一便是其重構(gòu)算法，重構(gòu)算法是指由M維的測量值y重構(gòu)出長度為N(M·N)的信號X的過程，如果原始信號X滿足兩個條件：X是可K稀疏并且X的感知矩陣滿足RIP準(zhǔn)則時，對（2）使的逆向求解S'=y 便是待估稀疏系數(shù)，然后從測量向量Y中將信號X精確無誤地恢復(fù)出來，一般通過范數(shù)求解最優(yōu)化問題是解碼最直接的方法：

2 貪婪算法之MP、OMP詳解

2.1 MP算法

用H表示Hilbert空間，把被表示的信號設(shè)為y，其長度為n，用一組向量構(gòu)成字典矩陣D，因為單位向量模為1，所以對其中的每個向量作歸一化處理，即MP算法基本操作步驟如下：

選擇與信號y最匹配的原子：將信號向量y與字典矩陣中每列（原子）做點乘運算，即求內(nèi)積，并且選擇內(nèi)積絕對值最大的一列，滿足如下所示，其中r0表示一個字典矩陣的列索引：

基于（4）式便可將信號y分解為兩部分（最匹配原子xr0的殘值和垂直投影分量），即：

將殘值R1f繼續(xù)進(jìn)行上述步驟1）中同樣的操作，經(jīng)過K步分解后，信號y被分解為：

其中R0f=y，在第一次分解過程中，不難發(fā)現(xiàn)三個向量構(gòu)成了一個直角三角形，由三角形性質(zhì)可得其滿足勾股定理，這個規(guī)律在后面的迭代過程中依舊滿足，又因為在（6）中f與正交，由此可得出：，因此MP算法是收斂的。但由于MP迭代結(jié)果大多情況下是次優(yōu)解，因此對MP算法進(jìn)行改進(jìn)，即OMP算法。

2.2 OMP算法

OMP算法對MP算法做了改進(jìn)，雖然稍有不同，但其性能的確提高了不少，首先對分解中的每一步都將已選擇的全部原子進(jìn)行正交化處理，即使前面的每個分量與OMP算法的殘值具有正交性，這使得在相同的精度要下，OMP收斂速度相比MP效率更高。其k階模型如下：

同理可得k+1階模型如下，用k+1階模型減去k階模型可得：

由于字典矩陣D中的原子不都是正交的，因此構(gòu)建一個輔助模型來表示字典矩陣D的xrk+1項對前k個項(n=1,2,…,k) xn的依賴，如下所示：

3 結(jié)語

壓縮感知是一種全新的數(shù)據(jù)采集理論，理論上要實現(xiàn)原始信號的精確重構(gòu)，只需采集少量概要的信息便可實現(xiàn)原始信號的精確重構(gòu)，對處理可壓縮或大規(guī)模稀疏的數(shù)據(jù)作出了巨大貢獻(xiàn)，而且即使原始信號不是稀疏的也可以將其在其他變換域中稀疏并加以壓縮采樣。本文從壓縮感知的3個方面闡述了其基礎(chǔ)理論，且詳細(xì)介紹了重構(gòu)算法中貪婪算法的其中兩種算法，即MP，OMP，包括算法的公式推導(dǎo)證明等。這兩個算法都采用一次解出一個（或多個）待重建信號的構(gòu)成要素，然后使用迭代的方式找出需重建信號的元素。

[1]楊真真，楊震，孫林慧.信號壓縮重構(gòu)的正交匹配追蹤類算法綜述[J].信號處理，2013（4）：486-496.

[2]BARANΙUK R.Compressive sensing[C].Conference on Ιnformation Sciences & Systems, 2008（4）：iv-v.

[3]方紅，楊海蓉.貪婪算法與壓縮感知理論[J].Acta Automatica Sinica，2011（12）：1413-1421.

[4]盧雁，吳盛教，趙文強.壓縮感知理論綜述[J].計算機與數(shù)字工程，2012（8）：12-14.

[5]尹宏鵬，劉兆棟，柴毅，等.壓縮感知綜述[J].控制與決策，2013（10）：1441-1445.

Theory of compressed perception theory and two greedy algorithms

Li Yingting
（Software Engineering College of Computer and Ιnformation Science College in Southwest University, Chongqing 400715, China）

The compression perception theory makes the sampling frequency directly related to the content and structure of the signal. Ιt compresses the data directly at the sampling frequency far below the Nyquist sampling theorem, making a great contribution to the processing of redundant data. The basic theory of compression perception is introduced in details from three aspects: signal reconstruction algorithm, signal sparse base and signal measurement matrix design. Greedy algorithm is the highest in the reconstruction algorithm efficiency of the algorithm. This paper has introduced two classic algorithms proposed at the beginning: matching pursuit and orthogonal matching pursuit, given a detailed description of the nature, mathematical framework and derivation process of two algorithms, as well as analyzed and proved its convergence.

compressed sensing; matching pursuit; measurement matrix; orthogonal matching pursuit

李盈婷（1996— ），女，甘肅古浪。