基于壓縮感知的信號重構(gòu)

薛 男，凌 霖，陶曉洋，曹佩佩

（江蘇科技大學(xué) 電子信息學(xué)院，江蘇 鎮(zhèn)江 212003）

基于壓縮感知的信號重構(gòu)

薛 男，凌 霖，陶曉洋，曹佩佩

（江蘇科技大學(xué) 電子信息學(xué)院，江蘇 鎮(zhèn)江 212003）

壓縮感知是針對稀疏或可壓縮信號，在采樣的同時即可對信號數(shù)據(jù)進(jìn)行適當(dāng)壓縮的新理論，采用該理論，可以僅需少量信號的觀測值來實現(xiàn)精確重構(gòu)信號。文中概述了CS理論框架及關(guān)鍵技術(shù)問題，介紹了信號稀疏表示、觀測矩陣和重構(gòu)算法。最后仿真實現(xiàn)了基于壓縮感知的信號重構(gòu)，并對正交匹配追蹤（OMP）重構(gòu)算法性能作了分析。

壓縮感知；稀疏性；信號重構(gòu)；正交匹配追蹤

奈奎斯特采樣定理指出：信號的采樣頻率不得低于信號帶寬的2倍，否則就會出現(xiàn)信息的丟失。因此在寬帶模擬數(shù)字化過程中往往需要非常高的采樣頻率，同時又要針對獲取的大量原始采樣信息進(jìn)行數(shù)據(jù)壓縮和傳輸，這就對存儲資源、傳輸資源和計算資源都造成了極大程度的浪費(fèi)。而且，由于在實際應(yīng)用中電子器件（如 A/D轉(zhuǎn)換器等）的物理特性約束問題，提高采樣頻率的代價極其巨大。另一方面，隨著現(xiàn)代信息技術(shù)的高速發(fā)展和人們對信息數(shù)據(jù)量的需求的不斷增加，人們對傳統(tǒng)的信號處理框架要求的采樣和處理速度都提出了更高的要求，于是給出一個新問題：能否建立一個新的信號處理框架，在保證信息沒有損失的同時，用遠(yuǎn)低于奈奎斯特采樣定理所要求的采樣頻率對信號進(jìn)行采樣，并且能夠精確的恢復(fù)信號？假如這個問題得到解決，就可以顯著的減小數(shù)據(jù)處理、傳輸和存儲的代價，進(jìn)一步降低信號處理的時間成本和器件成本。

在 2004年 ，Candès[1]、Romberg[2]、Tao[3]和 Donoho[4]針 對 稀疏性信號，在信號逼近和稀疏分解等理論的基礎(chǔ)上建立了壓縮感知（Compressive Sensing or Compressive Sampling， CS）理論框架，該理論在隨后的幾年間迅速發(fā)展，從而為解決上述問題奠定了堅實的理論基礎(chǔ)。與傳統(tǒng)方式不同，壓縮感知理論框架是以空間變換為基礎(chǔ)，以隨機(jī)觀測矩陣為手段，以優(yōu)化求解作為信號恢復(fù)的方法。壓縮感知理論可以用比傳統(tǒng)方法更少的采樣數(shù)目去精確恢復(fù)特定的信號或圖像，避免了大量的數(shù)據(jù)集合而且能在獲取信息的同時直接建立數(shù)據(jù)壓縮。

1 壓縮感知簡介

不同于傳統(tǒng)的均勻采樣，壓縮感知的核心是線性測量過程，設(shè)x（n）為傳統(tǒng)采樣得到的信號，長度為N，通過壓縮感知可直接得到 y（m），長度為 M（M＜N），它們的關(guān)系為 y=Φx，其中Φ稱為傳感矩陣或測量矩陣，大小為M×N，y可以看作是信號關(guān)于測量矩陣Φ的測量值，測量過程如圖1所示。

圖1 壓縮感知的線性測量過程（系數(shù)s有4個非零元）Fig.1 Linear measurement process of CS（coefficient s has four nonzero element）

從y（m）恢復(fù)出原信號 x（n）的過程，稱為基于壓縮感知的信號稀疏重構(gòu)。

壓縮感知理論指出，如果某個集合中只有少量的非零元素，就稱這個集合具有稀疏性，如果一個自然信號在某個變換基上的分解表示結(jié)果呈現(xiàn)出稀疏性，就稱這一信號具有稀疏性。只要信號在某個特定的變換域內(nèi)具有稀疏性，那么就可以通過一個與變換基不相干的觀測基將信號投影到低維空間中，然后通過對這個優(yōu)化問題的求解就可以高精度重構(gòu)出原始信號。

1.1 信號稀疏表示

式中，st=（x，Ψt），s和 x是 L×1 維矩陣，Ψ 為 L×L 矩陣，如果 s僅有 K（K＜＜L）個非零元（或取較大的值），而其他 N－L個系數(shù)全為零（或取值很?。﹦t稱x是K－稀疏的，Ψ為x的稀疏基。

通常情況下，信號無法滿足嚴(yán)格稀疏的條件（即信號在稀疏域中只有K個非零系數(shù)）。通過選擇一個合適的稀疏基Ψ，能使稀疏系數(shù)的個數(shù)最大限度的減少。從傅立葉變換開始，以及后來陸續(xù)出現(xiàn)的K－L變換、小波變換和目前正處于研究熱點(diǎn)的超小波變換，所有的這些變換都是根據(jù)信號的結(jié)構(gòu)特性來稀疏的表示它。

近年來，人們發(fā)現(xiàn)信號可以通過加入冗余來實現(xiàn)稀疏化，因而出現(xiàn)一種被稱為過完備原子庫的冗余系統(tǒng)。這個過完備原子庫中的原子個數(shù)要遠(yuǎn)大于信號長度，并且最大程度的符合被逼近信號的內(nèi)在結(jié)構(gòu)。因此，可以從原子庫中找到具有最佳線性組合的一系列原子來表示目標(biāo)信號，實現(xiàn)信號在這些原子下的稀疏表示。

1.2 觀測（測量）矩陣

式中：x是N×1矩陣，y是M×1矩陣，Φ是M×N的測量矩陣 。 將式（1）代入（2），有:

式中：Θ=ΦΨ是M×N矩陣。

測量值維數(shù)M遠(yuǎn)遠(yuǎn)小于信號維數(shù)N，求解式（3）的逆問題是一個病態(tài)問題，所以無法直接從的M個測量值中解出信號x。由于式（3）中s是K稀疏的，即僅有K個非零系數(shù)，而且K＜M＜＜N，那么利用信號稀疏分解理論中已有的稀疏分解算法，可以通過求解式（3）的逆問題得到稀疏系數(shù)s，再代回（1）進(jìn)一步得到信號x。為了保證算法的收斂性，使得K個系數(shù)能夠由M個測量值準(zhǔn)確的恢復(fù)，式（3）中矩陣Θ必須滿足受限等距特性（RIP）準(zhǔn)則，即對于任意有嚴(yán)格K稀疏（可壓縮情況時，要求是3K）的矢量v，矩陣Θ都能保證如下不等式成立：

式中ε>0。RIP準(zhǔn)則的一種等價的情況是測量矩陣Φ和稀疏矩陣Ψ滿足不相關(guān)性的要求。當(dāng)測量數(shù)M滿足M≥K*log（N/K）時信號能實現(xiàn)較好的重構(gòu)。

實際測量中稀疏基Ψ可能會因信號的不同而改變，因此希望找到對任意的稀疏基Ψ都能滿足和測量基Φ不相關(guān)。對一維信號而言，測量矩陣Φ選取服從高斯分布的基矢量能保證和任意稀疏基Ψ不相關(guān)的概率很高，類似的矩陣還有Bernouli矩陣等。

1.3 稀疏重構(gòu)

定義一個向量 x=[x（1），x（2），…，x（L）]T的 l－范數(shù)為：

當(dāng)l=0，得到0－范數(shù)，表示向量x中非零項的數(shù)目。

信號重構(gòu)最直接的方法就是在l0范數(shù)下求解：

但是，基于l0范數(shù)的優(yōu)化問題是一個NP問題，計算量大得根本無法直接求解。從數(shù)學(xué)角度分析，這和稀疏分解問題非常相似，所以現(xiàn)有的稀疏分解算法可以直接應(yīng)用到信號重構(gòu)中，通常情況下，將其轉(zhuǎn)化為在l1范數(shù)下求解，這就將一個非凸優(yōu)化問題轉(zhuǎn)化為凸優(yōu)化的問題。

以上考慮的都是等式約束，然而實際中，測量過程可能會引入噪聲，于是y=Φs變?yōu)閥=Φx+n，其中n為高斯白噪聲。因此，上述優(yōu)化問題中的等式約束需要改為不等式約束，即:

目前常用的重構(gòu)算法多是基于最優(yōu)化方法和匹配跟蹤方法構(gòu)造的，可粗略地歸納為以下3類：針對l0范數(shù)最小提出的一系列貪婪算法，針對l1范數(shù)最小提出的線性規(guī)劃最優(yōu)化算法，以及統(tǒng)計優(yōu)化重構(gòu)算法。

貪婪算法是通過每次迭代過程中的局部最優(yōu)解來實現(xiàn)對原始信號的逼近，代表性的貪婪算法有正交匹配追蹤（Orthogonal Matching Pursuit，OMP）算法及其對它的一系列改進(jìn)算法，如正則化正交匹配追蹤[5]（Regularized Orthogonal Matching Pursuit， ROMP）， 最 優(yōu) 正 交 匹 配 追 蹤 （Optimized Orthogonal Matching Pursuit，OOMP），稀疏自適應(yīng)匹配追蹤（Sparsity Adaptive Matching Pursuit， SAMP），壓縮采樣匹配追蹤（Compressive Sampling Matching Pursuit，CoSaMP）算法等。該類算法在正交方向?qū)ふ曳橇阆禂?shù)，對于算法的收斂速度有很好的提高，但是重構(gòu)效果相對較差，需要的測量數(shù)也較多。

針對l1范數(shù)最小的線性規(guī)劃最優(yōu)化算法主要為基追蹤法（Basis Pursuit，BP）， 梯度投影稀疏重構(gòu) （Gradient Projection for Sparse Reconstruction，GPSR），最小絕對收縮和選擇算子（Least Absolute Shrinkage And Selection Operator， LASSO），L1_maggic等。此類方法重構(gòu)效果較好，需要的測量數(shù)也相對較少，但是其速度慢，對于解決大尺度問題難以實際應(yīng)用。

另外，以 Sparse Bayesian為代表的統(tǒng)計優(yōu)化算法也在應(yīng)用，其性能介于前兩者之間。

因此，構(gòu)建快速有效、穩(wěn)定且具有一定魯棒性的重構(gòu)算法是當(dāng)前壓縮感知理論中亟待解決的一個問題。

2 信號重構(gòu)實驗

以正交匹配追蹤算法（OMP）[6]為例實現(xiàn)基于壓縮感知的信號重構(gòu)。

正交匹配追蹤算法本質(zhì)思想是：以貪婪迭代的方法選擇Φ的列，使得在每次迭代中所選擇的列與當(dāng)前的冗余向量最大程度地相關(guān)，從測量向量中減去相關(guān)部分并反復(fù)迭代，直到迭代次數(shù)達(dá)到稀疏度K，強(qiáng)制迭代停止。

核心算法步驟如下：

輸入：測量矩陣Φ，采樣向量y，稀疏度K；

初始化：殘差 r0=y，索引集 Λ0=?，t=1；

循環(huán)執(zhí)行步驟1－5：

步驟1）：找出殘差r和測量矩陣的列φj內(nèi)積中最大值所對應(yīng)的腳標(biāo) λ，即 λt=arg maxj=1…N|＜rt－1，φj>|；

步驟5）：判斷是否滿足t>K，若滿足，則停止迭代；若不滿足，則執(zhí)行步驟1）。

取一個一維信號，由4個單一頻率正弦波合成，正弦波信號頻率分別為 f1=50 Hz，f2=100 Hz，f3=200 Hz，f4=400 Hz，信號長度N=256。通過快速傅里葉變換得出，信號稀疏度K=7，則測量數(shù)M≥K*log（N/K），取M=56。信號的測量矩陣為Φ=M×N的高斯隨機(jī)矩陣。

如圖2為無噪情況下原信號和重構(gòu)信號的效果對比圖。圖中，橫坐標(biāo)指信號的長度N，縱坐標(biāo)為信號的幅度值。

圖2 一維信號重構(gòu)效果對比圖Fig.2 One dimensional signal reconstruction effect comparison

計算重構(gòu)信號與原信號的誤差發(fā)現(xiàn)相對誤差值僅為e－015數(shù)量級，的確實現(xiàn)了精確重構(gòu)，但是當(dāng)在原信號中加入噪聲后，OMP算法精確重構(gòu)信號的概率隨噪聲增大逐漸降低，相對誤差值也明顯增大，甚至無法重構(gòu)原信號。

進(jìn)一步，為研究OMP算法對于不同測量矩陣維數(shù)M及稀疏度下的重構(gòu)概率情況，進(jìn)行蒙特卡羅仿真，以重構(gòu)絕對誤差小于1e－9進(jìn)行成功重構(gòu)概率計算，仿真結(jié)果如圖3所示。

圖3 重構(gòu)概率變化圖Fig.3 Figure of reconstruction probability variation

從圖中可以看出，信號稀疏度越低對觀測矩陣維數(shù)M的要求越低，更易實現(xiàn)精確重構(gòu)。

OMP算法保證了每次迭代的最優(yōu)性，減少了迭代的次數(shù)。但是，它在每次迭代中僅選取一個原子來更新原子集合，這樣必然會付出巨大的重建時間代價。迭代的次數(shù)與稀疏度K或采樣個數(shù)M密切相關(guān)，隨其增大，耗時也將大幅增加。因此之后出現(xiàn)了許多改進(jìn)的匹配追蹤算法，如ROMP、StOMP、CoSaMP等等。

3 結(jié)束語

本文介紹了壓縮感知理論，并采用OMP算法實驗驗證了基于壓縮感知的信號重構(gòu)，OMP算法作為貪婪算法的代表，對于維數(shù)較低的小尺度信號問題運(yùn)算速度很快，但是對于存在噪聲的大尺度信號問題，重構(gòu)結(jié)果不是很精確，也不具有魯棒性。

[1]CandèsE.Compressive sampling proceedingsofthe international congress of mathematicians[C].Madrid，Spain，2006（3）:1433－1452.

[2]Candès E，Romberg J，Tao T.Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory，2006，52（2）:489－509.

[3]Candès E J，Tao T.Near optimal signal recovery from random projections:universal encoding strategies[J].IEEE Trans.Info.Theory，2006，52（12）:5406－5425.

[4]Donoho D L.Compressed sensing [J].IEEE Trans.on Information Theory,2006，52（4）:1289－1306.

[5]劉亞新，趙瑞珍，胡紹海，等.用于壓縮感知信號重建的正則化自適應(yīng)匹配追蹤算法[J].電子信息學(xué)報，2010，32（11）:2714-2716.

LIU Ya-xin，ZHAO Rui-zhen，HU Shao-hai，et al.Regularized adaptive matching pursuit algorithm for signal reconstruction based on compressive sensing[J].Journal of Electronics&Information Technology，2010，32（11）:2714-2716.

[6]Tropp J，Gilbert A.Signal recovery from random measurements via orthogonal matching pursuit[J].Transactions on Information Theory，2007，53（12）：4655-4666.

Signal reconstruction based on compressive sensing

XUE Nan，LING Lin，TAO Xiao-yang，CAO Pei-pei
（School of Electronic&Information， Jiangsu University of Science and Technology， Zhenjiang 212003， China）

Compressive sensing （CS）is a novel signal sampling theory under the condition that the signal is sparse or compressible.It has the ability of compressing a signal during the process of sampling.Using compressive sensing theory，one can reconstruct sparse or compressible signals accurately from a very limited number of measurements.This paper surveys the theoretical framework and the key technical problems of compressed sensing and introduces signal sparse representation，measurement matrix and reconstruction algorithms.In the end，realizes signal reconstruction and analyses the performances of Orthogonal Matching Pursuit（OMP）reconstruction algorithms.

compressed sensing； sparsity； signal reconstruction； OMP

TN911.7

A

1674－6236（2013）07-0034-03

2012-11-19稿件編號201211161

江蘇科技大學(xué)本科生創(chuàng)新計劃專項經(jīng)費(fèi)資助（103022005）

薛 男（1991—），男，江蘇鹽城人。研究方向：信號與信息處理。