【導(dǎo)讀】數(shù)據(jù)壓縮技術(shù)是提高無(wú)線(xiàn)數(shù)據(jù)傳輸速度的有效措施之一。近年來(lái)出現(xiàn)的壓縮感知理論則不受制于奈奎斯

　　

【正文】 ，如一維信號(hào)會(huì)在高頻出現(xiàn)振蕩。 針對(duì)上述問(wèn)題， 2020 年 1 月 Cand232。s 和 Romberg 提出了不同的信號(hào)恢復(fù)方法，該方法要求對(duì)原信號(hào)具有少量的先驗(yàn)條件 ，同時(shí)也可以對(duì)所求結(jié)果施加適當(dāng)?shù)南拗?，以約束重構(gòu)信號(hào)的特性。通過(guò)在凸集上交替投影（ Projections onto Convex Sets）的方法，可以快速求解線(xiàn)性規(guī)劃問(wèn)題。 另一類(lèi)基于貪婪思想的迭代算法以更多的觀(guān)測(cè)數(shù)量作為代價(jià)達(dá)到了更加快速重構(gòu)的目的。 （ MP）和正交匹配追蹤（ OMP）算法來(lái)求解優(yōu)化問(wèn)題重構(gòu)信號(hào)，大大提高了計(jì)算的速度，且易于實(shí)現(xiàn)。樹(shù)形匹配追蹤（ TMP）算法是 2020年 Chinh La 和 Minh 。該方法針對(duì) BP、 MP和 OMP方法沒(méi)有考慮信號(hào)的多尺度分解時(shí)稀疏信號(hào)在各子帶位置的關(guān)系，將稀疏系數(shù)的樹(shù)型結(jié)構(gòu)加以利用，進(jìn)一步提升了重構(gòu)信號(hào)的精度和求解的速度。匹配追蹤類(lèi)算法都是基于貪婪迭代算法，以多于 BP算法需要的采樣數(shù)目換取計(jì)算復(fù)雜度的降低。例如 OMP算法，需要 cKM?，)ln(2 Nc?個(gè)采樣點(diǎn)數(shù)才能以較高的概率恢復(fù)信號(hào)，信號(hào)重構(gòu)的計(jì)算復(fù)雜度為)( 2NKO。 2020年 Donoho等人提出了分段正交匹配追蹤（ StOMP， stagewise 24 OMP）算法。它將 OMP進(jìn)行一定程度的簡(jiǎn)化，以逼近精度為代價(jià)進(jìn)一步提高了計(jì)算速度（計(jì)算復(fù)雜度為 O(N)），更加適合于求解大規(guī) 模問(wèn)題。 E. Hale， W. Yin基于分裂算子和同倫算子提出了求解最小 1范數(shù)大規(guī)模問(wèn)題的方法，適合于糾錯(cuò)編碼、磁共振成像、 NMR波譜研究等領(lǐng)域的大規(guī)模問(wèn)題求解。 在上述各種方法中，觀(guān)測(cè)矩陣中的所有值都非零，這樣信號(hào)采樣過(guò)程的計(jì)算量是O(MN)，在大規(guī)模的數(shù)據(jù)面前，這個(gè)量級(jí)還是非常大的。因此一類(lèi)利用稀疏矩陣作為觀(guān)測(cè)矩陣進(jìn)行采樣的方法出現(xiàn)了。 Graham Cormode等人，提出利用分組測(cè)試和隨機(jī)子集選取來(lái)估計(jì)稀疏信號(hào)的非零系數(shù)的位置和取值，該方法需要的采樣數(shù)為 )log(2NKOM?，信號(hào)重構(gòu)的計(jì)算復(fù)雜度為)log( 2NKO，得到重 構(gòu)信號(hào)的速度更快。 Gilbert等人在 2020 年 4 月提出了鏈?zhǔn)阶粉櫍?CP， Chaining Pursuit）方法來(lái)恢復(fù)可壓縮信號(hào)。利用)log( 2NKO個(gè)采樣觀(guān)測(cè)重構(gòu)信號(hào)，需要計(jì)算量為 )loglog(22 KNKO，該方法對(duì)特別稀疏信號(hào)的恢復(fù)計(jì)算性能較高，但當(dāng)信號(hào)的稀疏度減少，需要的采樣點(diǎn)數(shù)會(huì)迅速增加，甚至超過(guò)信號(hào)本身的長(zhǎng)度，這就失去了壓縮采樣的意義。 總之，目前為止出現(xiàn)的重構(gòu)算法都可歸入以下三大類(lèi)： （ 1）貪婪追蹤算法：這類(lèi)方法是通過(guò)每次迭代時(shí)選擇一個(gè)局部最優(yōu)解來(lái)逐步逼近原始信號(hào)。這些算法包括 MP算法， OMP算法，分段 OMP算法（ StOMP） 和正則化 OMP（ ROMP）算法。 （ 2）凸松弛法：這類(lèi)方法通過(guò)將非凸問(wèn)題轉(zhuǎn)化為凸問(wèn)題求解找到信號(hào)的逼近， 如 BP算法，內(nèi)點(diǎn)法，梯度投影方法和迭代閾值法。 （ 3）組合算法：這類(lèi)方法要求信號(hào)的采樣支持通過(guò)分組測(cè)試快速重建，如傅 立葉采樣，鏈?zhǔn)阶粉櫤?HHS追蹤等。 總之，每種算法都有其固有的缺點(diǎn)。凸松弛法重構(gòu)信號(hào)所需的觀(guān)測(cè)次數(shù)最少， 但往往計(jì)算負(fù)擔(dān)很重。貪婪追蹤算法在運(yùn)行時(shí)間和采樣效率上都位于另兩種算法 之間。 由上面的分析可知，重構(gòu)算法和所需的觀(guān)測(cè)次數(shù)密切相關(guān)，當(dāng)前，壓縮感知 理論的信號(hào)重構(gòu)問(wèn)題的研究主要集中在 如何構(gòu)造穩(wěn)定的、計(jì)算復(fù)雜度較低的、對(duì) 觀(guān)測(cè)數(shù)量要求較少的重構(gòu)算法來(lái)精確地恢復(fù)原信號(hào)。 壓縮感知優(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)的全局信息），一 25 開(kāi)始就可以傳輸長(zhǎng)度較短的信號(hào)。這樣做的好處就是將信號(hào)壓縮這一端的過(guò)程簡(jiǎn)單化，而將復(fù)雜的部分交給數(shù)據(jù)還原的這一端來(lái)做。這種優(yōu)勢(shì)在醫(yī)學(xué)圖像領(lǐng)域體現(xiàn)的愈為明顯，因?yàn)椴杉瘮?shù)據(jù)的過(guò)程往往是對(duì)病人帶來(lái)很大麻煩甚至身體傷害的過(guò)程。以 X 光斷層掃描為例， 眾所周知 ， X 光輻射會(huì)對(duì)病人造成身體損害，而壓縮感知的特點(diǎn)使得我們可以用比經(jīng)典少得多的輻射劑量來(lái)進(jìn)行數(shù)據(jù)采集，這在醫(yī)學(xué)上的意義是不言而喻的。 （ 2）由于直接感知壓縮后的數(shù)據(jù)，所以不受奈奎斯特采樣定律的局限，降低了對(duì)采樣系統(tǒng)硬件設(shè)備的要求，這對(duì)于寬帶信號(hào)非常實(shí)用。 （ 3）具有抗干擾能力。由于感知到的測(cè)量值中的任何一項(xiàng)都是重要的，或者說(shuō)不重要的， 所以如果測(cè)量值丟失了其中的某幾項(xiàng)，仍然可以完美重構(gòu)信號(hào)。 當(dāng)然，目前的壓縮感知理論還不是特別完善， 尚存在一些問(wèn)題需要研究，在這里將列出其中幾個(gè)問(wèn)題： （ 1）實(shí)際應(yīng)用領(lǐng)域中，測(cè)量到的數(shù)據(jù)可能無(wú)法包含信號(hào)的全局信息，例如最傳統(tǒng)的攝像問(wèn)題，每個(gè)感光器件所感知到的只是一小塊圖像而不是什么全局信息。 （ 2）感知到的測(cè)量值的長(zhǎng)度一般是重要分量長(zhǎng)度的 4倍，才能近乎完美地重構(gòu)。 （ 3）重構(gòu)算法是 NP 問(wèn)題。即使將 0范數(shù)轉(zhuǎn)化為 1 范數(shù)，由于不可微性（ indifferentiable），算法的計(jì)算復(fù)雜度仍然很高。而且，目前的重構(gòu)算法對(duì)含噪信號(hào)或者采樣過(guò)程中引入噪聲的信號(hào)重構(gòu)效果不夠理想。 （ 4）壓縮感知理論是采用非自適應(yīng)線(xiàn)性投影來(lái)保持信號(hào)的原始結(jié)構(gòu)，不夠靈活，需要研究自適 應(yīng)傳感技術(shù)，根據(jù)不同的信號(hào)類(lèi)型采用不同的數(shù)據(jù)采樣和重構(gòu)策略。 壓縮感知在傳感網(wǎng)中的觀(guān)測(cè)方式 之前已經(jīng)提及將壓縮感知運(yùn)用到傳感網(wǎng)中，即在節(jié)點(diǎn)處得到觀(guān)測(cè)值數(shù)據(jù)并傳給sink節(jié)點(diǎn)（或者融合中心）?，F(xiàn)在將分別講述壓縮感知在傳感網(wǎng)中的兩種觀(guān)測(cè)方式。 （ 1） 第一種：模擬通信方式 模擬通信，即傳輸?shù)臏y(cè)量值是模擬數(shù)據(jù)，具體步驟如下（假設(shè)有個(gè)傳感節(jié)點(diǎn)）： 1)對(duì)于個(gè)節(jié)點(diǎn)而言，每一個(gè)節(jié)點(diǎn)都要利用其節(jié)點(diǎn)網(wǎng)絡(luò)地址（或者編號(hào)）作為產(chǎn)生偽隨機(jī)的種子（ seed），得到隨機(jī)投影矢量 }{1,kijiA ?的個(gè) K元素。 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è)元組 26 （式 ） 所有的節(jié)點(diǎn)在 k個(gè)時(shí)隙內(nèi)（次傳輸）連貫的將相應(yīng)的 jV 以模擬方式傳至融合中心。由于無(wú)線(xiàn)電波的累加性質(zhì)，在 k次傳輸后 sink節(jié)點(diǎn)最終得到的接收信號(hào)為 ?? ????nj j Axvy 1 ?? （式 ） 其中ω為通信過(guò)程中產(chǎn)生的噪聲。 以上步驟是以完全分散的形式將感知數(shù)據(jù)的 k個(gè)隨機(jī)投影在 k次傳輸中傳給 sink節(jié)點(diǎn)。 （ 2） 第二種：數(shù)字通信方式 數(shù)字通信方式，即傳輸?shù)臏y(cè)量值是量化后的值。這種方式可以達(dá)到同樣的目的。假設(shè)節(jié)點(diǎn)能夠進(jìn)行本地通信，并能建立一條路由，從而與某個(gè)確定的簇頭節(jié)點(diǎn)之間形成生成樹(shù)。具體步驟如下： 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)。 這兩種方法主要的不同就在于第一種方式不需要復(fù)雜的路由信息。但考慮到數(shù)字通信的抗噪聲能力強(qiáng)，遠(yuǎn)距離傳輸能保證信號(hào)質(zhì)量，在本文中將選取第二種方式。 27 第 3 章 壓縮感知理論應(yīng)用概述 壓縮傳感理論帶來(lái)了傳統(tǒng)信號(hào)采樣理論的變革，而且具有很廣闊的應(yīng)用前景和場(chǎng)合?，F(xiàn)有的應(yīng)用主要包括壓縮感知成像、模擬信息的轉(zhuǎn)換、生物傳感等方面。 壓縮成像 運(yùn)用壓縮感知原理，美國(guó) RICE大學(xué)已經(jīng)成功研制了 “單像素”壓縮數(shù)碼照相機(jī)，設(shè)計(jì)的原理是首先通過(guò)光路系統(tǒng)將成像目標(biāo)投影到一個(gè)數(shù)字微鏡器件上，然后其反射光由透鏡聚焦到單個(gè)光敏二極管上，光敏二極管兩端的電壓值即為一個(gè)測(cè)量值 y，將此投影操作重復(fù) M次，得到測(cè)量向量 y，然后用最小全變分算法構(gòu)建的數(shù)字信號(hào)處理器重構(gòu)原始圖像 f。數(shù)字微鏡器件由數(shù)字電壓信號(hào)控制微鏡片的機(jī)械運(yùn)動(dòng)以實(shí)現(xiàn)對(duì)入射光線(xiàn)的調(diào)整，相當(dāng)于隨機(jī)觀(guān)測(cè)矩陣 Φ。由于該相機(jī)直接獲取的是 M次隨機(jī)線(xiàn)性測(cè)量值，而不是獲取原始信號(hào)的 N (M N)個(gè)像素值，為低像素相機(jī)拍攝高質(zhì)量的圖像提供了可能。而且壓縮感知技術(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)換器件帶寬的要求。設(shè)計(jì)的重點(diǎn)由傳統(tǒng)的設(shè)計(jì)昂貴的接收端硬件轉(zhuǎn)化成為設(shè)計(jì)新穎可靠的信號(hào)恢復(fù)算法，從而簡(jiǎn)化了雷達(dá)成像系統(tǒng)。 Bhattacharya等人將壓縮感知理論應(yīng)用到合成孔徑雷達(dá)圖像數(shù)據(jù)獲取上，從而解決了海量數(shù)據(jù)的采集和存儲(chǔ)問(wèn)題，顯著降低了衛(wèi)星圖像處理的計(jì)算代價(jià)。另外，壓縮傳感技術(shù)也可以應(yīng)用于醫(yī)學(xué)成像領(lǐng)域，如稀疏核磁共振成像、壓縮感知三維 磁共振波譜成像等等。 模擬信息轉(zhuǎn)換 對(duì)于帶寬非常高的信號(hào)，比如雷達(dá)和通信信號(hào)處理系統(tǒng)涉及的射頻信號(hào)，根據(jù)奈奎斯特定理，要獲得完整的信號(hào)信息，所采用的模數(shù)轉(zhuǎn)換器必須具有很高的采樣頻率。然而由于傳感器及轉(zhuǎn)換硬件性能的限制，獲得的信號(hào)的帶寬要遠(yuǎn)遠(yuǎn)低于實(shí)際信號(hào)的帶寬，存在較大的信息的丟失。對(duì)此 Kriolos等人設(shè)計(jì)了基于壓縮感知理論的模擬 /信息轉(zhuǎn)換器，利用壓縮感知理論中測(cè)量信息可以得到完整信號(hào)的原理。首先獲得原始信號(hào)的線(xiàn)性測(cè)量，再利用后端數(shù)字信號(hào)處理器重構(gòu)原始信號(hào)或者直接計(jì)算原始信號(hào)的統(tǒng)計(jì)數(shù)據(jù)等信息。 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ī)采樣。然而這種方法卻需要多個(gè)模數(shù)轉(zhuǎn)換芯片，每個(gè)芯片利用率不太高。第 28 二種模型采用一組電容和數(shù)字控制換向器隨機(jī)采樣，該系統(tǒng)只需要一個(gè)模數(shù)轉(zhuǎn)換芯片即可。 生物傳感 生物傳感中的傳統(tǒng) DNA芯片能平行測(cè)量多個(gè)有機(jī)體，但是只能識(shí)別有限種類(lèi)的有機(jī)體， Sheikh等人運(yùn)用壓縮感知和群組檢測(cè)原理設(shè)計(jì)的壓 縮感知 DNA芯片克服了這個(gè)缺點(diǎn)，壓縮感知 DNA芯片中的每個(gè)探測(cè)點(diǎn)都能識(shí)別一組目標(biāo)，從而明顯減少了所需探測(cè)點(diǎn)數(shù)量。此外，基于生物體基因序列稀疏特性， Sheikh等驗(yàn)證了可以通過(guò)置信傳播的方法實(shí)現(xiàn)壓縮感知 DNA芯片中的信號(hào)重構(gòu)。 除此之外，壓縮感知理論還被應(yīng)用于信號(hào)的檢測(cè)分類(lèi)、數(shù)據(jù)的通信、無(wú)線(xiàn)傳感器網(wǎng)絡(luò)應(yīng)用和地球物理數(shù)據(jù)的分析等眾多的領(lǐng)域。 本章小結(jié) 本章詳細(xì)描述了壓縮感知理論基本框架。壓縮感知理論是一個(gè)非常簡(jiǎn)單有效的信號(hào)采集協(xié)議，它以較低采樣速率和獨(dú)立于信號(hào)的采樣方式采樣信號(hào)，然后又用強(qiáng)大的計(jì)算能力從 看上去不完整的觀(guān)測(cè)集合中重構(gòu)原信號(hào)。對(duì)壓縮感知理論實(shí)現(xiàn)的兩個(gè)前提要求 ——信號(hào)稀疏性及觀(guān)測(cè)矩陣和稀疏表示基之間滿(mǎn)足不相干性進(jìn)行了詳細(xì)的論述，著重介紹了信號(hào)稀疏變換、觀(guān)測(cè)矩陣設(shè)計(jì)和重構(gòu)算法三個(gè)方面的最新研究進(jìn)展情況。 壓縮感知理論是近幾年剛剛興起的理論，但卻展現(xiàn)了強(qiáng)大的生命力引起了廣泛的關(guān)注，下面我們將對(duì)該理論的歷史和發(fā)展歷程做出介紹。 29 第 4章 CS 在無(wú)線(xiàn)傳感網(wǎng)中的應(yīng)用 前文我們已經(jīng)對(duì)壓縮感知（ CS）理論做了叫詳細(xì)的介紹，下面我將介紹將壓縮感知應(yīng)用于無(wú)線(xiàn)傳感的優(yōu)勢(shì)以及采用 OMP 算法，實(shí)現(xiàn)對(duì)一維 信號(hào)和二維信號(hào)圖像的CS 重構(gòu)。 研究背景 前面緒論中已經(jīng)提到無(wú)線(xiàn)傳感網(wǎng)中的一些感知數(shù)據(jù)具有時(shí)間相關(guān)性和空間相關(guān)性，利用這種數(shù)據(jù)特點(diǎn)，人們可以對(duì)感知數(shù)據(jù)進(jìn)行了壓縮處理。下面將介紹已有的基于相關(guān)性的數(shù)據(jù)壓縮技術(shù)，并闡明利用 CS 壓縮數(shù)據(jù)的優(yōu)勢(shì)。 基于感知數(shù)據(jù)相關(guān)性的壓縮 利用傳感數(shù)據(jù)間的時(shí)間相關(guān)性，文獻(xiàn) [13]提出了節(jié)省一個(gè)傳感器節(jié)點(diǎn)內(nèi)存和計(jì)算資源的無(wú)損壓縮算法。利用傳感數(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ù)壓縮中，降低了傳輸能耗。文獻(xiàn) [33]在時(shí)域和空間域提出了多分辨率和查詢(xún)（ Multiresolution Compression and Query, MCQ）架構(gòu)，用離散余弦變換和差分編碼技術(shù)來(lái)降低數(shù)據(jù)冗余度，延長(zhǎng)網(wǎng)絡(luò)壽命。但是這些算法并沒(méi)有綜合考慮時(shí)間相關(guān)性和空間相關(guān)性，文獻(xiàn) [46]將融合了這 兩種相關(guān)性的分布式信源編碼運(yùn)用到傳感網(wǎng)的數(shù)據(jù)壓縮中。在一些分布式編碼算法中，需要進(jìn)行傳感器節(jié)點(diǎn)間的信息交換，傳輸這些信息需要消耗能量，因此，文獻(xiàn) [13,22]提出了基于聯(lián)合稀疏模型的分布式壓縮感知算法，既采用了兩種相關(guān)性，又不需要傳感器節(jié)點(diǎn)之間交換信息，而且能夠大大降低所需要傳輸?shù)臏y(cè)量值的數(shù)目，在此基礎(chǔ)上，文獻(xiàn) [21]還利用貝爾實(shí)驗(yàn)室所采集的實(shí)際數(shù)據(jù)進(jìn)行了仿真驗(yàn)證。另外文獻(xiàn)