【正文】 示能 力。s 和 Tao通過(guò)研究發(fā)現(xiàn)，滿足冪定律衰減的信號(hào)，可利用壓縮感知理論進(jìn)行恢復(fù)，并且重構(gòu)誤RppNi ip ?? ?? /11 )( ? 差滿足： rrCS NKCXXE ????? ))/(log( 6 （式 ） 其中 r=1/p1/2， 0p1。如何找到或構(gòu)造適合一類信號(hào)的正交基，以求得信號(hào)的最稀疏表示，這是一個(gè)有待進(jìn)一步研究的問(wèn)題。把變換基是正交基 的條件擴(kuò)展到了由多個(gè)正交基構(gòu)成的正交基字典。 最近幾年，對(duì)稀疏表示研究的另一個(gè)熱點(diǎn)是信號(hào)在過(guò)完備字典下的稀疏分解。從 從過(guò)完備字典中找到具有最佳線性組合的 K項(xiàng)原子來(lái)表示一個(gè)信號(hào)，稱作信號(hào)的稀疏逼近或高度非線性逼近。文獻(xiàn)以淺顯易懂的表達(dá)說(shuō)明了過(guò)完備字典對(duì)信號(hào)表示的必要性，同時(shí)還指出字典的構(gòu)成應(yīng)盡量符合信號(hào)本身所固有的特性。這兩個(gè)問(wèn)題也一直是該領(lǐng)域研究的熱點(diǎn)，學(xué)者們對(duì)此已做了一些探索，其中，以非相干字典為基礎(chǔ)的一系列理論證明得到了進(jìn)一步改進(jìn)。 從過(guò)完備字典的構(gòu)成角度來(lái)講，文獻(xiàn) [38]中提出使用局部 Cosine基來(lái)刻畫(huà)聲音信號(hào)的局部頻域特性；利用 bandlet基來(lái)刻畫(huà)圖像中的幾何邊緣。 從稀疏分解算法角度來(lái)講，在音視頻信號(hào)處理方面，基于貪婪迭代思想的 MP算法表現(xiàn)出極大的優(yōu)越性，但不是全局最優(yōu)解。BP算法具有全局最優(yōu)的優(yōu)點(diǎn)，但計(jì)算復(fù)雜度極高，例如對(duì)于長(zhǎng)度為 8192的信號(hào) ，采用小波字典分解，等價(jià)于求解一個(gè)長(zhǎng)度為 8192*212992的線性規(guī)劃。之后又出現(xiàn)了一系列同樣基于貪婪迭代思想的改進(jìn)算法，如正交匹配追蹤算法（ OMP），樹(shù)形匹配追蹤（ TMP），分段匹配追蹤（ StOMP）算法等。這些協(xié)議是非自適應(yīng)的，僅僅需要用少量的固定波形和 原信號(hào) 聯(lián)系起來(lái)，這些固定波形和為信號(hào)提供簡(jiǎn)潔表示的基不相關(guān)。進(jìn)一步講，使用優(yōu)化方法可以收集到的少量的觀測(cè)值中重構(gòu)信號(hào)。觀測(cè)器的設(shè)計(jì)目的是如何采樣得到 M個(gè)觀測(cè)值，并保證從中能重構(gòu)出長(zhǎng)度為 N的信號(hào) X或者基?下等價(jià)的稀疏系數(shù)向量 。觀測(cè)過(guò)程實(shí)際就是利用N?觀測(cè)矩陣 的 M個(gè)行向量? ?Mjj 1??對(duì)稀疏系數(shù)向量進(jìn)行投影，即計(jì)算 和各個(gè)觀測(cè)向量? ?Mjj 1??之間的內(nèi)積， 得到 M個(gè)觀測(cè)值， ),...,2,1(, Mjy jj ????? ?，記觀測(cè)向量),... ,( 21 MyyyY ?，即 XAXYCST ??????? （式 ） 圖 （ a）是（式 ）的形象描述。 圖 （ a）隨機(jī)高斯矩陣作為觀測(cè)矩陣?，稀疏域選擇 DCT變換域，對(duì)信號(hào) X進(jìn)行 DCT變換后再進(jìn)行觀測(cè)。 對(duì)于給定的 Y從（式 ）中求出?是 一個(gè)線性規(guī)劃問(wèn)題，但由于 M N，即方程（ a） （ b） 圖 觀測(cè)矩陣的圖形表示 的個(gè)數(shù)少于未知數(shù)的個(gè)數(shù)，這一欠定問(wèn)題一般來(lái)講無(wú)確定解。此時(shí)，只要設(shè)法確定出?中的 K個(gè)非零系數(shù) i?的合適位置，由于觀測(cè)向量 Y是這些非零系數(shù) i?對(duì)應(yīng)?的 K個(gè)列向量的線性組合，從而可以形成一個(gè)?的線性方程組來(lái)求解這些非零項(xiàng)的具體值。這個(gè)充要條件和 Cand232。即，要想使信號(hào)完全重構(gòu)，必須保證觀測(cè)矩陣不會(huì)把兩個(gè)不同的 K項(xiàng)稀疏信號(hào)映射到同一個(gè)采樣集合中，這就要求從觀測(cè)矩陣中抽取的每 M個(gè)列向量構(gòu)成的矩陣是非奇異的。 然而，判斷給定的CSA是否具有 RIP性質(zhì)是一個(gè)組合復(fù)雜度問(wèn)題。 文獻(xiàn) [24]指出如果保證觀測(cè)矩陣?和稀疏基?不相干，則CSA在很大概率上滿足RIP性質(zhì)。不相干性越強(qiáng)，互相表示時(shí)所需的系數(shù)越多；反之，相關(guān)性則越強(qiáng)。例如，可以生成多個(gè)零均值、方差為 1/ N 的隨機(jī)高斯函數(shù)，將它們作為觀測(cè)矩陣 的元素 i?，使得CSA以很高的概率具有 RIP性質(zhì)。因此可以從 M個(gè)觀測(cè)值),... ,( 21 MyyyY ?中以很高的概率去恢復(fù)長(zhǎng)度為 N的 K項(xiàng)稀疏信號(hào)。為進(jìn)一步簡(jiǎn)化觀測(cè)矩陣?，在某些條件下，以隨機(jī)1?為元素構(gòu)成的 Rademacher矩陣也可以證明具有 RIP性質(zhì)和普適性。在該理論中，對(duì) 觀測(cè)矩陣的約束是比較寬松的， Donoho在文獻(xiàn) [23]中給出了觀測(cè)矩陣所必需具備的三個(gè)條件，并指出大部分一致分布的隨機(jī)矩陣都具備這三個(gè)條件，均可作為觀測(cè)矩陣，如：部分 Fourier集、部分 Hadamard集、一致分布的隨機(jī)投影（ uniform Random Projection）集等，這與對(duì) RIP條件進(jìn)行研究得出的結(jié)論相一致。對(duì)于任何穩(wěn)定的重構(gòu)算法是否存在一個(gè)真實(shí)的確定性的觀測(cè)矩陣仍是一個(gè)有待研究的問(wèn)題。它指出，在模擬系統(tǒng)中，觀測(cè)噪聲也是影響觀測(cè)次數(shù)的重要因素，為說(shuō)明這一點(diǎn)，作者 從信息論的角度研究了稀疏信號(hào)的率失真函數(shù)，給出了觀測(cè)噪聲對(duì)信號(hào)重建效果的影響。由于觀測(cè)數(shù)量 M 遠(yuǎn)小于信號(hào)長(zhǎng)度 N，因此不得不面對(duì)求解欠定方程組XAY CS?的問(wèn)題，需要列舉出R空間的?? TK個(gè)稀疏空間，在計(jì)算上是相當(dāng)復(fù)雜的。然而，文獻(xiàn) [2326， 28]的近期研究結(jié)果表明如果信號(hào) X 是稀疏的，那么（ 1）精確恢復(fù)是可能的；（ 2）真實(shí)信號(hào)實(shí)際上就是一個(gè)簡(jiǎn)單凸優(yōu)化問(wèn)題的解。 為 更 清 晰 地 描 述 壓 縮 感 知 理 論 的 信 號(hào) 重 構(gòu) 問(wèn) 題 ， 首 先 定 義 向 量 ),...,( 1 NxxX ?的 p范數(shù)為 ppNi ip xX/11 )(??? （式 ） 當(dāng) p=0時(shí)得到 0范數(shù)，它實(shí)際上表示 X中非零項(xiàng)的個(gè)數(shù)。因此，求解（式 ）式的數(shù)值計(jì)算極不穩(wěn)定而且是 NP難問(wèn)題。于是稀疏分解的已有算法可以應(yīng)用到 CS重構(gòu)中。 不過(guò)， 1范數(shù)最小化不是尋找稀疏解的唯一方法； 其它方法，例如貪婪算法也已被提出。（ 2）僅僅觀測(cè)比信號(hào)長(zhǎng)度小得多的任何 M 個(gè)系數(shù)的集合，不會(huì)損失信息。已經(jīng)證明，如果 )/log(),(2 ?? NSCM ??????，那么重構(gòu)成功的概率超過(guò)??。因此這兩類問(wèn)題的求解本質(zhì)上是一樣的。 定理 2已證明：對(duì)于一個(gè) K項(xiàng) 稀疏（ KN）長(zhǎng)度為 N的信號(hào)僅僅需要投影到另一個(gè)不相關(guān)基上的 K+1個(gè)系數(shù)就可以以高概率被重構(gòu)。 Cand232。盡管 BP算法可行，但在實(shí)際應(yīng)用中存在兩個(gè)問(wèn)題：第一，即使對(duì)常見(jiàn)的圖像尺寸，算法的計(jì) 算復(fù)雜度也難以忍受，在采樣點(diǎn)個(gè)數(shù)滿足cKM?，)1/(log2 ?? KNc時(shí)，重構(gòu)計(jì)算復(fù)雜度的量級(jí)在)( 3NO；第二，由于 1范數(shù)無(wú)法區(qū)分稀疏系數(shù)尺度的位置，所以盡管整體上重構(gòu)信號(hào)在歐氏距離上逼近原信號(hào)，但存在低尺度能量搬移到了高尺度的現(xiàn)象，從而容易出現(xiàn)一些人工效應(yīng)，如一維信號(hào)會(huì)在高頻出現(xiàn)振蕩。s 和 Romberg 提出了不同的信號(hào)恢復(fù)方法，該方法要求對(duì)原信號(hào)具有少量的先驗(yàn)條件，同時(shí)也可以對(duì)所求結(jié)果施加適當(dāng)?shù)南拗?，以約束重構(gòu)信號(hào)的特性。 另一類基于貪婪思想的迭代算法以更多的觀測(cè)數(shù)量作為代價(jià)達(dá)到了更加快速重構(gòu)的目的。樹(shù)形匹配追蹤（ TMP）算法是 2020年 Chinh La 和 Minh 。匹配追蹤類算法都是基于貪婪迭代算法，以多于 BP算法需要的采樣數(shù)目換取計(jì)算復(fù)雜度的降低。 2020年 Donoho等人提出了分段正交匹配追蹤（ StOMP， stagewise OMP）算法。 E. Hale， W. Yin基于分裂算子和同倫算子提出了求解最小 1范數(shù)大規(guī)模問(wèn)題的方法，適合于糾錯(cuò)編碼、磁共振成像、 NMR波譜研究等領(lǐng)域的大規(guī)模問(wèn)題求解。因此一類利用稀疏矩陣作為觀測(cè)矩陣進(jìn)行采樣的方法出現(xiàn)了。 Gilbert等人在 2020 年 4 月提出了鏈?zhǔn)阶粉櫍?CP， Chaining Pursuit）方法來(lái)恢復(fù)可壓 縮信號(hào)。 總之，目前為止出現(xiàn)的重構(gòu)算法都可歸入以下三大類： （ 1）貪婪追蹤算法：這類方法是通過(guò)每次迭代時(shí)選擇一個(gè)局部最優(yōu)解來(lái)逐步逼近原始信號(hào)。 （ 2）凸松弛法：這類方法通過(guò)將非凸問(wèn)題轉(zhuǎn)化為凸問(wèn)題求解找到信號(hào)的逼近， 如 BP算法，內(nèi)點(diǎn)法，梯 度投影方法和迭代閾值法。 總之，每種算法都有其固有的缺點(diǎn)。貪婪追蹤算法在運(yùn)行時(shí)間和采樣效率上都位于另兩種算法 之間。 壓縮感知優(yōu)勢(shì)及不足 相對(duì)于傳統(tǒng)的 信息處理方式，壓縮感知理論毫無(wú)疑問(wèn)是具有優(yōu)勢(shì)的，這體現(xiàn)在以 下幾個(gè)方面： （ 1）采集數(shù)據(jù)的時(shí)候只需要采集一部分?jǐn)?shù)據(jù)（包含了原信號(hào)的全局信息），一開(kāi)始就可以傳輸長(zhǎng)度較短的信號(hào)。這種優(yōu)勢(shì)在醫(yī)學(xué)圖像領(lǐng)域體現(xiàn)的愈為明顯，因?yàn)椴杉瘮?shù)據(jù)的過(guò)程往往是對(duì)病人帶來(lái)很大麻煩甚至身體傷害的過(guò)程。 （ 2）由于直接感知壓縮后的數(shù)據(jù)，所以不受奈奎斯特采樣定律的局限，降低了對(duì)采樣系統(tǒng)硬件設(shè)備的要求，這對(duì)于寬帶信號(hào)非常實(shí)用。由于感知到的測(cè)量值中的任何一項(xiàng)都是重要的，或者說(shuō)不重要的， 所以如果測(cè)量值丟失了其中的某幾項(xiàng)，仍然可以完美重構(gòu)信號(hào)。 （ 2）感知到的測(cè)量值的長(zhǎng)度一般是重要分量長(zhǎng)度的 4倍，才能近乎完美地重構(gòu)。即使將 0范數(shù)轉(zhuǎn)化為 1 范數(shù)，由于不可微性（ indifferentiable），算法的計(jì)算復(fù)雜度仍然很高。 （ 4）壓縮感知理論是采用非自適應(yīng)線性投影來(lái)保持信號(hào)的原始結(jié)構(gòu)，不夠靈活，需要研究自適應(yīng)傳感技術(shù)，根據(jù)不同的信號(hào)類型采用不同的數(shù)據(jù)采樣和重構(gòu)策略?，F(xiàn)在將分別講述壓縮感知在傳感網(wǎng)中的兩種觀測(cè)方式。 sink節(jié)點(diǎn)在知道種子和節(jié)點(diǎn)在網(wǎng)絡(luò)中的地址后，也能夠很容易的為每個(gè)傳感節(jié)點(diǎn) j(j=1,...,n)重建出隨即矢量 }{ 1, kijiA ? 2)）編號(hào)為 j的傳感節(jié)點(diǎn)將所感知數(shù)據(jù) jx 與 , }{1,kijiA ?相乘得到個(gè)元組 （式 ） 所有的節(jié)點(diǎn)在 k個(gè)時(shí)隙內(nèi)（次傳輸）連貫的將相應(yīng)的 jV 以模擬方式傳至融合 中心。 以上步驟是以完全分散的形式將感知數(shù)據(jù)的 k個(gè)隨機(jī)投影在 k次傳輸中傳給 sink節(jié)點(diǎn)。這種方式可以達(dá)到同樣的目的。具體步驟如下： 1）首先傳感 節(jié)點(diǎn)能夠計(jì)算測(cè)量值 kijjiji XAV 1, }{ ?? ； 2）然后這些測(cè)量值可以經(jīng)過(guò)聚合在簇頭節(jié)點(diǎn)得到所有測(cè)量值 V=Ax，然后對(duì)這些值進(jìn)行編碼傳至 sink節(jié)點(diǎn)。但考慮到數(shù)字通信的抗噪聲能力強(qiáng)，遠(yuǎn)距離傳輸能保證信號(hào)質(zhì)量，在本文中將選取第二種方式?，F(xiàn)有的應(yīng)用主要包括壓縮感知成像、模擬 信息的轉(zhuǎn)換、生物傳感等方面。數(shù)字微鏡器件由數(shù)字電壓信號(hào)控制微鏡片的機(jī)械運(yùn)動(dòng)以實(shí)現(xiàn)對(duì)入射光線的調(diào)整，相當(dāng)于隨機(jī)觀測(cè)矩陣 Φ。而且壓縮感知技術(shù)也可以應(yīng)用于雷達(dá)成像領(lǐng)域，與傳統(tǒng)雷達(dá)成像技術(shù)相比，壓縮感知雷達(dá)成像主要實(shí)現(xiàn)了兩個(gè)重要改進(jìn)：在接收端省去了脈沖壓縮匹配濾波器；同時(shí)因?yàn)楸荛_(kāi)了對(duì)原始信號(hào)的直接采樣，降低了接收端對(duì)模數(shù)轉(zhuǎn)換器件帶寬的要求。 Bhattacharya等人將壓縮感知理論應(yīng)用到合成孔徑雷達(dá)圖像數(shù)據(jù)獲取上，從而解決了海量數(shù)據(jù)的采集和存儲(chǔ)問(wèn)題，顯著降低了衛(wèi)星 圖像處理的計(jì)算代價(jià)。 模擬信息轉(zhuǎn)換 對(duì)于帶寬非常高的信號(hào)，比如雷達(dá)和通信信號(hào)處理系統(tǒng)涉及的射頻信號(hào)，根據(jù)奈奎斯特定理，要獲得完整的信號(hào)信息，所采用的模數(shù)轉(zhuǎn)換器必須具有很高的采樣頻率。對(duì)此 Kriolos等人設(shè)計(jì)了基于壓縮感知理論的模擬 /信息轉(zhuǎn)換器，利用壓縮感知理論中測(cè)量信息可以得到完整信號(hào)的原理。 Laska等人進(jìn)一步發(fā)展了基于隨機(jī)采樣系統(tǒng)的模擬 /信息轉(zhuǎn)換器，并給出了隨機(jī)抽樣系統(tǒng)的兩種實(shí)現(xiàn)模型：第一種模型采用多個(gè)并行低采樣率的模數(shù)轉(zhuǎn)換器，每個(gè)模數(shù)轉(zhuǎn)換器之間有等間隔的位移，通過(guò)隨機(jī)控制來(lái)自不同的模數(shù)轉(zhuǎn)換器的采樣，實(shí)現(xiàn)隨機(jī)采樣。第二種模型采用一組電容和數(shù)字控制換向器隨機(jī)采樣，該系統(tǒng)只需要一個(gè)模數(shù)轉(zhuǎn)換芯片即可。此外，基于生物體基因序列稀疏特性， Sheikh等驗(yàn)證了可以通過(guò)置信傳播的方法實(shí)現(xiàn)壓縮感知 DNA芯片中的信號(hào)重構(gòu)。 本章小結(jié) 本章詳細(xì)描述了壓縮感知理論基本框架。對(duì)壓縮感知理論實(shí)現(xiàn)的兩個(gè)前提要求 ——信號(hào)稀疏性及觀測(cè)矩陣和稀疏表示基之間滿足不相干性進(jìn)行了詳細(xì)的論述，著重介紹了信號(hào)稀疏變換、觀測(cè)矩陣設(shè)計(jì)和重構(gòu)算法三個(gè)方面的最新研究進(jìn)展情況。 第 4章 CS 在無(wú)線傳感網(wǎng)中的應(yīng)用 前文我們已經(jīng)對(duì)壓縮感知（ CS）理論做了叫詳細(xì)的介紹，下面我將介紹將壓縮感知應(yīng)用于無(wú)線傳感的優(yōu)勢(shì)以及采用 OMP 算法，實(shí)現(xiàn)對(duì)一維信號(hào)和二維信號(hào)圖像的CS 重構(gòu)。下面將介紹已有的基于相關(guān)性的數(shù)據(jù)壓縮技術(shù)，并闡明利用 CS 壓縮數(shù)據(jù)的優(yōu)勢(shì)。利用傳感數(shù)據(jù)間（相鄰傳感器節(jié)點(diǎn) 在同一時(shí)刻所采集的數(shù)據(jù)之間）的空間相關(guān)性，文獻(xiàn) [17]提出了在多層架構(gòu)中，運(yùn)用多重主成分分析法（ Multiple Principal Component Analysis, MPCA）去除了普通節(jié)點(diǎn)間的數(shù)據(jù)相關(guān)性以及相鄰簇頭節(jié)點(diǎn)主成分之間的相關(guān)性，而文獻(xiàn) [26]則將近年提出壓縮感知算法運(yùn)用到基于分簇的傳感網(wǎng)數(shù)據(jù)壓縮中，降低了傳輸能耗。但是這些算法并沒(méi)有綜合考慮時(shí)間相關(guān)性和空間相關(guān)性，文獻(xiàn) [46]將融合了這兩種相關(guān)性的分布式信源編碼運(yùn)用到傳感網(wǎng)的數(shù)據(jù)壓縮中。另外文獻(xiàn) [26]在分布式架構(gòu)的基礎(chǔ)上利用小波提升 算法來(lái)壓縮數(shù)據(jù)，而文獻(xiàn) [23]則優(yōu)化了簇內(nèi)信息的交換，此外，文獻(xiàn) [25]也都各自闡述了相應(yīng)的數(shù)據(jù)壓縮技術(shù)。信號(hào)壓縮的分類方法根據(jù)不同的原理大致可以分為兩種。 （ 1）空間域處理方法 空間域處理方法是指直接在圖像所在的空間對(duì)