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

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

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

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

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

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

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

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

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

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

1 壓縮感知簡(jiǎn)介

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

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

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

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

1.1 信號(hào)稀疏表示

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

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

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

1.2 觀測(cè)（測(cè)量）矩陣

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

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

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

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

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

1.3 稀疏重構(gòu)

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

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

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

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

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

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

貪婪算法是通過(guò)每次迭代過(guò)程中的局部最優(yōu)解來(lái)實(shí)現(xiàn)對(duì)原始信號(hào)的逼近，代表性的貪婪算法有正交匹配追蹤（Orthogonal Matching Pursuit，OMP）算法及其對(duì)它的一系列改進(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ù)，對(duì)于算法的收斂速度有很好的提高，但是重構(gòu)效果相對(duì)較差，需要的測(cè)量數(shù)也較多。

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

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

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

2 信號(hào)重構(gòu)實(shí)驗(yàn)

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

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

核心算法步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文介紹了壓縮感知理論，并采用OMP算法實(shí)驗(yàn)驗(yàn)證了基于壓縮感知的信號(hào)重構(gòu)，OMP算法作為貪婪算法的代表，對(duì)于維數(shù)較低的小尺度信號(hào)問(wèn)題運(yùn)算速度很快，但是對(duì)于存在噪聲的大尺度信號(hào)問(wè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]劉亞新，趙瑞珍，胡紹海，等.用于壓縮感知信號(hào)重建的正則化自適應(yīng)匹配追蹤算法[J].電子信息學(xué)報(bào)，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稿件編號(hào)201211161

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

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