【正文】 在一些分布式編碼算法中，需要進(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) [33]在時(shí)域和空間域提出了多分辨率和查詢（ Multiresolution Compression and Query, MCQ）架構(gòu)，用離散余弦變換和差分編碼技術(shù)來降低數(shù)據(jù)冗余度，延長(zhǎng)網(wǎng)絡(luò)壽命。 基于感知數(shù)據(jù)相關(guān)性的壓縮 利用傳 感數(shù)據(jù)間的時(shí)間相關(guān)性，文獻(xiàn) [13]提出了節(jié)省一個(gè)傳感器節(jié)點(diǎn)內(nèi)存和計(jì)算資源的無損壓縮算法。 研究背景 前面緒論中已經(jīng)提到無線傳感網(wǎng)中的一些感知數(shù)據(jù)具有時(shí)間相關(guān)性和空間相關(guān)性，利用這種數(shù)據(jù)特點(diǎn)，人們可以對(duì)感知數(shù)據(jù)進(jìn)行了壓縮處理。 壓縮感知理論是近幾年剛剛興起的理論，但卻展現(xiàn)了強(qiáng)大的生命力引起了廣泛的關(guān)注，下面我 們將對(duì)該理論的歷史和發(fā)展歷程做出介紹。壓縮感知理論是一個(gè)非常簡(jiǎn)單有效的信號(hào)采集協(xié)議，它以較低采樣速率和獨(dú)立于信號(hào)的采樣方式采樣信號(hào)，然后又用強(qiáng)大的計(jì)算能力從看上去不完整的觀測(cè)集合中重構(gòu)原信號(hào)。 除此之外，壓縮感知理論還被應(yīng)用于信號(hào)的檢測(cè)分類、數(shù)據(jù)的通信、無線傳感器網(wǎng) 絡(luò)應(yīng)用和地球物理數(shù)據(jù)的分析等眾多的領(lǐng)域。 生物傳感 生物傳感中的傳統(tǒng) DNA芯片能平行測(cè)量多個(gè)有機(jī)體，但是只能識(shí)別有限種類的有機(jī)體， Sheikh等人運(yùn)用壓縮感知和群組檢測(cè)原理設(shè)計(jì)的壓縮感知 DNA芯片克服了這個(gè)缺點(diǎn)，壓縮感知 DNA芯片中的每個(gè)探測(cè)點(diǎn)都能識(shí)別一組目標(biāo)，從而明顯減少了所需探測(cè)點(diǎn)數(shù)量。然而這種方法卻需要多個(gè)模數(shù)轉(zhuǎn)換芯片，每個(gè)芯片利用率不太高。首先獲得原始信號(hào)的線性測(cè)量，再利用后端數(shù)字信號(hào)處理器重構(gòu)原始信號(hào)或者直接計(jì)算原始信號(hào)的統(tǒng)計(jì)數(shù)據(jù)等信息。然而由于傳感器及轉(zhuǎn)換硬件性能的限制，獲得的信號(hào)的帶寬要遠(yuǎn)遠(yuǎn)低于實(shí)際信號(hào)的帶寬，存在較大的信息的丟失。另外，壓縮傳感技術(shù)也可以應(yīng)用于醫(yī)學(xué)成像領(lǐng)域，如稀疏核磁共振成像、壓縮感知三維磁共振波譜成像等等。設(shè)計(jì)的重點(diǎn)由傳統(tǒng)的設(shè)計(jì)昂貴的接收端硬件轉(zhuǎn)化成為設(shè)計(jì)新穎可靠的信號(hào)恢復(fù)算法，從而簡(jiǎn)化了雷達(dá)成像系統(tǒng)。由于該相機(jī)直接獲取的是 M次隨機(jī)線性測(cè)量值，而不是獲取原始信號(hào)的 N (M N)個(gè)像素值，為低像素相機(jī)拍攝高質(zhì)量的圖像提供了可能。 壓縮成像 運(yùn)用壓縮感知原理，美國 RICE大學(xué)已經(jīng)成功研制了“單像素”壓縮數(shù)碼照相機(jī)，設(shè)計(jì)的原理是首先通過光路系統(tǒng)將成像目標(biāo)投影到一個(gè)數(shù)字微鏡器件上，然后其反射光由透鏡聚焦到單個(gè)光敏二極管上，光敏二極管兩端的電壓值即為一個(gè)測(cè)量值 y，將此投影操作重復(fù) M次，得到測(cè)量向量 y，然后用最小全變分算法構(gòu)建的數(shù)字信號(hào)處理器重構(gòu)原始圖像 f。 27 第 3 章 壓縮感知理論應(yīng) 用概述 壓縮傳感理論帶來了傳統(tǒng)信號(hào)采樣理論的變革，而且具有很廣闊的應(yīng)用前景和場(chǎng)合。 這兩種方法主要的不同就在于第一種方式不需要復(fù)雜的路由信息。假設(shè)節(jié)點(diǎn)能夠進(jìn)行本地通信，并能建立一條路由，從而與某個(gè)確定的簇頭節(jié)點(diǎn)之間形成生成樹。 （ 2） 第二種：數(shù)字通信方式 數(shù)字通信方式，即傳輸?shù)臏y(cè)量值是量化后的值。由于無線電波的累加性質(zhì)，在 k次傳輸后 sink節(jié)點(diǎn)最終得到的接收信號(hào)為 ?? ????nj j Axvy 1 ?? （式 ） 其中ω為通信過程中產(chǎn)生的噪聲。 （ 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元素。 壓縮感知在傳感網(wǎng)中的觀測(cè)方式 之前已經(jīng)提及將壓縮感知運(yùn)用到傳感網(wǎng)中，即在節(jié)點(diǎn)處得到觀測(cè)值數(shù)據(jù)并傳給sink節(jié)點(diǎn)（或者融合中心）。而且，目前的重構(gòu)算法對(duì)含噪信號(hào)或者采樣過程中引入噪聲的信號(hào)重構(gòu)效果不夠理想。 （ 3）重構(gòu)算法是 NP 問題。 當(dāng)然，目前的壓縮感知理論還不是特別完善， 尚存在一些問題需要研究，在這里將列出其中幾個(gè)問題： （ 1）實(shí)際應(yīng)用 領(lǐng)域中，測(cè)量到的數(shù)據(jù)可能無法包含信號(hào)的全局信息，例如最傳統(tǒng)的攝像問題，每個(gè)感光器件所感知到的只是一小塊圖像而不是什么全局信息。 （ 3）具有抗干擾能力。以 X 光斷層掃描為例，眾所周知 ， X 光輻射會(huì)對(duì)病人造成身體損害，而壓縮感知的特點(diǎn)使得我們可以用比經(jīng)典少得多的輻射劑量來進(jìn)行數(shù)據(jù)采集，這在醫(yī)學(xué)上的意義是不言而喻的。這樣做的好處就是將信號(hào)壓縮這一端的過程簡(jiǎn)單化，而將復(fù)雜的部分交給數(shù)據(jù)還原的這一端來做。 由上面的分析可知，重構(gòu)算法和所需的觀測(cè)次數(shù)密切相關(guān)，當(dāng)前，壓縮感知 理論的信號(hào)重構(gòu)問題的研究主要集中在如何構(gòu)造穩(wěn) 定的、計(jì)算復(fù)雜度較低的、對(duì) 觀測(cè)數(shù)量要求較少的重構(gòu)算法來精確地恢復(fù)原信號(hào)。凸松弛法重構(gòu)信號(hào)所需的觀測(cè)次數(shù)最少， 但往往計(jì)算負(fù)擔(dān)很重。 （ 3）組合算法：這類方法要求信號(hào)的采樣支持通過分組測(cè)試快速重建，如傅 立葉采樣，鏈?zhǔn)阶粉櫤?HHS追蹤等。這些算法包括 MP算法， OMP算法，分段 OMP算法（ StOMP）和正則化 OMP（ ROMP）算法。利用)log( 2NKO個(gè)采樣觀測(cè)重構(gòu)信號(hào)，需要計(jì)算量為 )loglog(22 KNKO，該方法對(duì)特別稀疏信號(hào)的恢復(fù)計(jì)算性能較高，但當(dāng)信號(hào)的稀疏度減少，需要的采樣點(diǎn)數(shù)會(huì)迅速增加，甚至超過信號(hào)本身的長(zhǎng)度，這就失去了壓縮采樣的意義。 Graham Cormode等人，提出利用分組測(cè)試和隨機(jī)子集選取來估計(jì)稀疏信號(hào)的非零系數(shù)的位置和取值，該方法需要的采樣數(shù)為 )log(2NKOM?，信號(hào)重構(gòu)的計(jì)算復(fù)雜度為)log( 2NKO，得到重構(gòu)信號(hào)的速 度更快。 在上述各種方法中，觀測(cè)矩陣中的所有值都非零，這樣信號(hào)采樣過程的計(jì)算量是O(MN)，在大規(guī)模的數(shù)據(jù)面前，這個(gè)量級(jí)還是非常大的。它將 OMP進(jìn)行一定程度的簡(jiǎn)化，以逼近精度為代價(jià)進(jìn)一步提高了計(jì)算速度（計(jì)算復(fù)雜度為 O(N)），更加適合于求解大規(guī)模問題。例如 OMP算法，需要 cKM?，)ln(2 Nc?個(gè)采樣點(diǎn)數(shù)才能以較高的概率恢復(fù)信號(hào)，信號(hào)重構(gòu)的計(jì)算復(fù)雜度為)( 2NKO。該方法針對(duì) BP、 MP和 OMP方法沒 有考慮信號(hào)的多尺度分解時(shí)稀疏信號(hào)在各子帶位置的關(guān)系，將稀疏系數(shù)的樹型結(jié)構(gòu)加以利用，進(jìn)一步提升了重構(gòu)信號(hào)的精度和求解的速度。 （ MP）和正交匹配追蹤（ OMP）算法來求解優(yōu)化問題重構(gòu)信號(hào)，大大提高了計(jì)算的速度，且易于實(shí)現(xiàn)。通過在凸集上交替投影（ Projections onto Convex Sets）的方法，可以快速求解線性規(guī)劃問題。 針對(duì)上述問題， 2021 年 1 月 Cand232。s 和 Donoho 近來提出一種可行的基于線性規(guī)劃的重構(gòu)方法，論證了只使用對(duì)信號(hào)的 cK（ c =3或者 4）個(gè)觀測(cè)值，利用線性規(guī)劃 的方法就可以得到和組合搜索相同的解。然而，求得最小的 0范數(shù)解需要進(jìn)行組合搜索，計(jì)算復(fù)雜度相當(dāng)高。于是用于過完備庫下稀疏分解的方法都可以用于求解壓縮感知理論的重構(gòu)計(jì)算。 重構(gòu)算法 由前面的分析可知， 過完備庫下的稀疏分解問題和壓縮感知理論的重構(gòu)問題都是線性約束下的 0范數(shù)求解問題。（ 3）最小化帶線性方程約束的 1范數(shù)可以很容易地被轉(zhuǎn)化為線性規(guī)劃問題，于是可以找到更高效的求解算法。 23 由以上討論我們可以得出結(jié)論：（ 1）相關(guān)性在 CS中起著至關(guān)重要的作用：?和?相關(guān)性越小，需要采樣的數(shù)目就越少。 Chen， Donoho和 Saunders指出，求解一個(gè)更加簡(jiǎn)單的 1范數(shù)最小優(yōu)化問題會(huì) 產(chǎn)生同等的解（要求?和?不相關(guān)）： 1min XT? . YXXA TCS ???? （式 ） 稍微的差別使得問題變成了一個(gè) 凸優(yōu)化問題，于是可以方便地化簡(jiǎn)為線性規(guī)劃問題，典型算法代表： BP算法?？梢?，壓縮感知和稀疏分解問題從數(shù)學(xué)意義上講是同樣的優(yōu)化問題。 在信號(hào) X 稀疏或可壓縮的前提下，求解欠定方程組XAY CS?的問題轉(zhuǎn)化為最小0范數(shù)問題： 0min XT? . YXXA TCS ???? （式 ） 但是，它需要列出 X中所有非零項(xiàng)位置的KNC種可能的線性組合，才能得到最優(yōu)解。但是，文獻(xiàn) [30]和 [23]均指出由于信號(hào) X 是稀疏的或可壓縮的，這個(gè)前提從根本上改變了問題，使得問題可解，而觀測(cè)矩陣具有 RIP性質(zhì)也為從 M 個(gè)觀測(cè)值中精確恢復(fù)信號(hào)提供了理論保證。乍一看，我們幾乎不可能期望從 Y 恢復(fù)每個(gè)NRX?。 稀疏信號(hào)的重構(gòu) 壓縮感知理論的核心問題是從觀測(cè)得到的有限的 MN個(gè)觀測(cè)樣本中重構(gòu)出 N長(zhǎng)的原信號(hào)，即未知量個(gè)數(shù)比觀測(cè)量要多得多。文獻(xiàn) [56]則從信息論角度描述了信息論與 CS之間的聯(lián)系。但是，使用上述各種觀測(cè)矩陣進(jìn)行觀測(cè)后，都僅僅能保證以很高的概率去恢復(fù)信號(hào)，而不能保證百分之百地精確重構(gòu)信號(hào)。 目前，對(duì)觀測(cè)矩陣的研究是壓縮感知理論的一個(gè)重要方面?？傊?，隨機(jī)高斯矩陣與大多數(shù)固定正交基構(gòu)成的矩陣不相關(guān)，這一特性決定了選它作為觀測(cè)矩陣，其它正交基作為稀疏變換基時(shí)，CSA滿足 RIP性質(zhì)。隨機(jī)高斯矩陣?具有一個(gè)有用的性質(zhì)：對(duì)于一個(gè)NM?的隨機(jī)高斯矩陣 ，可以證明當(dāng) )/log(KNcKM?時(shí) 在很大概率下具有 RIP性質(zhì)（其中 c是一個(gè)很小的常數(shù)） 。通過選擇高斯隨機(jī)矩陣作為 即可高概率保證不相干性和 RIP性質(zhì)。不相干是指向量??i?不能用?i?稀疏表示。為了降低 問題的復(fù)雜度，能否找到一種易于實(shí)現(xiàn) RIP條件的替代方法成為構(gòu)造 觀測(cè)矩陣 的關(guān)鍵。從中可以看出，問題的關(guān)鍵是如何確定非零系數(shù)的位置來構(gòu)造出一個(gè)可解的M?線性方程組。s、 Tao等人提出的稀疏信號(hào)在觀測(cè)矩陣作用下必須保持的幾何性質(zhì)相一致。對(duì)此，有限等距性質(zhì)（ restricted isometry property， RIP）給出了存在確定解的充要條件。然而，如果具有 K 項(xiàng)稀疏性（ KM），則該問題有望求出確定解。（ b）是（ a）圖的另一種表達(dá)，變換后的 系數(shù)向量?是稀疏的， K=3，觀測(cè)得到的 Y是非零系數(shù) i?對(duì)應(yīng)的四個(gè)列向量的線性組合。這里，采樣過程是非自適應(yīng)的，也就是說，?無須根據(jù)信號(hào) X 而變化，觀測(cè)的不再是信號(hào)的點(diǎn)采樣而是信號(hào)的更一般的線性泛函。顯然，如果觀測(cè)過程破壞了 X中的信息，重構(gòu) 是不可能的。 壓縮感知理論中，通過變換得到信號(hào)的稀疏系數(shù)向量XT???后，需要設(shè)計(jì)觀測(cè)部分，它圍繞觀測(cè)矩陣?展開。此外，觀測(cè)過程獨(dú) 立于信號(hào)本身。 20 觀測(cè)矩陣設(shè)計(jì) 觀測(cè)部分的設(shè)計(jì)其實(shí)就是設(shè)計(jì)高效的觀測(cè)矩陣，換句話說，就是要設(shè)計(jì)一個(gè) 能捕捉稀疏信號(hào)中有 用信息的高效的觀測(cè)（即采樣）協(xié)議，從而將該稀疏信號(hào)壓 縮成少量的數(shù)據(jù)。 MP算法雖然收斂速度較 BP快，但不具備全局最優(yōu)性，且計(jì)算復(fù)雜度仍然很大。 Donoho等人另辟蹊徑，提出了 BP算法。還可以把其它的具有不同形狀的基函數(shù)歸入字典，如適合刻畫紋理的 Gabor基、適合刻畫輪廓的 Curvelet基等等。 從非線性逼近角度來講，信號(hào)的稀疏逼近包含兩個(gè)層面：一是根據(jù)目標(biāo)函數(shù)從一個(gè)給定的基庫中挑選好的或最好的基；二是從這個(gè)好的基中挑選最好的 K項(xiàng)組合。 目前信號(hào)在過完備字典下的稀疏表示的研究集中在兩個(gè)方面：（ 1）如何構(gòu)造一個(gè)適合某一類信號(hào)的過完備字典；（ 2）如何設(shè)計(jì)快速有效的稀疏分解算法。 過完備庫下的信號(hào)稀疏表示方法最早由 Mallat和 Zhang于 1993年首次提出， 并引入了 MP算法。 字典的選擇應(yīng)盡可能好地符合被逼近信號(hào)的結(jié)構(gòu)，其構(gòu)成可以沒有任何限制。即在某個(gè)正交基字典里，自適應(yīng)地尋找可以逼近某一種信號(hào)特征的最優(yōu)正交基，根據(jù)不同的信號(hào)尋找最適合信號(hào)特性的一組正交基，對(duì)信號(hào)進(jìn)行變換以得到最稀疏的信號(hào)表示。 Gabriel Peyr233。 文獻(xiàn) [30]指出光滑信號(hào)的 Fourier系數(shù)、小波系數(shù)、有界變差函數(shù)的全變差范數(shù)、振蕩信號(hào)的 Gabor系數(shù)及具有不連續(xù)邊緣的圖像信號(hào)的 Curvelet系數(shù)等都具有足夠的稀疏性，可以通過壓縮感知理論恢復(fù)信號(hào)。 Cand232。 如何找到信號(hào)最佳的稀疏域？這是壓縮感知理論應(yīng)用的基礎(chǔ)和前提，只有選擇合適的基表示信號(hào) 才能保證信號(hào)的稀疏度，從而保證信號(hào)的恢復(fù)精度。 文獻(xiàn) [23]給出稀疏的定義：信號(hào) X在正交基?下的變換系數(shù)向量為XT???，假如對(duì)于 0p2和 R 0，這些系數(shù)滿足： （ 式 ） 則說明系數(shù)向量?在某種意義下是稀疏的。 下面我們對(duì)壓縮感知理論的這三個(gè)關(guān)鍵技術(shù)做一個(gè)詳細(xì)的總結(jié)和分析，以為后文對(duì)壓縮感知理論在圖像重構(gòu)方面的研究打下基礎(chǔ)。 （ 3）重構(gòu)算法的設(shè)計(jì)。即如何設(shè)計(jì)一個(gè)平穩(wěn)且滿足受限等距特性條件或者與變換基 Ψ 滿足不相關(guān)約束條件的 M N 維觀測(cè)矩陣 Φ，以保證信號(hào)稀疏表示后的向量 Θ能從原來的 N 維