【正文】 于線性規(guī)劃的重構(gòu)方法，論證了只使用對信號的cK（c =3或者4）個觀測值，利用線性規(guī)劃的方法就可以得到和組合搜索相同的解。然而，求得最小的0范數(shù)解需要進行組合搜索，計算復(fù)雜度相當(dāng)高。于是用于過完備庫下稀疏分解的方法都可以用于求解壓縮感知理論的重構(gòu)計算。 重構(gòu)算法由前面的分析可知，過完備庫下的稀疏分解問題和壓縮感知理論的重構(gòu)問題都是線性約束下的0范數(shù)求解問題。（3）最小化帶線性方程約束的1范數(shù)可以很容易地被轉(zhuǎn)化為線性規(guī)劃問題，于是可以找到更高效的求解算法。由以上討論我們可以得出結(jié)論：（1）相關(guān)性在CS中起著至關(guān)重要的作用：和相關(guān)性越小，需要采樣的數(shù)目就越少。Chen，Donoho和Saunders指出，求解一個更加簡單的1范數(shù)最小優(yōu)化問題會產(chǎn)生同等的解（要求和不相關(guān)）： . （）稍微的差別使得問題變成了一個凸優(yōu)化問題，于是可以方便地化簡為線性規(guī)劃問題，典型算法代表：BP算法?？梢?，壓縮感知和稀疏分解問題從數(shù)學(xué)意義上講是同樣的優(yōu)化問題。在信號X 稀疏或可壓縮的前提下，求解欠定方程組的問題轉(zhuǎn)化為最小0范數(shù)問題： . （） 但是，它需要列出X中所有非零項位置的種可能的線性組合，才能得到最優(yōu)解。但是，文獻[30]和[23]均指出由于信號X 是稀疏的或可壓縮的，這個前提從根本上改變了問題，使得問題可解，而觀測矩陣具有RIP性質(zhì)也為從M 個觀測值中精確恢復(fù)信號提供了理論保證。乍一看，我們幾乎不可能期望從Y 恢復(fù)每個。 稀疏信號的重構(gòu)壓縮感知理論的核心問題是從觀測得到的有限的MN個觀測樣本中重構(gòu)出N長的原信號，即未知量個數(shù)比觀測量要多得多。文獻[56]則從信息論角度描述了信息論與CS之間的聯(lián)系。但是，使用上述各種觀測矩陣進行觀測后，都僅僅能保證以很高的概率去恢復(fù)信號，而不能保證百分之百地精確重構(gòu)信號。 目前，對觀測矩陣的研究是壓縮感知理論的一個重要方面。總之，隨機高斯矩陣與大多數(shù)固定正交基構(gòu)成的矩陣不相關(guān)，這一特性決定了選它作為觀測矩陣，其它正交基作為稀疏變換基時，滿足RIP性質(zhì)。隨機高斯矩陣具有一個有用的性質(zhì)：對于一個的隨機高斯矩陣，可以證明當(dāng)時在很大概率下具有RIP性質(zhì)（其中c是一個很小的常數(shù)）。通過選擇高斯隨機矩陣作為即可高概率保證不相干性和RIP性質(zhì)。不相干是指向量不能用稀疏表示。為了降低問題的復(fù)雜度，能否找到一種易于實現(xiàn)RIP條件的替代方法成為構(gòu)造觀測矩陣F 的關(guān)鍵。從中可以看出，問題的關(guān)鍵是如何確定非零系數(shù)的位置來構(gòu)造出一個可解的線性方程組。s、Tao等人提出的稀疏信號在觀測矩陣作用下必須保持的幾何性質(zhì)相一致。對此，有限等距性質(zhì)（restricted isometry property， RIP）給出了存在確定解的充要條件。然而，如果具有K 項稀疏性（KM），則該問題有望求出確定解。（b）是（a）圖的另一種表達，變換后的系數(shù)向量是稀疏的，K=3，觀測得到的Y是非零系數(shù)對應(yīng)的四個列向量的線性組合。這里，采樣過程是非自適應(yīng)的，也就是說，無須根據(jù)信號X 而變化，觀測的不再是信號的點采樣而是信號的更一般的線性泛函。顯然，如果觀測過程破壞了X中的信息，重構(gòu)是不可能的。壓縮感知理論中，通過變換得到信號的稀疏系數(shù)向量后，需要設(shè)計觀測部分，它圍繞觀測矩陣展開。此外，觀測過程獨立于信號本身。 觀測矩陣設(shè)計觀測部分的設(shè)計其實就是設(shè)計高效的觀測矩陣，換句話說，就是要設(shè)計一個能捕捉稀疏信號中有用信息的高效的觀測（即采樣）協(xié)議，從而將該稀疏信號壓縮成少量的數(shù)據(jù)。MP算法雖然收斂速度較BP快，但不具備全局最優(yōu)性，且計算復(fù)雜度仍然很大。Donoho等人另辟蹊徑，提出了BP算法。還可以把其它的具有不同形狀的基函數(shù)歸入字典，如適合刻畫紋理的Gabor基、適合刻畫輪廓的Curvelet基等等。從非線性逼近角度來講，信號的稀疏逼近包含兩個層面：一是根據(jù)目標函數(shù)從一個給定的基庫中挑選好的或最好的基；二是從這個好的基中挑選最好的K項組合。目前信號在過完備字典下的稀疏表示的研究集中在兩個方面：（1）如何構(gòu)造一個適合某一類信號的過完備字典；（2）如何設(shè)計快速有效的稀疏分解算法。過完備庫下的信號稀疏表示方法最早由Mallat和Zhang于1993年首次提出， 并引入了MP算法。字典的選擇應(yīng)盡可能好地符合被逼近信號的結(jié)構(gòu)，其構(gòu)成可以沒有任何限制。即在某個正交基字典里，自適應(yīng)地尋找可以逼近某一種信號特征的最優(yōu)正交基，根據(jù)不同的信號尋找最適合信號特性的一組正交基，對信號進行變換以得到最稀疏的信號表示。Gabriel Peyr233。文獻[30]指出光滑信號的Fourier系數(shù)、小波系數(shù)、有界變差函數(shù)的全變差范數(shù)、振蕩信號的Gabor系數(shù)及具有不連續(xù)邊緣的圖像信號的Curvelet系數(shù)等都具有足夠的稀疏性，可以通過壓縮感知理論恢復(fù)信號。Cand232。如何找到信號最佳的稀疏域？這是壓縮感知理論應(yīng)用的基礎(chǔ)和前提，只有選擇合適的基表示信號才能保證信號的稀疏度，從而保證信號的恢復(fù)精度。文獻[23]給出稀疏的定義：信號X在正交基下的變換系數(shù)向量為，假如對于0p2和R 0，這些系數(shù)滿足： （）則說明系數(shù)向量在某種意義下是稀疏的。下面我們對壓縮感知理論的這三個關(guān)鍵技術(shù)做一個詳細的總結(jié)和分析，以為后文對壓縮感知理論在圖像重構(gòu)方面的研究打下基礎(chǔ)。（3）重構(gòu)算法的設(shè)計。即如何設(shè)計一個平穩(wěn)且滿足受限等距特性條件或者與變換基Ψ 滿足不相關(guān)約束條件的M N 維觀測矩陣Φ，以保證信號稀疏表示后的向量Θ能從原來的N 維降到M 維時所包含的重要信息沒有受到破壞，從而保證原始信號的準確重構(gòu)。即對于信號 ，如何找到一個合適的正交基或者緊框架Ψ，以使得原始信號在Ψ上的表示是稀疏的。最后設(shè)計合適的重構(gòu)算法從所得到的觀測值和原來的觀測矩陣來重構(gòu)原始始號。在信號的編碼測量即觀測矩陣的設(shè)計過程中，要選擇穩(wěn)定的觀測矩陣，觀測矩陣的選取必須滿足受限等距特性(Restricted Isometry Property，RIP)準則，才能保證信號的投影能夠保持原始信號的結(jié)構(gòu)特征。信號必須得在某種變換下才可以進行稀疏表示。 三個關(guān)鍵技術(shù)從以上壓縮感知理論的介紹中我們可以看出，壓縮感知理論主要包括以下三個方面的內(nèi)容：（1）信號稀疏表示；（2）信號的編碼測量即觀測矩陣的設(shè)計；（3）信號重構(gòu)算法的設(shè)計。研究者們通過大量的實驗分析，得出如下結(jié)論：精確重構(gòu)所需要的觀測值個數(shù)依賴于稀疏變換基和觀測基之間的不相關(guān)性。例如，可以通過在單位球面上獨立均勻地采樣并做規(guī)范正交化得到，此時，和間的相關(guān)性以很高的概率為。（3）為隨機矩陣，則可以是任何固定的基。這一點對于高效的數(shù)字計算是至關(guān)重要的。人們對noiselets感興趣基于以下兩個事實：1）它們和為圖像數(shù)據(jù)和其它類型的數(shù)據(jù)提供稀疏表示的系統(tǒng)不相關(guān)；2）它們具有快速算法。這也可以擴展到高維情況。（2）為小波基，是noiselet。（1）是尖峰基，為傅立葉基，則有。壓縮采樣研究的是具有低相關(guān)性的兩個系統(tǒng)。如果和包含了相關(guān)的元素，則相關(guān)性很大；否則，就很小。文獻[3]給出了相關(guān)性度量的具體定義，如下。因此在CS理論中隨機矩陣被廣泛應(yīng)用于CS觀測中。許多對基都滿足不相關(guān)性質(zhì)，例如，三角尖峰和傅里葉基中的正弦波不相關(guān)，傅里葉基和小波基不相關(guān)。由于MN，從觀測向量y中重構(gòu)信號x是一個欠定問題，然而信號稀疏的附加假設(shè)使得恢復(fù)成為可能也是可行的。用矩陣表示，則有。這就是壓縮感知（CS）理論的核心內(nèi)容。（b）coins圖像的9/7小波系數(shù)在一維下的表示 （c）1/16系數(shù)重構(gòu)圖像（PSNR=）(a)512x512的coins原始圖像2 不相關(guān)性 Cand232。而近幾年來Cand232。不過在傳統(tǒng)編碼中，這K個大系數(shù)的位置必須事先確定。我們稱至多有K個非零項的向量為K 稀疏，且有。現(xiàn)在稀疏的含義很清楚了：如果x在某個變換域下是稀疏或者可壓縮的，就意味著將x的系數(shù)按幅值大小排列衰減很快，那么x可以由K個大系數(shù)很好地逼近。本例中僅僅保留展開（）中的個大系數(shù)得到，其中表示系數(shù)向量的除K個大系數(shù)外其余置0的向量。（c）展示了這樣一個事實：將圖像在9/%，但肉眼很難察覺到失真。（a）是一幅具有N（N =512512）個像素點的coins圖像向量，我們在9/7小波基下展開該向量，如（），其中是為列向量構(gòu)成的的矩陣，是正交基。也就是說，中僅有K個非零，另外N K個都是零。如果信號在基下的展開系數(shù)在很小的集合上有值，我們就說該信號在域是稀疏的，如果有值序列集中在一個小范圍內(nèi)，那么我們就說該信號是可以壓縮的。為展開系數(shù)。不相關(guān)性表達了這樣的思想，正如時間域的Dirac或者沖擊信號可以在頻域展開那樣，在基Ψ下具有稀疏表示的信號一定可以在獲得它們的某個域中展開。更準確地說，CS利用了這樣一個事實，即許多自然信號在某個合適的基Ψ下具有簡潔的表達。前者屬于信號的性質(zhì)，后者和感知（觀測）形式有關(guān)。下面將從這三個方面詳細講述壓縮感知的關(guān)鍵技術(shù)。CS理論系統(tǒng)與傳統(tǒng)通信系統(tǒng)的類似關(guān)系如圖21所示：CS恢復(fù)CS測量 CS理論系統(tǒng)與傳統(tǒng)通信系統(tǒng)的類似關(guān)系 由圖21可知，在CS系統(tǒng)中，信源和信道編碼被CS測量（即一個矩陣與信號矢量相乘的形式）代替；信道和信源解碼則用CS恢復(fù)（即依賴于優(yōu)化準則的恢復(fù)算法）替代。在許多應(yīng)用中，包括數(shù)字圖像和視頻攝像中，奈奎斯特抽樣速率太高，不利于數(shù)據(jù)存儲和傳輸；在其他應(yīng)用，包括圖像系統(tǒng)（醫(yī)療瀏覽和雷達）、高速模數(shù)轉(zhuǎn)換中，增加抽樣速率代價也很昂貴。 第五章 對全文進行總結(jié)并展望下一步的研究工作。 第三章 進一步介紹由壓縮感知理論發(fā)展而來的分布式壓縮感知理論，分別描述了三種聯(lián)合稀疏模型及其應(yīng)用范圍，最后，將其與壓縮感知理論作了仿真性能比較。 本文內(nèi)容安排如下： 第一章 簡單介紹了課題的研究背景，包括現(xiàn)有的數(shù)據(jù)壓縮技術(shù)和有關(guān)無線傳感網(wǎng)絡(luò)的基本知識。這樣，通過傳輸少量數(shù)據(jù)就可以得到整個監(jiān)測區(qū)域內(nèi)的詳細情況。 圖14中監(jiān)測區(qū)域中有大量的無線傳感節(jié)點，傳感節(jié)點可以感知各種物理環(huán)境，包括聲音、溫度、壓力、地震等。無線傳感器網(wǎng)絡(luò)中的感知數(shù)據(jù)能夠進行壓縮是因為它具備數(shù)據(jù)壓縮的前提條件：首先，傳感器節(jié)點密度很大，節(jié)點之間感知的范圍相互重疊，這種高密度的節(jié)點分布一方面使得感知數(shù)據(jù)可靠性增強，另一方面也引起了數(shù)據(jù)冗余，使得相鄰節(jié)點之間所采集的數(shù)據(jù)具有高度相關(guān)性，稱為空間相關(guān)性；其次，由于傳感節(jié)點感知的物理數(shù)據(jù)大多數(shù)隨著時間變化很緩慢，所以同一個傳感器節(jié)點所感知的數(shù)據(jù)之間也有相關(guān)性，稱為時間相關(guān)性。 在這里，我們將說明利用壓縮技術(shù)來減少傳輸?shù)臄?shù)據(jù)量的必要性和可行性。 與傳統(tǒng)的網(wǎng)絡(luò)不同的是，傳統(tǒng)網(wǎng)絡(luò)以傳輸數(shù)據(jù)為目的，而無線傳感器網(wǎng)絡(luò)則是以數(shù)據(jù)為中心；與傳統(tǒng)的Ad Hoc網(wǎng)絡(luò)相比，無線傳感器網(wǎng)絡(luò)具有以下幾點特征： （1）網(wǎng)絡(luò)節(jié)點密度高，傳感節(jié)點數(shù)量多 （2）傳感器節(jié)點由電池供電 （3）網(wǎng)絡(luò)拓撲變化頻繁 （4）網(wǎng)絡(luò)具有容錯能力 無線傳感器網(wǎng)絡(luò)數(shù)據(jù)壓縮的必要性 因為在無線傳感器網(wǎng)絡(luò)中，每個傳感節(jié)點體積很小，而且分布非常密集，若是對所有采集的數(shù)據(jù)直接進行傳輸，則所需傳輸?shù)臄?shù)據(jù)量將是非常驚人的，會導(dǎo)致網(wǎng)絡(luò)擁塞，也會導(dǎo)致網(wǎng)絡(luò)壽命縮短；又由于傳感器節(jié)點由電池供電， 所以節(jié)點能量有限，而且無線傳感器網(wǎng)絡(luò)所布置的地方一般為人們不便于到達的地方，因此傳感器節(jié)點中的的電池很難更換。傳感器節(jié)點都分散在特定的感知區(qū)域，相互合作、實時監(jiān)測、感知和采集網(wǎng)絡(luò)周邊環(huán)境或監(jiān)測對象的溫度、聲波等各種信息。 （2）數(shù)據(jù)處理中轉(zhuǎn)站，這類節(jié)點不僅要完成采集的任務(wù)，還要接收鄰居節(jié)點的數(shù)據(jù)，一起轉(zhuǎn)發(fā)給距離基站更近的鄰居節(jié)點或者直接轉(zhuǎn)發(fā)到基站或匯聚節(jié)點。 無線傳感器網(wǎng)絡(luò)節(jié)點結(jié)構(gòu)圖 其中，數(shù)據(jù)采集模塊負責(zé)感知所需要的信息，數(shù)據(jù)處理和控制模塊負責(zé)對感知所得的信息和接收信息進行處理，通信模塊負責(zé)與其他節(jié)點進行通信，即發(fā)送或者接收信息，供電模塊則負責(zé)提供所需要的能量。 無線傳感器網(wǎng)絡(luò)概述 無線傳感器網(wǎng)絡(luò)一般由若干傳感器節(jié)點組成，節(jié)點是組成無線傳感器網(wǎng)絡(luò)的基本單位，它負責(zé)完成采集信息、融合并傳輸數(shù)據(jù)的功能。以上是關(guān)于壓縮感知理論與分布式壓縮感知理論的簡單介紹，詳細闡述將在第二章和第三章進行展開。就目前主流的兩種重建算法而言，基于1范數(shù)最小的重建算法計算量巨大，對于大規(guī)模信號無法應(yīng)用；貪婪算法雖然重建速度快，但是在信號重建質(zhì)量上還有待提高。 此外，迭代閾值法也得到了廣泛的應(yīng)用，此類算法也較易實現(xiàn)，計算量適中，在貪婪算法和凸優(yōu)化算法中都有應(yīng)用。二是凸優(yōu)化算法，它是把0范數(shù)放寬到1范數(shù)通過線性規(guī)劃求解的，此類算法主要包括梯度投影法、基追蹤法、最小角度回歸法等。首先生成一個零元素的矩陣Φ，在矩陣Φ的每一個列向量中，隨機地選取d個位置，然后在所選取的位置的值賦為1。首先生成一個向量u，由向量u生成相應(yīng)的輪換矩陣或托普利茲矩陣U，然后在矩陣U中隨機地選取其中的M行而構(gòu)造的矩陣Φ。生成大小為NN的哈達瑪矩陣，然后在生成矩陣中隨機地選取M行向量，構(gòu)成一個MN的矩陣。先生成NN的正交矩陣U（如傅里葉矩陣），然后在矩陣U中隨機地選取M行向量，對MN矩陣的列向量進行單位化得到測量矩陣。矩陣的每個元素獨立地服從對稱的貝努利分布，等概率為或。矩陣每個元素獨立地服從均值為0，方差為的高斯分布。Donoho給出壓縮感知概念的同時定性和定量的給出測量矩陣要滿足三個特征：(1)由測量矩陣的列向量組成的子矩陣的最小奇異值必須大于一定的常數(shù)；(2)測量矩陣的列向量體現(xiàn)某種類似噪聲的獨立隨機性；(3)滿足稀疏度的解是滿足1范數(shù)最小的向量。CandeS和Tao等證明:獨立同分布的高斯隨機測量矩陣可以成為普適的壓縮感知測量矩陣。壓縮感知理論中，通過變換得到信號的稀疏系數(shù)后，需要設(shè)計壓縮采樣系統(tǒng)的觀測部分，它圍繞觀測矩陣展開。目前信號在冗余字典下的稀疏表示的研究集中在兩個方面：一是如何構(gòu)造一個適合某一類信號的冗余字