王紅亮，王 帥，劉文怡

（中北大學(xué)電子測(cè)試技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 儀器科學(xué)與動(dòng)態(tài)測(cè)試教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030051）

0 引言

隨著信息技術(shù)的高速發(fā)展，需要傳輸?shù)臄?shù)據(jù)量和采樣頻率越來(lái)越大，因此，科學(xué)家遇到“信息瓶頸”的難題：采集時(shí)得到的海量數(shù)據(jù)進(jìn)行傳輸和存儲(chǔ)，讓目前的通信系統(tǒng)越來(lái)越難以承受［1］。傳統(tǒng)的香農(nóng)－奈奎斯特采樣定理要求采樣頻率必須大于信號(hào)最高頻率的兩倍以上，才能較好恢復(fù)出原信號(hào)，雖然實(shí)現(xiàn)了信號(hào)的采集、壓縮和恢復(fù)，但采集數(shù)據(jù)和頻率的急劇增加，使這種方法的缺點(diǎn)尤為突出：壓縮過(guò)程中丟棄了絕大部分采集的數(shù)據(jù)，增加了額外的存儲(chǔ)和傳輸設(shè)備。因此，人們一直尋找解決的辦法：采集頻率更低，產(chǎn)生的數(shù)據(jù)量更小，并且能很好地恢復(fù)原信號(hào)。

近年，Donoho、Candès、Romberg和 Tao在泛函數(shù)分析、矩陣?yán)碚?、統(tǒng)計(jì)概率論等基礎(chǔ)上提出了新型信號(hào)壓縮采樣的理論，稱(chēng)之為compressive sensing or compressed sensing（簡(jiǎn)稱(chēng) CS），中文翻譯為壓縮感知［2－5］。CS一經(jīng)提出便吸引許多科學(xué)家的關(guān)注，因?yàn)樗鉀Q了香農(nóng)－奈奎斯特采樣定律在信號(hào)采集中的不足，而且具有低采樣率、低速率和重構(gòu)質(zhì)量高等特點(diǎn)，不僅顯著降低采集設(shè)備和存儲(chǔ)設(shè)備的設(shè)計(jì)難度，而且減少設(shè)備使用數(shù)量。目前，在國(guó)內(nèi)壓縮感知理論已成為研究熱點(diǎn)，許多科研機(jī)構(gòu)和大學(xué)都投入大量的人力、物力開(kāi)展這方面研究：西安電子科技大學(xué)最先建立課題組并將壓縮感知理論應(yīng)用在超寬帶雷達(dá)信號(hào)檢測(cè)［6－8］，取得了非常好的效果，中國(guó)科學(xué)院在2010年開(kāi)設(shè)壓縮感知這門(mén)課，而且研究出基于壓縮感知的探地雷達(dá)數(shù)據(jù)壓縮采集方法，實(shí)現(xiàn)了雷達(dá)信號(hào)的實(shí)時(shí)采樣數(shù)據(jù)壓縮［9］。另外，北京航空航天大學(xué)、華南理工大學(xué)、解放軍理工大學(xué)等單位也在積極探索。

1 壓縮感知理論

壓縮感知的理論分為三個(gè)部分：構(gòu)建稀疏矩陣、設(shè)計(jì)觀測(cè)矩陣和重構(gòu)原始信號(hào)。其中判斷信號(hào)是否具有稀疏性是實(shí)現(xiàn)壓縮感知的前提；觀測(cè)矩陣的設(shè)計(jì)是其重要組成部分，它的設(shè)計(jì)不僅關(guān)系到壓縮和采樣過(guò)程的快慢，而且影響重構(gòu)信號(hào)的準(zhǔn)確性；重構(gòu)原始信號(hào)是其核心部分，因此，重構(gòu)算法是否合適決定恢復(fù)原始信號(hào)質(zhì)量的好壞。

1.1 數(shù)學(xué)模型

假定有限實(shí)值離散空間為RN，其中ψi（i＝1，2，…，N）是RN的基向量，則空間內(nèi)任意信號(hào)x（N個(gè)信息量）表示為：

式（1）中Ψ ＝ ［ψ1，ψ2，…，ψN］，Ψ 是由基向量ψi構(gòu)成的N×N正交矩陣，如圖1所示，矩陣s是信號(hào)x在Ψ域的稀疏后的矩陣。

然后采用與Ψ相干性較小的觀測(cè)矩陣Φ（M×N，M?N）對(duì)信號(hào)進(jìn)行線性投影，過(guò)程如圖2所示，得到觀測(cè)矩陣y：

觀測(cè)值y是M階列矩陣，注意：在此過(guò)程中觀測(cè)值y不是原信號(hào)的采樣值，而是信號(hào)x在觀測(cè)矩陣Φ上的投影值。由于信號(hào)x是可稀疏的矩陣，所以式（2）可以表示為：

式（3）中Θ（M×N矩陣）稱(chēng)為感知矩陣。

圖1 信號(hào)稀疏矩陣示意圖Fig.1 Sparse Matrix of Signal

圖2 觀測(cè)過(guò)程示意圖Fig.2 Measurement Process

從M維觀測(cè)值y準(zhǔn)確地恢復(fù)原始信號(hào)x最直接的方法是轉(zhuǎn)化為L(zhǎng)0范數(shù)的最優(yōu)化問(wèn)題：

但直接求式（4）的解是個(gè)NP－h(huán)ard問(wèn)題［5］：利用｜s｜｜0雖然可以得出稀疏后的矩陣s內(nèi)有多少個(gè)非零信息，卻不知道信息的具體位置，用枚舉法有個(gè)解（k和N 分別是信號(hào)x的稀疏度和信息總量），而N的值一般以萬(wàn)為單位，所以，這種方法找出最稀疏解的難度很大。但Donoho認(rèn)為最優(yōu)化問(wèn)題與信號(hào)的稀疏分解類(lèi)似，從信號(hào)稀疏分解的相關(guān)理論中尋找更有效的求解途徑，證明最小L0范數(shù)下在一定條件下和最小L1范數(shù)具有等價(jià)性可以找到最稀疏的解。所以，式（4）可轉(zhuǎn)化為L(zhǎng)1最小范數(shù)下的最優(yōu)化問(wèn)題：

1.2 壓縮感知約束條件

壓縮感知實(shí)現(xiàn)需要滿(mǎn)足一些條件：信號(hào)在某個(gè)變換域是可稀疏，稀疏矩陣和觀測(cè)矩陣盡量不相干，感知矩陣滿(mǎn)足RIP準(zhǔn)則等。

1.2.1 稀疏信號(hào)

信號(hào)x在正交基Ψ稀疏的變換為：s＝ΨTx，當(dāng)0＜p＜2，實(shí)數(shù)V＞0時(shí)，這些系數(shù)滿(mǎn)足：則說(shuō)明x在正交矩陣Ψ變換域是稀疏的，如果矩陣s中有k個(gè)非零元素（或大系數(shù)），則稱(chēng)s為x的k階稀疏矩陣（稀疏度為k），且k?N。

1.2.2 相干性

假設(shè)有兩組正交矩陣Ψ ＝ ［ψ1，ψ2，…，ψN］，ф＝［φ1，φ2，…，φN］，兩組正交矩陣的相干系數(shù)為：

其中φi，ψj是矩陣Φ，Ψ內(nèi)的第i列和第j列矩陣，根據(jù)線性代數(shù)所學(xué)知識(shí)得出相關(guān)系數(shù)的范圍在1≤μ2（Φ，Ψ）≤N，如果這兩個(gè)矩陣相干系數(shù)較小，則矩陣之間的相干性就越小，反之，相干性就越大。正交矩陣Φ，Ψ可做壓縮感知的稀疏矩陣和觀測(cè)矩陣，當(dāng)μ2（Φ，Ψ）＝N時(shí)，壓縮感知就變成傳統(tǒng)的壓縮采樣。文獻(xiàn)［5］推導(dǎo)出M的取值范圍：

根據(jù)前幾年研究CS的經(jīng)驗(yàn)，當(dāng)M≥4k時(shí)，其稀疏性，相干性和重構(gòu)信號(hào)的質(zhì)量都符合預(yù)期［10］。

1.2.3 RIP準(zhǔn)則

有限等距準(zhǔn)則（Restricted Isometry Property，RIP）是CS理論感知矩陣Θ需要滿(mǎn)足重要條件，CS理論的初衷是有效處理復(fù)雜信號(hào)［11］，所以，RIP 準(zhǔn)則適合的范圍以自然界信號(hào)為主。假設(shè)一個(gè)復(fù)雜矩陣Φ（M×N，M?N），P是Q的子集，其中集合Q＝｛1，2，…，N｝，Φp是Φ 中隨機(jī)抽取P 個(gè)列向量組成M×P矩陣

式（6）中矩陣sT為信號(hào)稀疏矩陣s的轉(zhuǎn)置，φj為Φp的列向量，Candès and Tao［5］定義k階稀疏矩陣的限制系數(shù)RIC為常數(shù)δk且δk∈（0，1）需要滿(mǎn)足的條件是：

Candès在文獻(xiàn)［12］中證明：當(dāng)P＝2k時(shí)，L1范數(shù)代替L0范數(shù)需要滿(mǎn)足的條件δ2s＜0.414，但是判斷矩陣是否滿(mǎn)足RIP準(zhǔn)則，以及RIC的計(jì)算都是非常困難的，因此相繼出現(xiàn)了利用其他理論如相關(guān)性判別理論［13］和矩陣Spark判別理論［14］等驗(yàn)證感知矩陣。

1.3 含噪聲的壓縮感知模型

CS理論應(yīng)用時(shí)，信號(hào)常常伴隨著噪聲和其他因素的干擾，Candès在文獻(xiàn)［3］［12］提出含噪聲的CS模型：

其中z為隨機(jī)噪聲或其他因素干擾產(chǎn)生的變量矩陣，目前，含有噪聲處理的方法主要有基追蹤降噪法［15］以及轉(zhuǎn)化為二次規(guī)劃問(wèn)題解決原始信號(hào)恢復(fù)［16］。若式（7）滿(mǎn)足RIP準(zhǔn)則且－1，則可轉(zhuǎn)化為范數(shù)L1最優(yōu)化問(wèn)題：

式（8）中ε稱(chēng)為誤差值，是理想觀測(cè)值與實(shí)際觀測(cè)值的差，并且方程的解s′滿(mǎn)足：

sk為原信號(hào)稀疏矩陣s的k階稀疏逼近，b1，b2為較小的常量，式（8）中的ε是無(wú)噪聲下的自身誤差值，式（9）中的ε是有噪聲和干擾的情況下產(chǎn)生的誤差。

1.4 壓縮感知與香農(nóng)采樣的區(qū)別

壓縮感知采集方法并不是對(duì)數(shù)據(jù)直接進(jìn)行采集，而是通過(guò)一組特定波形去感知信號(hào)，即將信號(hào)投影到給定波形上（衡量與給定波形的相關(guān)度），感知到一組壓縮數(shù)據(jù)，最后利用最優(yōu)化的方法實(shí)現(xiàn)對(duì)壓縮數(shù)據(jù)解密，估計(jì)出原始信號(hào)的重要信息［17］。

圖3 壓縮感知和香農(nóng)采樣過(guò)程示意圖Fig.3 Process of Compressed Sensing and Shannon sampling

如圖3所示，香農(nóng)采樣是線性抽樣，所以，得到的采樣值接近于N個(gè)，經(jīng)過(guò)低通濾波器濾除絕大部分，最后只是將剩下的k個(gè)抽樣值（k?N）傳輸或存儲(chǔ)，在恢復(fù)信號(hào)時(shí)，利用k個(gè)采樣值通過(guò)帶限內(nèi)插等方法恢復(fù)信號(hào)xr，其中xr中有N個(gè)值。但在這整個(gè)過(guò)程有個(gè)缺點(diǎn)：采樣時(shí)得到的樣本值，在壓縮過(guò)程中丟棄了絕大部分只剩下k個(gè)，所以，采樣過(guò)程做了很多的“無(wú)用功”。

壓縮感知和香農(nóng)采樣的區(qū)別主要在兩方面，一方面，CS是非線性和非自適應(yīng)性采樣，不會(huì)隨輸入信號(hào)的頻率不同而改變輸入裝置，不論輸入的是聲信號(hào)，圖像信號(hào)還是視頻信號(hào)等都能恢復(fù)原信號(hào)，只是恢復(fù)信號(hào)的質(zhì)量參差不齊。另一方面，CS的采樣和壓縮同時(shí)進(jìn)行，解決了香農(nóng)采樣中先采集再丟棄的問(wèn)題。

細(xì)心觀察圖4和圖5發(fā)現(xiàn)：香農(nóng)采樣其實(shí)是壓縮感知的特殊形式，只是其觀測(cè)矩陣是單位矩陣（脈沖函數(shù)），壓縮感知的觀測(cè)矩陣是行數(shù)遠(yuǎn)小于列數(shù)，但其獨(dú)特的設(shè)計(jì)正是壓縮感知的優(yōu)點(diǎn)：信號(hào)與觀測(cè)矩陣相乘最終得到的觀測(cè)矩陣y遠(yuǎn)小于原信號(hào)。壓縮和采樣在同一過(guò)程，避免了先采樣再濾除的問(wèn)題。

圖4 香農(nóng)采樣的矩陣示意圖Fig.4 Matrix of Shannon sampling

圖5 壓縮感知采樣過(guò)程示意圖Fig.5 Sampling Process of Compressed Sensing

2 壓縮感知實(shí)現(xiàn)方法

目前，國(guó)內(nèi)外學(xué)者已經(jīng)提出許多壓縮感知實(shí)現(xiàn)的方法，本章將這些方法進(jìn)行歸類(lèi)介紹。

2.1 信號(hào)的稀疏

壓縮感知模型的前提是信號(hào)在變換域是否稀疏，因此，稀疏矩陣的選擇影響著信號(hào)重構(gòu)質(zhì)量的好壞。經(jīng)過(guò)幾十年的發(fā)展，信號(hào)稀疏已經(jīng)提出多種表示方法，如圖6所示，主要分為三大類(lèi)。第一類(lèi)是正交基矩陣，利用Fourier變換、離散余弦變換 （Discrete Cosine Transform，DCT）和小波變換（Wavelet）等正交基變換稀疏信號(hào)。

第二類(lèi)是多尺度幾何分析法（或者超小波變換法），其中Ridgelet［18］，Curvelet［19］和Contourlet［20］等方法應(yīng)用較多。

在自然圖像中包含有大量的紋理特征，線奇異性表現(xiàn)比較突出，小波變換等方法達(dá)不到最優(yōu)的逼近，所以，圖像的稀疏就需要其他更有效的方法。Candès等人在1998年提出了變換脊波變換（Ridgelet）以及在此基礎(chǔ)提出曲波變換（Curvelet）。Ridgelet變換是沿脊線刻畫(huà)直線的奇異性，能有效地表示直線的奇異性特征，具有直線奇異性的多變量函數(shù)有良好的稀疏性，但對(duì)于圖像曲線邊緣的描述，其稀疏逼近性能只相當(dāng)于小波變換，不具有最優(yōu)的非線性逼近稀疏，而且曲線奇異性仍是一個(gè)曲線，不是一個(gè)點(diǎn)，對(duì)于奇異性小波的表示將不是稀疏的。

圖6 稀疏矩陣的方法示意圖Fig.6 Achieve Methods of Sparse Matrix

Curvelet變換的實(shí)現(xiàn)是通過(guò)一種特殊的濾波過(guò)程和多尺度Ridgelet變換，而且在所有可能的尺度上進(jìn)行Ridgelet變換，這樣的曲線波能自適應(yīng)地“跟蹤”該奇異曲線，從而達(dá)到非常好的稀疏特性，此方法相對(duì)于小波變換的最大優(yōu)點(diǎn)是具有高度的各向異性，所以，Curvelet變換能更稀疏表達(dá)圖像信息。

Do等人提出的Contourlet變換是一種多分辨率、局域性和多方向的稀疏表示方法，用類(lèi)似于輪廓段的基結(jié)構(gòu)稀疏圖像，Contourlet變換基的支撐區(qū)間是隨尺度而變化的“長(zhǎng)條形結(jié)構(gòu)”，具有方向性和各向異性，從而使表示圖像邊緣的Contourlet系數(shù)能量更加集中，相比于小波變換Contourlet變換能更“稀疏”地表示圖像。

正交基變換的缺點(diǎn)是：信號(hào)的稀疏變換唯一，如果正交基選擇不合適，不能得到最稀疏的矩陣，進(jìn)而影響信號(hào)重構(gòu)，同時(shí)這類(lèi)方法對(duì)高維信號(hào)如圖像和視頻信號(hào)等不適用。多尺度幾何分析法以“最優(yōu)”圖像表示理論為基礎(chǔ)，主要解決了高維空間數(shù)據(jù)稀疏表示的問(wèn)題，卻僅對(duì)高維信號(hào)有很好的效果，一維信號(hào)不能得到最稀疏的解。

針對(duì)上述兩類(lèi)方法的優(yōu)缺點(diǎn)，由Mallat和Zhang在1993年提出了全新的稀疏理論——冗余字典（或稱(chēng)過(guò)完備字典），而且指出冗余字典對(duì)于信號(hào)稀疏表示的必要性和重要性，最后，介紹了匹配追蹤（Matching pursuit，MP）算法。冗余字典仍是目前信息領(lǐng)域研究的難點(diǎn)和熱點(diǎn)，其主要內(nèi)容：將空間RN的N個(gè)基向量增加到N＋P個(gè)（P為正整數(shù)），兵器矩陣的任意N個(gè)列向量不相關(guān)，字典中可能既有Fourier變換基同時(shí)有Curvelet變換基等，需要遵循一個(gè)原則：各個(gè)基向量盡可能使輸入信號(hào)達(dá)到最稀疏?；谶@種原則，冗余字典一定是非正交而且是冗余的，正是通過(guò)增加基向量個(gè)數(shù)提高變換系統(tǒng)的冗余性增強(qiáng)信號(hào)逼近的靈活性，從而提高稀疏表示高階信號(hào)的能力。根據(jù)能量守恒定理，信號(hào)原有的能量沒(méi)有發(fā)生轉(zhuǎn)移且大小不變，則稀疏后的信號(hào)會(huì)呈現(xiàn)在極少位置的系數(shù)非常大，絕大部分位置系數(shù)基本為零。

冗余字典可以使信號(hào)呈現(xiàn)最佳稀疏，其設(shè)計(jì)方法有人工構(gòu)造和字典訓(xùn)練兩類(lèi)，目前人工構(gòu)造應(yīng)用較為廣泛，其構(gòu)造冗余字典主要思想是：利用參數(shù)和含參數(shù)的函數(shù)中選取若干函數(shù)來(lái)近似表示信號(hào)，參數(shù)的選取是字典設(shè)計(jì)中一個(gè)很重要的問(wèn)題。經(jīng)典的方法有Gabor字典［21］，Refinement－Gaussian混合字典［22］和Gabor感知多成分字典［23］等。字典訓(xùn)練是近幾年提出的，使用較多的有K－SVD算法［24］及在此基礎(chǔ)提出的 EK－SVD［25］，DK－SVD［26］等，這種方法的優(yōu)點(diǎn)是稀疏表示效果較好，計(jì)算復(fù)雜度較低，但缺點(diǎn)是沒(méi)有完備的理論支撐。

2.2 觀測(cè)矩陣的設(shè)計(jì)

壓縮感知理論模型中，觀測(cè)矩陣在信號(hào)稀疏和信號(hào)重構(gòu)中起關(guān)鍵性的作用。如圖7所示，現(xiàn)在的觀測(cè)矩陣設(shè)計(jì)分為兩大類(lèi)：隨機(jī)觀測(cè)矩陣和確定性觀測(cè)矩陣。

圖7 設(shè)計(jì)觀測(cè)矩陣的方法Fig.7 Achieve Methods of Measurement Matrix

2.2.1 隨機(jī)觀測(cè)矩陣

觀測(cè)矩陣設(shè)計(jì)的原則是與稀疏矩陣盡可能不相干，同時(shí)，自身的列矩陣之間相互獨(dú)立。目前，隨機(jī)矩陣如隨機(jī)高斯矩陣［2，5］、部分哈馬達(dá)隨機(jī)矩陣［27］和托普利茲矩陣［28］等采用較多，其中符合獨(dú)立正太分布的高斯隨機(jī)矩陣最具有代表性。這些隨機(jī)矩陣的共同點(diǎn)是：列矩陣之間保持非常好的相互獨(dú)立性，同時(shí)隨機(jī)矩陣與稀疏矩陣有非常小的相干性，精確重建所需的觀測(cè)次數(shù)較少而且符合RIP準(zhǔn)則，所以，此方法在軟件仿真時(shí)非常受“歡迎”，但因?yàn)槠渥陨淼牟淮_定性很難在硬件電路實(shí)現(xiàn)，這也是令人“惋惜”的地方。

2.2.2 確定性觀測(cè)矩陣

Ronald A.Devore最先提出了符合RIP準(zhǔn)則的多項(xiàng)式確定性觀測(cè)矩陣，解決了隨機(jī)觀測(cè)矩陣的不足。簡(jiǎn)單敘述構(gòu)造確定性觀測(cè)矩陣的步驟［29］：

假設(shè)存在有限元素個(gè)數(shù)為z的集合T，T中的元素取值范圍為｛0，1，2，…，z－1｝。給定任意正整數(shù)d，0＜d＜z，用Pc來(lái)表示最高次冪小于或等于c的多項(xiàng)式集合：H（x）＝a0＋a1x＋…＋acxc，其中H（x）的系數(shù)｛a0，a1，…，ac｝的取值范圍為集合T，即a0，a1，…，ac∈T，所以，共有N ＝zc＋1個(gè)多項(xiàng)式。定義大小為z×z的零矩陣F，即矩陣F的元素值全為0。且記矩陣F的位置為｛（0，0），（0，l），（0，2），…，（z－1，z－2），（z－1，z－1）｝。

首先，在矩陣F的每一列的某一個(gè)位置插入數(shù)值1。其插值方式如下：把x到H（x）當(dāng)作是T到T的映射，即多項(xiàng)式H（x）的自變量和函數(shù)都在集合F中取值，矩陣F的第x列第H（x）個(gè)位置的值由0變成1。

然后，把矩陣F轉(zhuǎn)換為大小為M×l的列向量VH，其中M＝z2。在向量VH中，從第一個(gè)位置開(kāi)始，前z個(gè)元素中有1個(gè)1，前2z個(gè)元素中有2個(gè)1，以此類(lèi)推，在列向量VH中共有p個(gè)1。

循環(huán)上述兩個(gè)步驟直到取完所有多項(xiàng)式系數(shù)后，共有一個(gè)這樣的列向量。由這N個(gè)列向量組成的矩陣記為Φ0，大小為M×N，M＝z2，N＝zc＋1。而且，文獻(xiàn)［30］證明上述確定多項(xiàng)式觀測(cè)矩陣符合RIP準(zhǔn)則。

多項(xiàng)式確定性觀測(cè)矩陣也有缺陷，如觀測(cè)值M的取值范圍比隨機(jī)矩陣的設(shè)計(jì)時(shí)間比較長(zhǎng)，觀測(cè)矩陣不夠稀疏等，但它可以在硬件電路中實(shí)現(xiàn)，而且有廣闊的應(yīng)用前景，這些都是隨機(jī)觀測(cè)矩陣沒(méi)有的優(yōu)點(diǎn)。

2.3 重構(gòu)信號(hào)算法

重建算法的設(shè)計(jì)應(yīng)該遵循如下基本準(zhǔn)則：算法應(yīng)該利用盡量少的壓縮測(cè)量，并且快速、穩(wěn)定、精確或近似精確地重建原始信號(hào)。重構(gòu)算法有兩大類(lèi)應(yīng)用較為廣泛：松弛法和貪婪算法。

2.3.1 松弛法

Donoho提出利用L1范數(shù)代替L0范數(shù)，變成線性規(guī)劃的凸優(yōu)化問(wèn)題［31］，找出最稀疏的矩陣恢復(fù)原信號(hào)，這種方法稱(chēng)為松弛法。

如圖8用二維平面表示Lp范數(shù)球在0＜p＜1，p＝1，p＝2的稀疏求解問(wèn)題。當(dāng)p＝0，利用范數(shù)L0求最稀疏矩陣的解是NP－h(huán)ard問(wèn)題。當(dāng)0＜p＜1時(shí)，范數(shù)Lp本身不是凸函數(shù)，而且所得到最稀疏的解不唯一。當(dāng)p＝1時(shí)，范數(shù)L1是凸函數(shù)，約束于y＝Φx直線上轉(zhuǎn)化為線性規(guī)劃的凸優(yōu)化問(wèn)題，最稀疏解在坐標(biāo)軸是唯一的，其他坐標(biāo)軸的坐標(biāo)為0。當(dāng)p＝2時(shí)，得到的唯一解是與y＝Φx直線相切的點(diǎn)，且不在坐標(biāo)軸上，所以這個(gè)解不是最稀疏的。

圖8 三種Lp范數(shù)球的2D示意圖Fig.8 Three Kind of 2Dgraph of Norm Lpball

雖然利用L1范數(shù)代替L0范數(shù)可以求解最稀疏的矩陣，但要滿(mǎn)足RIP準(zhǔn)則、稀疏性、一致不確定性和弱準(zhǔn)確重構(gòu)等條件，但是利用L1范數(shù)求解也存在個(gè)問(wèn)題：如果y＝Φx滿(mǎn)足斜率為45°，稀疏解有無(wú)窮多個(gè)，所以，應(yīng)近盡量避免這種情況。L1范數(shù)最小化是利用基追蹤BP［32］的優(yōu)化求出最小值，解決BP線性規(guī)劃的凸優(yōu)化問(wèn)題應(yīng)用較多的方法有內(nèi)點(diǎn)法、梯度 投 影 法 （Gradient Projection for Sparse Reconstruction，GPSR）、 同 倫 算 法 （Homotopy Algorithm，HA）［33］和 最 小 角 度 回 歸 法 （Least Angle Regression，LARS）［34］。這類(lèi)方法優(yōu)點(diǎn)是重構(gòu)信號(hào)的質(zhì)量較好，需要觀測(cè)的個(gè)數(shù)較少，缺點(diǎn)是計(jì)算復(fù)雜度較高。

2.3.2 貪婪算法

貪婪算法的主要思想是：每一步迭代都選擇最匹配的原子，直至逼近原信號(hào)。這類(lèi)方法有匹配追蹤（MP）法、正交匹配追蹤（OMP）法以及在此基礎(chǔ)上的正則正交匹配追蹤（Regularize Orthogonal Matching Pursuit，ROMP）［35］和壓縮感知匹配追蹤 （Compressed Sampling Matching Pursuit，CoSaMP）［36］和閾值迭代法［37］等，其中OMP算法最具代表性。

圖9 重構(gòu)信號(hào)的算法示意圖Fig.9 Signal Algorithm of Recovery Signal

下面簡(jiǎn)單敘述OMP算法：

輸入：感知矩陣Φ，測(cè)量向量y，稀疏度k；

輸出：x的k稀疏的逼近xr，重建誤差r；

初始化：余量r0＝y(tǒng)，重建信號(hào)x0＝0，索引集Γn＝Γn－1∪ ｛k｝，迭代次數(shù)n＝0；

步驟1：計(jì)算余量和感知矩陣Φ的每一列的內(nèi)積gn＝ΦTrn－1；

步驟2：找出gn中元素最大的元素，j＝argmax｜gn［i］｜；

步驟3：更新索引集Γn＝Γn－1∪ ｛j｝及原子集合 ΦΓn ＝ ΦΓn－1∪ ｛φj｝；

步驟5：更新余量rn＝y(tǒng)－Φxn；

步驟6：判斷是否滿(mǎn)足停止條件，滿(mǎn)足則停止，xr＝xn，r＝rn輸出xr，xn，否則轉(zhuǎn)步驟1。

貪婪方法的計(jì)算復(fù)雜度雖然較低，但與松弛法相比，需要將原始信號(hào)內(nèi)的N個(gè)元素逐一恢復(fù)，而且重構(gòu)時(shí)每次恢復(fù)的計(jì)算都有微小誤差，每個(gè)元素的誤差的疊加最終也會(huì)變成非常可觀的值，同時(shí)，需要較多的觀測(cè)次數(shù)，所以，重構(gòu)信號(hào)的質(zhì)量也相對(duì)較低。

3 壓縮感知應(yīng)用

目前，壓縮感知在各個(gè)領(lǐng)域的應(yīng)用成果不斷涌現(xiàn)，CS起源于對(duì)核 磁 共 振 （Magnetic Resonance Imaging，MRI）成像的研究，同時(shí)，在超聲探測(cè)圖像、遙感成像和光學(xué)成像等方面進(jìn)展迅速。此外，CS在語(yǔ)音信號(hào)的稀疏和去噪、信道編碼數(shù)據(jù)傳輸、雷達(dá)檢測(cè)等方面也在不斷深入。

3.1 圖像方面

在光學(xué)成像領(lǐng)域，首先將CS理論應(yīng)用于實(shí)踐的是Rice大學(xué)的Baraniuk教授等研發(fā)的“單像素相機(jī)”［30］，如圖10所示，相機(jī)主要利用數(shù)字微鏡陣列（Digital Micromirror Array，DMA）完成了目標(biāo)圖像在偽隨機(jī)而至模型的線性投影，通過(guò)單一信號(hào)光子檢測(cè)器采樣，取得遠(yuǎn)小于香農(nóng)采樣的像素點(diǎn)恢復(fù)圖像，同時(shí)，具有自適應(yīng)圖像波長(zhǎng)的能力。在醫(yī)學(xué)成像領(lǐng)域，Lustig提出的稀疏 MRI成像［38］是最早將CS應(yīng)用于醫(yī)學(xué)成像，通過(guò)空間的部分?jǐn)?shù)據(jù)完美恢復(fù)出原始圖像，而且，提高了MRI的成像速度，減少對(duì)人體的輻射時(shí)間，從而降低危害。清華大學(xué)的焦鵬飛等提出將CS應(yīng)用于CT成像［39］，減少了采集圖像數(shù)據(jù)量，恢復(fù)的圖像更加清晰。此外，Ronen Tur在2010年提出了基于有限更新率的壓縮感知超聲成像算法［40］。所以，CS在三維圖像、腦部成像和超聲圖像檢測(cè)等方面有較大的應(yīng)用前景。

3.2 語(yǔ)音方面

目前，國(guó)內(nèi)外將壓縮感知理論應(yīng)用在語(yǔ)音信號(hào)處理才剛剛開(kāi)始，相對(duì)于其他領(lǐng)域的研究成果也相對(duì)較少。語(yǔ)音信號(hào)壓縮感知理論的研究主要集中在語(yǔ)音信號(hào)稀疏基、語(yǔ)音增強(qiáng)和語(yǔ)音編碼三個(gè)方向。

圖10 Rice大學(xué)的單像素相機(jī)結(jié)構(gòu)圖Fig.10 Structure of Single Pix Camera

Giacobello等［41］利用語(yǔ)音信號(hào)冗余域的稀疏性，特別是濁音信號(hào)的稀疏性，通過(guò)壓縮感知計(jì)算稀疏的線性激勵(lì)的近似值，然后再進(jìn)行編碼，并與多脈沖激勵(lì)等方法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明取得較好的聽(tīng)覺(jué)效果。該文獻(xiàn)也提出CS可以應(yīng)用到非正交基上具有稀疏性的語(yǔ)音信號(hào)。同時(shí)，語(yǔ)音信號(hào)自適應(yīng)方面的研究開(kāi)始受到關(guān)注，通過(guò)相應(yīng)自適應(yīng)算法能更好將語(yǔ)音信號(hào)稀疏、去噪和編碼［42］。此外，壓縮感知理論還應(yīng)用到語(yǔ)音信號(hào)處理的其他方向：語(yǔ)音信息隱藏、語(yǔ)音丟包補(bǔ)償策略和欠定盲源分離等。隨著壓縮感知理論研究的不斷深入，有關(guān)語(yǔ)音信號(hào)方面的成果也會(huì)不斷涌現(xiàn)。

3.3 模數(shù)轉(zhuǎn)換

CS應(yīng)用在模／數(shù)轉(zhuǎn)換是近幾年研究的難點(diǎn)，針對(duì)這個(gè)問(wèn)題，較為成熟是S.Kirolos，J.Laska在2006提出的模擬信息轉(zhuǎn)換器（Anology to Information convertor，AIC）［43］（結(jié)構(gòu)如圖11）。模擬信息轉(zhuǎn)換器主要原理是：采用一組具有信號(hào)Nyquist頻率的隨機(jī)序列對(duì)待測(cè)試信號(hào)進(jìn)行隨機(jī)解調(diào)，將高頻模擬信號(hào)投影到基帶采樣，利用重構(gòu)算法恢復(fù)原始信號(hào)。Cande’s在AIC基礎(chǔ)上研究出RMPI壓縮采樣芯片［44］，同時(shí)出現(xiàn)多通道的AIC寬帶轉(zhuǎn)換器 （Modulated Wideband Conversion，MWC）［45］。文獻(xiàn)［46］建立了并行多通道的AIC聲音信號(hào)壓縮感知模型，通過(guò)大量的相關(guān)實(shí)驗(yàn)得出結(jié)論：多路AIC很好的滿(mǎn)足RIP準(zhǔn)則和非相干性，同時(shí)，多通道恢復(fù)信號(hào)的質(zhì)量遠(yuǎn)好于單通道。目前，這種模型已成功運(yùn)用在逆合成孔徑雷達(dá)、穿墻雷達(dá)和探地雷達(dá)等雷達(dá)探測(cè)領(lǐng)域，并取得了預(yù)期的結(jié)果［47］。

4 壓縮感知的展望

壓縮感知理論的出現(xiàn)為信息領(lǐng)域帶來(lái)一次新的“革命”，改變了傳統(tǒng)壓縮采樣信號(hào)的模式，減少了采集海量冗余數(shù)據(jù)造成存儲(chǔ)和傳輸設(shè)備的使用量，而且降低不斷接近采集設(shè)備極限的抽樣頻率。不過(guò)，該理論剛剛提出，在應(yīng)用時(shí)也有需要改進(jìn)的方面：

1）去噪方面

雖然CS在壓縮采樣過(guò)程可以去除部分噪聲，但觀測(cè)值進(jìn)行傳輸、存儲(chǔ)和恢復(fù)原信號(hào)時(shí)，也會(huì)產(chǎn)生大量的噪聲，目前的方法是采用濾波器，但會(huì)造成相位偏移和衰減等問(wèn)題，所以，設(shè)計(jì)觀測(cè)矩陣和恢復(fù)算法盡量減少噪聲是目前研究的新趨勢(shì)。

2）自適應(yīng)觀測(cè)矩陣設(shè)計(jì)方面

觀測(cè)矩陣需要滿(mǎn)足RIP等條件，大多采用隨機(jī)性觀測(cè)矩陣，但隨機(jī)矩陣在硬件實(shí)現(xiàn)非常困難，而且不具有普遍適用性。所以，有必要建立自適應(yīng)觀測(cè)矩陣，不僅在硬件電路中可以實(shí)現(xiàn)，并且對(duì)不同的信號(hào)（如語(yǔ)音、圖像）進(jìn)行自適應(yīng)壓縮采樣。

3）低速模數(shù)轉(zhuǎn)換方面

壓縮感知的應(yīng)用領(lǐng)域絕大部分是針對(duì)數(shù)字信號(hào)，雖然模／數(shù)轉(zhuǎn)換雖然采用AIC可以實(shí)現(xiàn)，但先利用奈奎斯特定律進(jìn)行高速采樣，再利用CS方法低速處理恢復(fù)原信號(hào)，能否利用ADC低速采樣進(jìn)行壓縮感知方法恢復(fù)信號(hào)。

圖11 AIC結(jié)構(gòu)模型Fig.11 Structure Model of AIC

5 結(jié)論

壓縮感知理論基于信號(hào)可稀疏性原理，通過(guò)將信號(hào)從高階矩陣線性投影為低階矩陣的方法實(shí)現(xiàn)壓縮采樣。與傳統(tǒng)香農(nóng)采樣定理相比，具有采樣速率遠(yuǎn)低于奈奎斯特采樣頻率，壓縮和采樣過(guò)程同時(shí)進(jìn)行等優(yōu)點(diǎn)。本文簡(jiǎn)述了壓縮感知的基本理論，重點(diǎn)介紹了稀疏矩陣、觀測(cè)矩陣和重建算法的研究進(jìn)展和限制條件。雖然該理論存在非自適應(yīng)采樣等缺陷，但在核磁共振、雷達(dá)探測(cè)和語(yǔ)音編碼等領(lǐng)域取得了較好的效果，而且在醫(yī)療三維成像、超聲圖像檢測(cè)等方面具有良好的發(fā)展前景。但該理論還有待進(jìn)一步研究和驗(yàn)證，以滿(mǎn)足各種實(shí)際應(yīng)用需要。

［1］Richard G.Baraniuk.More Is Less：Signal Processing and the Data Deluge［J］.Science，2011，331：717－718.

［2］David L Donoho.Compressed sensing［J］.IEEE Transactions on Information Theory，2006，52（4）：1289－1306.

［3］ECandès，Wakin M.An introduction to compressive sampling［J］.IEEE Signal Processing Magazine，2008，25（2）：21－30.

［4］Donoho David L，Tsaig Y.Extensions of compressed sensing［J］.Signal Processing，2006，86（3）：533－548.

［5］Candès E，Romberg J，Tao Terence.Robust uncertainty principles：exact signal reconstruction from highly in－complete frequency information［J］.IEEE Transactions on Information Theory，2006，52（2）：489－509.

［6］焦李成，楊淑媛，劉芳，等.壓縮感知回顧與展望［J］.電子學(xué)報(bào)，2011，39（7）；1651－1662.

［7］石光明，劉丹華，高大化，等.壓縮感知理論及其研究進(jìn)展［J］.電子學(xué)報(bào)2009，37（5）：1070－1081.

［8］Shi G，Lin J，Chen X，Qi F，et al.UWB Echo Signal Detection With Ultra－Low Rate Sampling Based on Compressed Sensing［J］.IEEE Trans.on Circuits and Systems II：Express Briefs，2008，55（4）：379－383.

［9］盧策吾，劉小軍，方廣有.基于感知壓縮的探地雷達(dá)數(shù)據(jù)壓縮采集［J］.電子學(xué)報(bào)，2011，9（39）：2201－2206.

［10］Ventura R，Vandergheynst P，F(xiàn)rossard P.Low－rate and flexible image coding with redundant representations［J］.IEEE Trans.Image Processing，2006，15（3）：726－739.

［11］MElad，Bruckstein A M.A generalized uncertainty principle and sparse representation in pairs of bases ［J］.IEEE Transactions on Information Theory，2002，48（9）：2558－2567.

［12］Candès E.compressive sampling［C］／／Madrid，Spain：Proceedings of the International Congress of Mathematicians，2006：1433－1452.

［13］Donoho D L，Huo X.Uncertainty principles and ideal atomic decomposition［J］.IEEE Transactions on Information Theory，1999，47（7）：2845－2862.

［14］MElad，Bruckstein A M.A generalized uncertainty principle and sparse representation in pairs of bases［J］.IEEE Transactions on Information Theory，2002，48（9）：2558－2567.

［15］Chen S S，Donoho D L，Saunders M A.Atomic decomposition by basis pursuit［J］.SIAM Journal on Scientific Computing，2001，43（1）：129－159.

［16］Boyd S P，Vandenberghe L.Convex Optimization［M］.Cambridge：Cambridge University Press，2004.

［17］戴瓊海，付長(zhǎng)軍，季向陽(yáng).壓縮感知研究［J］.計(jì)算機(jī)學(xué)報(bào)，2011，3（34）：425－434.

［18］Candès E.Ridgelet：Theory and Application［D］.California：Stanford University，1998.

［19］Candès E，Donoho D L.Curvelets［R］.California：Stanford University，1999.

［20］Pennec E，Mallat S.Sparse geometric image representations with bandelet［J］.IEEE Trans.Image Process，2005，14（4）：423－438.

［21］Bergeau F，Mallat S.Match pursuit of images［C］／／Proceedings of IEEE Signal Processing.Philadelphia，USA：IEEE ComputerSociety，1994：330－333.

［22］Ventura R，Vandergheynst P，F(xiàn)rossard P.Low－rate and flexible image coding with redundant representations［J］.IEEE.Trans.Image Processing，2006，15（3）：726－739.

［23］Sun Y B，Xiao L，Wei Z H，et al.Sparse representations of images by a multi－component Gabor perception dictionary［J］.Acta Automatica Sinica，2008，34 （11）：1379－1387.

［24］Michal A，Elad M，Alfred B.K－SVD：An algorithm for designing over－complete dictionaries for sparse representation［J］.IEEE Transactions on Signal Processing，2006，54（11）：4311－4322.

［25］Mazhar R，Gader P D.EK－SVD：Optimized dictionary design for sparse representations［C］／／19th International Conference on Pattern Recognition，2008：1－4.

［26］Zhang Q，Li B X.Discriminative K－SVD for dictionary learning in face recognition［C］／／IEEE Conference on Computer Vision and Pattern Recognition （CVPR），2010：2691－2698.

［27］Tsaig Y，Donoho D，Extensions of compressed sensing［J］，signal Processing，2006，86（3），549－571.

［28］Holger Rauhu.Circulant and Toeplitz matrices in compressed sensing［J］.In Processing SPAR’09，Saint Malo，2009.

［29］Ronald A.Devore.Deterministieeon struetions of compressed sensing matrice［J］.Journal of ComPlexity，2007，23（4－6）：918－925.

［30］Duarte M F，Davenport M A，Takhar，et al.Single－pixel imaging via compressive sampling［J］.IEEE Signal Processing Magazine，2008，25（2）：83－91.

［31］David Donoho.For most large underdetermined systems of linear equations，the minimal ell－1norm near－solution approximates the sparsest near－solution［J］.Communications on Pure and Applied Mathematics，2006，59（7）：907－934.

［32］Chen Shaobing，Donoho D L，Saunders M A.Atomic decomposition by dasis dursuit［J］.SIAM Journal on Scientific Computing，1998，20（1）：33－61.

［33］Malioutov D M，Cetin M，Willsky A S.Homotopy continuation for sparse signal representation［C］／／IEEE International Conference on Acoustics，Speech，and Signal Processing.Philadelphia，USA：IEEE Press，2005：733－736.

［34］Efron B，Hastie T，Johnstone I，et al.Least angle regression［J］.The Annals of Statistics，2004，32（2）：407－451.

［35］Needell D，Vershynin R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit［J］.Foundations of Comp.Math，2000，9（3）：317－334.

［36］Needell D，Tropp J.Cosamp：Iterative signal recovery from incomplete and inaccurate samples［J］.Applied and Comput.Harmon.Anal.2009，26（3）：301－321.

［37］Daubechies I，Defrise M，Mol C De.An iterative thresholding algorithm for linear inverse problemswith a sparsity constraint［J］.Comm.Pure.Appl.Math，2004

［38］Lustig M，Donoho D，Pauly J M.Sparse MRI：The application of compressed sensing for rapid MR imaging［J］.Magnetic Resonance in Medicine，2007，58（6）：1182－1195.

［39］焦鵬飛，李亮，趙驥.壓縮感知在醫(yī)學(xué)圖像重建中的最新進(jìn) 展 ［J］.CT 理 論 與 應(yīng) 用 研 究，2012，21（1）：133－147.

［40］Tur R，Eldar Y C，F(xiàn)riedman Z.Innovation rate sampling of pulse streams with application to ultrasound imaging［J］.IEEE Transactions on Signal Processing，2011，59（4）：1827－1842.

［41］Giacobello D，Christensen M G，Murthi M N，et al.Retrieving sparse patterns using a compressed sensing framework：applications to speech coding based on sparse linear prediction［J］.Signal Processing Letters，IEEE，2010，17（1）：103－106.

［42］羅武駿，陶文鳳，左加闊，等.自適應(yīng)語(yǔ)音壓縮感知方法［J］.東 南 大 學(xué) 學(xué) 報(bào) （自 然 科 學(xué) 版 ），2012，42（6）：1027－1030.

［43］Kirolos S，Ragheb T，Laska J N，et al.Practical issues in implementing analog－to－digital converters［J］.International Workshop on System－on－Chip for Real－Time Applications，2006：141－146.

［44］Becker S，Bobin J，Candès E J，NESTA：a fast and accurate first－order method for sparse recovery［J］.SIAM J.Imaging Sci.2011，4（1）：1－39.

［45］Mishali M，Eldar Y C.From Theory to Practice：Sub－Nyquist Sampling of Sparse Wideband Analog Signals［J］.IEEE Journal of Selected Topics on Signal Processing，2010，4（2）：375－391.

［46］余愷，李元實(shí)，王智，等.基于壓縮感知的新型聲信號(hào)采集方法［J］.儀器儀表學(xué)報(bào).2011，33（1）：106－112.

［47］劉記紅，徐少坤.壓縮感知雷達(dá)成像綜述［J］.信號(hào)處理，2011，27（2）：251－260.