屆電子畢業(yè)論文正文

1、目錄第1章 緒論11.1 研究背景和意義11.2 CS理論框架21.3 本文框架結(jié)構(gòu)4第2章 國內(nèi)外研究現(xiàn)狀62.1 從稀疏重構(gòu)到壓縮感知62.2 稀疏重構(gòu)算法和重構(gòu)條件研究72.3 壓縮感知在光學成像中的應用9第3章 壓縮感知（CS）基本理論123.1 壓縮感知背景123.2 壓縮感知理論13壓縮感知的前提條件稀疏性和不相干性133.2.2 三個關(guān)鍵技術(shù)17信號的稀疏表示173.2.4 觀測矩陣設(shè)計193.2.5 稀疏信號的重構(gòu)213.2.6 重構(gòu)算法223.3壓縮感知理論應用概述24壓縮成像243.3.2 模擬信息轉(zhuǎn)換253.3.3 生物傳感253.4 本章小結(jié)25第4章 壓縮感知實現(xiàn)及結(jié)

2、果分析264.1圖像壓縮基本理論26傳統(tǒng)圖像壓縮重構(gòu)方法264.1.2 圖像壓縮重構(gòu)質(zhì)量的評價274.2 壓縮感知理論算法對一維信號的實現(xiàn)284.2.1 正交匹配追蹤算法（OMP）294.2.2 算法的實現(xiàn)及結(jié)果分析304.3 壓縮感知理論算法對二維圖像重構(gòu)的實現(xiàn)334.3.1 基于小波變換的分塊壓縮感知理論334.3.2 實現(xiàn)步驟344.3.3 重構(gòu)結(jié)果及分析374.4 本章小結(jié)42第5章 總結(jié)與展望435.1 總結(jié)435.2 展望43參考文獻45致謝47附錄48第1章 緒論信號采樣是聯(lián)系模擬信源和數(shù)字信息的橋梁。隨著信息技術(shù)日新月異的進步，人們對信息的巨量需求造成了信號采樣、傳輸和存儲的巨

3、大壓力。如何緩解這種壓力又能有效提取承載在信號中的有用信息是信號與信息處理中急需解決的問題之一。近幾年來，在信號處理領(lǐng)域出現(xiàn)的壓縮感知理論（CS）打破了傳統(tǒng)采樣過程中信號采樣速率必須達到信號帶寬兩倍以上才能精確重構(gòu)原始信號的奈奎斯特采樣定理，使得信息存儲、處理和傳輸?shù)某杀敬蟠蠼档汀?.1 研究背景和意義信息技術(shù)的飛速發(fā)展使得人們對信息的需求量劇增。現(xiàn)實世界的模擬化和信號處理工具的數(shù)字化決定了信號采樣是從模擬信源獲取數(shù)字信息的必經(jīng)之路。 奈奎斯特采樣定理則是指導如何采樣的重要理論基礎(chǔ)。它指出，采樣速率必須達到信號帶寬的兩倍以上才能精確重構(gòu)信號。然而隨著人們對信息需求量的增加，攜帶信息的信號帶寬越

4、來越寬，以此為基礎(chǔ)的信號處理框架要求的采樣速率和處理速度也越來越高，因而對寬帶信號處理的困難在日益加劇。例如高分辨率地理資源觀測，其巨量數(shù)據(jù)傳輸和存儲就是一個艱難的工作。另一方面，在實際應用中，為了降低存儲、處理和傳輸?shù)某杀荆藗兂２捎脡嚎s方式以較少的比特數(shù)表示信號，大量的非重要的數(shù)據(jù)被拋棄。這種高速采樣再壓縮的過程浪費了大量的采樣資源，于是很自然地引出一個問題:能否利用其它變換空間描述信號，建立新的信號描述和處理的理論框架，使得在保證信息不損失的情況下，用遠低于奈奎斯特采樣定理要求的速率采樣信號，同時又可以完全恢復信號? 即能否將對信號的采樣轉(zhuǎn)變成對信息的采樣? 如果這個問題被解決，就可以極

5、大地降低信號的采樣頻率及數(shù)據(jù)存儲和傳輸代價，顯著地降低信號處理時間和計算成本，并將帶領(lǐng)信號處理進入一個新的革命時代。近幾年來出現(xiàn)的一種新穎的理論Compressed sensing(也稱為Compressive sampling) 表明這是可能的。 目前還沒有一個統(tǒng)一的中文詞匯與之對應，有人稱之為壓縮傳感，也有人稱其為壓縮感知(以下均采用壓縮感知) 。 壓縮感知理論與傳統(tǒng)奈奎斯特采樣定理不同，它指出，只要信號是可壓縮的或在某個變換域是稀疏的，那么就可以用一個與變換基不相關(guān)的觀測矩陣將變換所得高維信號投影到一個低維空間上，然后通過求解一個優(yōu)化問題就可以從這些少量的投影中以高概率重構(gòu)出原信號，可以

6、證明這樣的投影包含了重構(gòu)信號的足夠信息。 在該理論框架下，采樣速率不決定于信號的帶寬，而決定于信息在信號中的結(jié)構(gòu)和內(nèi)容。 事實上，壓縮感知理論的某些抽象結(jié)論源于Kashin創(chuàng)立的范函分析和逼近論， 最近由Candès，Romberg ，Tao和Donoho等人構(gòu)造了具體的算法并且通過研究表明了這一理論的巨大應用前景。從信號分析角度來講，傅立葉變換是信號和數(shù)字圖像處理的理論基礎(chǔ)，小波分析將信號和數(shù)字圖像處理帶入到一個嶄新的領(lǐng)域。 多尺度幾何分析是繼小波分析后的新一代信號分析工具，它具有多分辨、局部化和多方向性等優(yōu)良特性，更適合于處理圖像等高維信號。 這些研究工作都為壓縮感知理論奠定了基

7、礎(chǔ)。顯然，在壓縮感知理論中，圖像/信號的采樣和壓縮同時以低速率進行，使傳感器的采樣和計算成本大大降低，而信號的恢復過程是一個優(yōu)化計算的過程。 因此，該理論指出了將模擬信號直接采樣壓縮為數(shù)字形式的有效途徑，具有直接信息采樣特性。 由于從理論上講任何信號都具有可壓縮性，只能找到其相應的稀疏表示空間，就可以有效地進行壓縮采樣，這一理論必將給信號采樣方法帶來一次新的革命。 壓縮感知理論的引人之處還在于它對應用科學和工程的許多領(lǐng)域具有重要的影響和實踐意義， 如統(tǒng)計學、信息論、編碼等。本文以稀疏信號的壓縮觀測及重構(gòu)為主線，綜述了壓縮感知理論以及與之相關(guān)的信號稀疏變換、觀測矩陣設(shè)計、重構(gòu)算法等一系列最新理論

8、成果和應用研究，描述了國內(nèi)外的研究進進展，討論了其中的公開問題，展望了未來的研究方向。1.2 CS理論框架在傳統(tǒng)理論的指導下，信號X的編解碼過程如圖1.1所示：編碼端首先獲得X 的N點采樣值，經(jīng)變換后只保留其中K個最大的投影系數(shù)并對它們的幅度和位置編碼，最后將編得的碼值進行存儲或傳輸。解壓縮僅是編碼過程的逆變換。實際上，采樣得到的大部分數(shù)據(jù)都是不重要的，即K值很小，但由于奈奎斯特采樣定理的限制，采樣點數(shù)N可能會非常大，采樣后的壓縮是造成資源浪費的根本所在。圖1.1 傳統(tǒng)編解碼理論框圖CS 理論的信號編解碼框架和傳統(tǒng)的框架大不一樣，如圖1.2 所示。CS 理論對信號的采樣、壓縮編碼發(fā)生在同一個步

9、驟，利用信號的稀疏性，以遠低于Nyquist采樣率的速率對信號進行非自適應的測量編碼。測量值并非信號本身，而是從高維到低維的投影值，從數(shù)學角度看，每個測量值是傳統(tǒng)理論下的每個樣本信號的組合函數(shù)，即一個測量值已經(jīng)包含了所有樣本信號的少量信息。解碼過程不是編碼的簡單逆過程，而是在盲源分離中的求逆思想下，利用信號稀疏分解中已有的重構(gòu)方法在概率意義上實現(xiàn)信號的精確重構(gòu)或者一定誤差下的近似重構(gòu)，解碼所需測量值的數(shù)目遠小于傳統(tǒng)理論下的樣本數(shù)。壓縮感知的核心思想是壓縮和采樣合并進行，并且測量值遠小于傳統(tǒng)采樣方法的數(shù)據(jù)量，突破了香農(nóng)采樣定理的瓶頸，使高分辨率的信號采集成為可能。 壓縮感知理論主要包括信號的稀疏

10、表示、隨機測量和重構(gòu)算法等三個方面。稀疏表示是應用壓縮感知的先驗條件，隨機測量是壓縮感知的關(guān)鍵過程，重構(gòu)算法是獲取最終結(jié)果的必要手段。圖1.2 CS理論下數(shù)據(jù)的編解碼過程 壓縮感知關(guān)鍵要素包括稀疏表示、測量矩陣和重構(gòu)算法。 信號在某種表示方式下的稀疏性，是壓縮感知應用的理論基礎(chǔ)，經(jīng)典的稀疏化的方法有離散余弦變換（DCT）、傅里葉變換（FFT）、離散小波變換（DWT）等。最近幾年，對稀疏表示研究的另一個熱點是信號在冗余字典下的稀疏分解。 這是一種全新的信號表示理論：用超完備的冗余函數(shù)庫取代基函數(shù)，稱之為冗余字典，字典中的元素被稱為原子。目前信號在冗余字典下的稀疏表示的研究集中在兩個方面：一是如何

11、構(gòu)造一個適合某一類信號的冗余字典，二是如何設(shè)計快速有效的稀疏分解算法。目前常用的稀疏分解算法大致可分為匹配追蹤（Matching Pursuit）和基追蹤（Basis Pursuit）兩大類。壓縮感知理論中，通過變換得到信號的稀疏系數(shù)后，需要設(shè)計壓縮采樣系統(tǒng)的觀測部分，它圍繞觀測矩陣展開。觀測器的設(shè)計目的是如何采樣得到M個觀測值，并保證從中能重構(gòu)出長度為N的信號X或者稀疏基基下等價的稀疏系數(shù)向量。CandeS和Tao等證明:獨立同分布的高斯隨機測量矩陣可以成為普適的壓縮感知測量矩陣。2007年Candes等研究者建立了著名的約束等距性（RIP）理論，即要想使信號完全重構(gòu)，必須保證觀測矩陣不會把

12、兩個不同的 K項稀疏信號映射到同一個采樣集合中，這就要求從觀測矩陣中抽取的每M個列向量構(gòu)成的矩陣是非奇異的。Donoho給出壓縮感知概念的同時定性和定量的給出測量矩陣要滿足三個特征：(1)由測量矩陣的列向量組成的子矩陣的最小奇異值必須大于一定的常數(shù)；(2)測量矩陣的列向量體現(xiàn)某種類似噪聲的獨立隨機性；(3)滿足稀疏度的解是滿足1范數(shù)最小的向量。目前常用的測量矩陣包括：（1）隨機高斯矩陣。矩陣每個元素獨立地服從均值為0，方差為的高斯分布。（2）隨機貝努利矩陣。矩陣的每個元素獨立地服從對稱的貝努利分布，等概率為或-。 （3）部分正交矩陣。先生成N×N的正交矩陣U（如傅里葉矩陣），然后在矩

13、陣U中隨機地選取M行向量，對M×N矩陣的列向量進行單位化得到測量矩陣。（4）部分哈達瑪矩陣。生成大小為N×N的哈達瑪矩陣，然后在生成矩陣中隨機地選取M行向量，構(gòu)成一個M×N的矩陣。（5）托普利茲和循環(huán)矩陣。首先生成一個向量u，由向量u生成相應的輪換矩陣或托普利茲矩陣U，然后在矩陣U中隨機地選取其中的M行而構(gòu)造的矩陣。（6）稀疏隨機矩陣。首先生成一個零元素的矩陣，在矩陣的每一個列向量中，隨機地選取d個位置，然后在所選取的位置的值賦為1。 壓縮感知的重構(gòu)算法主要分為兩大類，一是貪婪算法，它是通過選擇合適的原子并經(jīng)過一系列的逐步遞增的方法實現(xiàn)信號矢量的逼近，此類算法主要

14、包括匹配跟蹤算法、正交匹配追蹤算法、補空間匹配追蹤算法等。二是凸優(yōu)化算法，它是把0范數(shù)放寬到1范數(shù)通過線性規(guī)劃求解的，此類算法主要包括梯度投影法、基追蹤法、最小角度回歸法等。凸優(yōu)化算法算法比貪婪算法所求的解更加精確，但是需要更高的計算復雜度。 此外，迭代閾值法也得到了廣泛的應用，此類算法也較易實現(xiàn)，計算量適中，在貪婪算法和凸優(yōu)化算法中都有應用。但是，迭代閾值法對于迭代初值和閾值的選取均較敏感，且不能保證求出的解是稀疏的。 就目前主流的兩種重建算法而言，基于1范數(shù)最小的重建算法計算量巨大，對于大規(guī)模信號無法應用；貪婪算法雖然重建速度快，但是在信號重建質(zhì)量上還有待提高。1.3 本文框架結(jié)構(gòu)本文通過

15、對壓縮感知理論進行系統(tǒng)認真的學習和研究，查閱了大量的國內(nèi)外相關(guān)的文獻和資料，主要完成了圍繞正交匹配追蹤算法的信號和圖像重構(gòu)處理。本文的主要結(jié)構(gòu)如下所示：第一章，緒論。本章首先介紹了壓縮感知理論研究的背景和意義，然后綜述了CS理論的理論框架，最后陳述了本文的內(nèi)容安排。第二章，國內(nèi)外研究現(xiàn)狀。本章介紹了壓縮感知理論的歷史、發(fā)展及將來的研究方向。然后介紹了其在光學成像方面的應用。第三章，壓縮感知（CS）基本理論。本章詳細闡述了壓縮感知理論的基本原理。首先講述了CS理論的數(shù)學原理，然后圍繞壓縮感知的三個關(guān)鍵技術(shù)，信號的稀疏表示、觀測矩陣的設(shè)計和重構(gòu)算法展開討論，介紹了該理論是如何實現(xiàn)的。最后介紹了其在

16、現(xiàn)實中的最新應用及一些不足和需要改進之處。第四章，壓縮感知實現(xiàn)及結(jié)果分析。本章首先簡單介紹了傳統(tǒng)圖像壓縮技術(shù)在變換編碼方面的重構(gòu)方法。然后完成了分別基于離散傅里葉變換（DFT）和離散余弦變換的一維信號和二維圖像的OMP算法重構(gòu)，并進行了性能參數(shù)方面的對比。第五章，總結(jié)和展望。本章總結(jié)了本設(shè)計所完成的工作，并對其中的缺陷做出了說明，指出了所采用算法的不足指出，對下一步的工作做了展望。 第2章 國內(nèi)外研究現(xiàn)狀壓縮感知理論是近幾年剛剛興起的理論，但卻展現(xiàn)了強大的生命力引起了廣泛的關(guān)注，下面我們將對該理論的歷史和發(fā)展歷程做出介紹。2.1 從稀疏重構(gòu)到壓縮感知早在壓縮感知理論正式提出以前，1970年代的

17、石油勘探地震數(shù)據(jù)處理中，人們已經(jīng)發(fā)現(xiàn)香農(nóng)-奈奎斯特采樣定理的限制是“可以突破的”。由于測量條件的限制，獲取的數(shù)據(jù)十分有限，根據(jù)傳統(tǒng)理論并不足以重構(gòu)地層結(jié)構(gòu)。幸運的是，地層內(nèi)部是均質(zhì)的，只是層與層之間又不連續(xù)，且這種不連續(xù)是“稀疏的”。當理由這種稀疏性先驗知識時，便可以較好的反演地質(zhì)結(jié)構(gòu)。從數(shù)學上看，地層結(jié)構(gòu)反演屬于典型的逆問題，逆問題往往是病態(tài)的，需要加入正規(guī)化約束以得到有用的結(jié)果。”稀疏性”是近二十年來逐步發(fā)展起來的一種正規(guī)化約束，含稀疏性約束的逆問題被稱為稀疏重構(gòu)問題，其本質(zhì)是從超完備字典中尋找盡可能少的原子（選出的原子只占所有原子中很少的一部分），通過它們的線性組合來逼近給定的向量y。即

18、 x，s.t (式2.1) 定義2.1：對于MN維矩陣，若其各列具有單位長度，則稱之為字典，矩陣的各列被稱為原子。 稀疏重構(gòu)問題本質(zhì)上是一種后端處理方法。其應用是在數(shù)據(jù)獲取之后，并沒有與前端的數(shù)據(jù)獲取系統(tǒng)相結(jié)合。采樣理論的研究自Shannon以后也經(jīng)歷著不斷的發(fā)展，其中基于“新息率”（rate of innovation）的采樣策略與壓縮感知理論密切相關(guān)。考慮在單位時間內(nèi)具有有限自由度的信號，稱該自由度為新息率。實際應用中有很多這樣的信號，如Poisson過程、非均勻采樣和分段多項式等。這些信號不是帶限的，根據(jù)Shannon定理，均勻矩形脈沖采樣條件下無法精確重構(gòu)。文獻11-14指出基于高于新

19、息率的非均勻采樣和適當構(gòu)造的核函數(shù)，這些信號仍可以精確重構(gòu)。Analog-to-information conversion(AIC)是根據(jù)壓縮感知理論設(shè)計的一種新概念采樣體制，其充分利用這樣一個事實：許多射頻信號雖然具有很大的帶寬，但是他們的“新息率”有限，因此可以根據(jù)其新息率，而非帶寬進行采樣。隨著稀疏重構(gòu)和新興采樣定理研究的不斷深化，很多學者發(fā)現(xiàn)，當測量數(shù)據(jù)不完全時，有時甚至只有很小一部分測量數(shù)據(jù)，利用該方法仍可以很好的重構(gòu)原圖像。2006年Candes, Romberg及Tao等人在研究高度欠定的核磁共振成像問題時，得出一個重要的結(jié)論：當測量矩陣為Fourier矩陣時，O(K*log(

20、N)的數(shù)據(jù)采集量能將N維空間的K稀疏信號精確重建。2007年，Candes和 Romberg將Fourier測量方式推廣到任意正交測量并得到類似的結(jié)論。這兩項工作表述了一個問題：可通過低維頻域(或時域)信號實現(xiàn)高維稀疏時域(或頻域)信號的精確重建。這個令人驚喜的發(fā)現(xiàn)促使壓縮感知理論的誕生：既然利用部分測量數(shù)據(jù)就可以精確重構(gòu)原圖像，那么為什么不在測量時就僅獲得所需的數(shù)據(jù)，而不是耗費大量資源來獲取全部數(shù)據(jù)。其后Candes, Romberg及Tao等人，初步建立了壓縮感知的理論基礎(chǔ)。壓縮成像的組成可以分為兩個部分：數(shù)據(jù)的獲取過程和圖像的重構(gòu)過程。其中，后者和稀疏重構(gòu)的研究一脈相傳，但需特別考慮二維

21、圖像所涉及的大規(guī)模數(shù)據(jù)下的保精確度快速計算問題；前者的研究理論上需研究使得“稀疏重構(gòu)”能夠恢復原信號的測量矩陣的行質(zhì)，即可重構(gòu)條件，應用中還需考慮滿足重構(gòu)條件的測量矩陣的物理實現(xiàn)問題，即利用適當?shù)挠布O(shè)備完成壓縮采樣。2.2 稀疏重構(gòu)算法和重構(gòu)條件研究首先給出l范數(shù)的定義，需要指出的是，當參數(shù)p在某些范圍內(nèi)取值時，(式2.2)的定義可能不滿足三角不等式，因此不是真正意義上的范數(shù)，但不影響討論，仍稱其為范數(shù)。定義2.3： 信號的l范數(shù)為： （式2.2）其中當p=0時，（式2.2）等價于計算x中的非零元素的個數(shù)，當p=2時，（式2.2）為空間中的歐氏范數(shù)，當時，根據(jù)定義2.1，圖像的稀疏性最本質(zhì)的

22、度量為l范數(shù)，則（式2.1）的數(shù)學描述為 s.t. （式2.3）若測量噪聲中含有噪聲，則重構(gòu)模型為 s.t. （式2.4）其中參數(shù)反映了測量噪聲的水平。（式2.3）和（式2.4）等含l范數(shù)的稀疏重構(gòu)問題已被證明是NP難解的，需要尋找多項式時間內(nèi)可解得近似方法，現(xiàn)有的主要方法可以分為：1)貪婪算法 基本思想是迭代地從字典中選擇原子，并計算相應的系數(shù)，使得這些原子的線性組合與測量數(shù)據(jù)之間的差別逐漸縮小。以最基本的正交匹配追蹤（Orthogonal Matching Pursuit,OMP）算法為例，設(shè)當前迭代結(jié)果為，已選取原子的索引為，它是的一個子集，令；設(shè)殘差，計算與字典中的原子的相關(guān)性，取其中

23、絕對值最大的元素，即為索引j；令更新后的索引集為，則更新后的信號為，其中為按索引的各列后得到的子矩陣。由于是線性無關(guān)的，因此可以通過最小二乘計算得到。其它的貪婪算法還有StOMP算法、Regularized OMP(ROMP)算法以及Compressive Sampling Matching Pursuit(CoSaMP)等。在計算復雜度方面，從形式上看，若字典是顯示的，則貪婪算法涉及矩陣向量之間的乘法運算，其運算量為O(MN),若具有隱式的快速變換，則計算量可顯著降低。此外，求解的最小二乘過程可以利用的QR分解，其運算量為O(MK)。注：稱是顯式的，若和的運算可以通過矩陣和向量的乘法運算完成

24、；相對應的，稱是隱式的，是指和的運算可以通過函數(shù)運算完成。2）凸優(yōu)化 基本思想是將（式2.3）和（式2.4）“松弛”為凸優(yōu)化問題，利用凸函數(shù)性質(zhì)，實現(xiàn)多項式時間內(nèi)的稀疏重構(gòu)。由于l范數(shù)是最接近l范數(shù)的凸函數(shù)，因此常將l范數(shù)松弛為l范數(shù)，文獻27-31討論了l范數(shù)與l范數(shù)之間的等價特性條件。內(nèi)點法（interior-point）為最早的l范數(shù)凸優(yōu)化求解方法，可用的軟件包有SeDuMi和MOSEK等。但總的來說，內(nèi)點法的重構(gòu)結(jié)果受參數(shù)選取影響較大，且計算復雜度高，不適用于二維像等大數(shù)據(jù)量應用問題。梯度下降類算法是一階精度的l范數(shù)凸優(yōu)化求解方法，該類算法在每步的迭代中計算殘差的梯度： （式2.5）

25、（式2.6）其中，均為控制參數(shù)。其它類似的方法包括TwIST和GPSR等。當測量矩陣滿足可重構(gòu)條件時，這些方法能迅速識別信號中稀疏分量的位置，并重構(gòu)原信號。3)其它算法 一些非凸優(yōu)化算法，如將l范數(shù)松弛為l，0<p<1范數(shù)；或者通過先驗分布引入稀疏性，再用貝葉斯方法實現(xiàn)稀疏重構(gòu)；此外，還有一些啟發(fā)式算法（heuristic algorithms）,用借鑒圖模型和編碼理論中的belief-propagation和message-passing技術(shù)。重構(gòu)條件的研究就是討論稀疏重構(gòu)解得唯一性條件。設(shè)和是兩個稀疏解，則有：，即矩陣將稀疏度為2K的信號映射為零，這意味著當且僅當?shù)拿總€2K列子

26、矩陣均為單射時，稀疏解是唯一的。在實際運用中，不僅要求稀疏解是唯一的，還要求其實穩(wěn)定的，假設(shè)測量數(shù)據(jù)有擾動，其導致解的變化滿足：，穩(wěn)定性是指微小的不會導致較大。約束等距性（Restricted Isometry Property，RIP）是壓縮感知理論中用以描述重構(gòu)條件的指標，但對于給定的測量矩陣，驗證其是否滿足RIP是NP難解問題。此外，稀疏重構(gòu)理論中常用的字典相關(guān)性，也可以用于重構(gòu)條件的描述，它的優(yōu)點是計算簡單，缺點是得到的條件不是緊致的，如根據(jù)相關(guān)性理論，M個測量數(shù)據(jù)（即測量矩陣的行數(shù)為M）至多可恢復稀疏度的信號，而根據(jù)RIP當測量矩陣為特定的隨機矩陣時，可重構(gòu)信號的稀疏度可以放寬為。2

27、.3 壓縮感知在光學成像中的應用壓縮感知應用于光學成像的首個實際系統(tǒng)是Rice大學Baraniuk等建立的“單相素相機”，其原理圖與實際系統(tǒng)如圖圖2.3.1 單相素相機與實際系統(tǒng)圖 左圖中，入射光線經(jīng)過第一個透鏡之后進入成像系統(tǒng)，照射在放置于像平面的數(shù)字微鏡設(shè)備（Digital Micro-mirror Device，DMD）陣列上。DMD陣列由數(shù)百萬個尺寸為um量級的微小反射鏡組成，每個反射鏡的角度可以獨立控制（圖中用黑白兩色表示兩個不同的反射角度），從而可以控制其上的反射光線的方向。DMD陣列的反射光線經(jīng)過第二個透鏡，其中僅一個方向的光線進入不具備空間分辨力的單相素光子探測器，經(jīng)過AD轉(zhuǎn)換

28、后以數(shù)字信號的形式被記錄下來。DMD上的每個微小反射鏡的角度是可以控制的，頻率可以到達Hz，所有小反射鏡角度控制的一次實現(xiàn)稱為一個“測量模式”。每個“測量模式”下，探測采集一個數(shù)字信號，為了獲得足夠多的數(shù)據(jù)，需要進行多次測量。“單相素相機”實際系統(tǒng)如右圖所示，該系統(tǒng)目前已可獲取原理驗證性圖像。值得一提的是rice大學的單像素相機硬件成本昂貴，重建算法效率低下，還有很大的改進空間。其它基于壓縮感知原理建立的成像系統(tǒng)有：Compressive Structured Light for Recovering Inhomogeneous Participating Media, Compressive

29、 Dual Photography, Random Lens Imager和Tranform Imager等。特別地，美國國防高級研究計劃局（DARPA）資助的Multiple Optical Non-Redundant Aperture Generalized Sensors(MONTAGE)致力于通過有機結(jié)合光學系統(tǒng)、檢測和后處理技術(shù)的最新進展，開發(fā)革命性的成像系統(tǒng)。Compressive Optical MONTAGE Photography Initiative(COMP-I)是MONTAGE計劃下的一個子項目，其目標是在不損失成像系統(tǒng)分辨率的條件下，減小焦距，制造“超薄”成像系統(tǒng)。目

30、前，已實現(xiàn)了一個5mm的環(huán)形孔徑透鏡，其分辨率與40mm焦距的傳統(tǒng)成像系統(tǒng)相當。“超薄”成像的關(guān)鍵技術(shù)之一是所謂的焦平面編碼，即在焦平面處設(shè)置二值幅度調(diào)制掩膜，固定于探測器上，以完成對焦平面光場的某種變換，而探測器測量的是這種變換下的“系數(shù)”（本質(zhì)上，每個測量是光場的一種線性組合）。最后在計算機上將測量數(shù)據(jù)逆變換得到原圖像。在光學成像領(lǐng)域，將與之相類似的技術(shù)稱之為“計算成像”。傳統(tǒng)的成像系統(tǒng)利用透鏡或反射鏡系統(tǒng)形成圖像，并利用探測器進行采樣。數(shù)據(jù)處理在傳統(tǒng)概念中被認為是后處理過程，并不納入成像系統(tǒng)設(shè)計的考慮之中。隨著電子學的發(fā)展，在探測器和光場操控、編碼方面取得了重大的進展；另一方面，光學系統(tǒng)

31、的設(shè)計卻受限于信息光學中物理定理的限制，為了提高分辨率，體積重量不斷增加。因此，現(xiàn)代成像系統(tǒng)的設(shè)計不能僅考慮前端的光學系統(tǒng)，還需考慮探測器和圖像重構(gòu)的因素?！坝嬎愠上瘛钡母拍罹褪窃谶@樣的背景下提出的，它同時需要光學系統(tǒng)、采樣以及圖像重構(gòu)的技術(shù)，于壓縮成像有著異曲同工之處。目前，已有若干類似的“計算成像”原理驗證系統(tǒng)。Duke大學Duke Image and Spectroscopy Program(DISP)小組在DARPA MONTAGE計劃的支持下，在多路光學技術(shù)中開展了很多研究。例如，驗證了紅外相機可以采用同時利用多路小孔徑光學透鏡收集若干低分辨率圖像，但不是當長焦距大孔徑透鏡，是想高分

32、辨率成像。如上所述，CS測量矩陣的實現(xiàn)硬件是將CS推向?qū)嵱玫谋貍錀l件。在RIP理論指導下，萊斯大學R. Baraniuk教授等研制的單像素相機和A/I轉(zhuǎn)換器。隨后，有多種CS硬件相繼報道，例如，麻省理工學院教授等人研制的MRI RF脈沖設(shè)備，麻省理工學院W. T. Freeman教授等人研制的編碼孔徑相機，耶魯大學研制的超譜成像儀，伊利諾伊州立大學O. Milenkovic等人研制的DNA微陣列傳感器，我們課題組研制的CS濾波器和混沌腔，等等。這些CS硬件實現(xiàn)將CS向?qū)嵱没七M了一大步，然而僅能處理有限維信號，無法處理無限維信號。另外，由于缺乏有效的CS矩陣判別理論，除rice大學的單像素相機

33、(硬件成本昂貴，重建算法效率低下)外，其它硬件均缺乏嚴格的理論分析。第3章 壓縮感知（CS）基本理論信號的稀疏重構(gòu)主要包括三個方面內(nèi)容：1）信號的稀疏表示方法，它是重構(gòu)的前提；2）稀疏約束項的構(gòu)造，它在一定程度上決定了重構(gòu)所需的壓縮采樣數(shù)量和重構(gòu)過程的復雜度；3）含稀疏約束項的最優(yōu)化求解方法，它決定了重構(gòu)的計算復雜度、精度和穩(wěn)健性。信號的壓縮采樣理論主要討論為使稀疏重構(gòu)能精確、穩(wěn)定恢復原信號，測量矩陣需滿足的條件。3.1 壓縮感知背景 考慮一個實值的有限長一維離散時間信號X， 可以看作為一個空間N ×1 維的列向量， 元素為X n ， n = 1 ，2 ， N。空間的任何信號都可以用

34、N ×1維的基向量的線性組合表示。 為簡化問題，假定這些基是規(guī)范正交的。把向量作為列向量形成N ×N 的基矩陣: = ， 于是任意信號X 都可以表示為： or （式3.1）其中是投影系數(shù)構(gòu)成的N ×1 的列向量。反變換后得到： （式3.2） 顯然， X 和是同一個信號的等價表示， X是信號在時域的表示，則是信號在 域的表示。 如果的非零個數(shù)比N 小很多，則表明該信號是可壓縮的。一般而言，可壓縮信號是指可以用K 個大系數(shù)很好地逼近的信號， 即它在某個正交基下的展開的系數(shù)按一定量級呈現(xiàn)指數(shù)衰減， 具有非常少的大系數(shù)和許多小系數(shù)。這種通過變換實現(xiàn)壓縮的方法稱為變換編碼。

35、變換編碼在數(shù)據(jù)采樣系統(tǒng)中，比如數(shù)碼相機，發(fā)揮了重要作用。 在這些系統(tǒng)中， 采樣速率高但信號是可壓縮的，采樣得到N 點采樣信號X；通過變換后計算出完整的變換系數(shù)集合i ；確定K個大系數(shù)的位置，然后扔掉N-K個小系數(shù)；對K個大系數(shù)的值和位置進行編碼，從而達到壓縮的目的。圖3.1 傳統(tǒng)方法壓縮過程但這種傳統(tǒng)的信號編解碼方法存在顯著的一些缺點：（1）考慮到奈奎斯特采樣定理，為了能獲得很好的信號分辨率，采樣間隔會取的很小，這樣便造成了原始信號長度會很長，因此變換過程也會消耗較長的時間。（2）K個需要保留的重要分量的位置，是隨著信號的不同而不同的。因此，這種策略是“自適應”的，而且需要分配多余的空間來存儲

36、這些位置。（3）一旦在傳輸?shù)倪^程中K 個分量的某幾個丟失了，后果便可想而知。例如按照以上方法制作一個音頻設(shè)備，便會存在以下的一些缺點：帶來電力的大量消耗和用戶的不滿、帶來存儲空間的增加、帶來較差的抗干擾能力等。針對上述所遇到的問題，壓縮感知理論指出：對于信號，如果它在某個正交變換基上是可進行稀疏變換的，則選取一個與不相關(guān)的M × N 維觀測矩陣來觀測得到原始信號的M個降維觀測向量Y，即Y = ，其中，是原始信號在正交變換基 域的稀疏表示形式。擁有了這M 個測量值Y 和觀測矩陣，最后通過求解一個優(yōu)化問題便可以得到原始信號的精確重構(gòu)或近似逼近。重構(gòu)算法的問題是基于如下嚴格的數(shù)學最優(yōu)化問題

37、：目標函數(shù)：，且滿足等式約束： （式3.3）綜合以上所述，得到了基于壓縮感知理論框架下的信號編解碼流程圖，如圖 3.2所示。圖3.2 壓縮感知理論框架下的信號編解碼流程3.2 壓縮感知理論3.2.1壓縮感知的前提條件稀疏性和不相干性CS隱含的兩個基本前提：稀疏性和不相關(guān)性。前者屬于信號的性質(zhì)，后者和感知（觀測）形式有關(guān)。稀疏性：稀疏性表達了這樣一個思想，一個連續(xù)時間信號的“信息速率”可能比由帶寬所決定的香農(nóng)采樣率要低很多，或者，一個離散時間信號所依賴的自由度數(shù)目遠遠低于它的長度。更準確地說，CS利用了這樣一個事實，即許多自然信號在某個合適的基下具有簡潔的表達。不相關(guān)性：不相關(guān)性說明用于采樣信號

38、的波在基下有很稠密的表達。不相關(guān)性表達了這樣的思想，正如時間域的Dirac或者沖擊信號可以在頻域展開那樣，在基下具有稀疏表示的信號一定可以在獲得它們的某個域中展開。1 稀疏性眾所周知，任意長度為N 的離散信號X 都可以表示為一系列基函數(shù)的疊加，即可以在任何正交基下用下式表示：（式3.3）其中由一組基向量構(gòu)成的正交基，例如，sinusoids，尖峰spikes、B-splines，wavelets。為展開系數(shù)。展開系數(shù)大，說明信號和基足夠相似。如果信號在基下的展開系數(shù)在很小的集合上有值，我們就說該信號在域是稀疏的，如果有值序列集中在一個小范圍內(nèi)，那么我們就說該信號是可以壓縮的。本章我們將集中研究

39、具有稀疏表示的信號，其中X是K個基向量的線性組合，K<<N。也就是說，中僅有K個非零，另外N -K個都是零。許多自然信號在一些基下有簡潔的表達。圖3.3（a）是一幅具有N（N =512×512）個像素點的coins圖像向量，我們在9/7小波基下展開該向量，如（式3.4），其中是為列向量構(gòu)成的的矩陣，是正交基。圖3.3（b）是coins圖像的9/7小波系數(shù)在一維下的表示。圖2.3（c）展示了這樣一個事實：將圖像在9/7小波變換域丟掉93.75%的小系數(shù)后得到的逼近圖像盡管PSNR只有29.09dB，但肉眼很難察覺到失真。由此可見，盡管原圖中幾乎所有的像素都是非零值，它在9/

40、7小波域中卻是稀疏的：大部分小波系數(shù)都很小，少數(shù)的大系數(shù)（1/16）就可以捕獲信號的大部分信息。本例中僅僅保留展開（式3.4）中的個大系數(shù)得到，其中表示系數(shù)向量的除K個大系數(shù)外其余置0的向量。該向量從嚴格意義上說是稀疏的，因為K<<N ，即除了極少數(shù)項外其余均為0。現(xiàn)在稀疏的含義很清楚了：如果x在某個變換域下是稀疏或者可壓縮的，就意味著將x的系數(shù)按幅值大小排列衰減很快，那么x可以由K個大系數(shù)很好地逼近。圖3.3（c）所示告訴我們，可以丟棄除了少數(shù)幾個系數(shù)外的所有小系數(shù)而不會帶來視覺上的損失。我們稱至多有K個非零項的向量為K -稀疏，且有。稀疏性原理是大部分現(xiàn)代有損壓縮編碼算法和許多

41、其它應用的基礎(chǔ)。不過在傳統(tǒng)編碼中，這K個大系數(shù)的位置必須事先確定。更一般地，稀疏性是一個基本的建模工具，可以進行信號的精確統(tǒng)計估計和分類、有效的數(shù)據(jù)壓縮等等。而近幾年來Candès等人提出的壓縮感知理論使得稀疏性有了更加令人驚奇的深遠含義，即信號稀疏性對采樣本身有重要意義，稀疏性決定了我們可以擺脫奈奎斯特采樣頻率的約束，并可以做到高效地非自適應地采樣信號。（b）coins圖像的9/7小波系數(shù)在一維下的表示(a)512x512的coins原始圖像 （c）1/16系數(shù)重構(gòu)圖像（PSNR=29.09dB）圖3.3稀疏重構(gòu)圖像案例2 不相關(guān)性 Candès， Romberg等人已經(jīng)

42、證明一個降維的投影集合包含了重構(gòu)稀疏信號的足夠信息。這就是壓縮感知（CS）理論的核心內(nèi)容。在CS中，假定信號在某個變換域的系數(shù)是K項稀疏的，我們不直接對K個重要的系數(shù)直接編碼，而是將信號的系數(shù)向量投影到另一個基函數(shù)集合上，觀測得到M (<<N)個投影然后再編碼。用矩陣表示，則有，。其中Y 是一個的列向量，觀測矩陣是一個以每個基向量作為行向量的矩陣。由于M<<N，從觀測向量y中重構(gòu)信號x是一個欠定問題，然而信號稀疏的附加假設(shè)使得恢復成為可能也是可行的。CS理論告訴我們，當滿足一定條件時，也即是基不能稀疏表示（該條件被稱為兩組基不相關(guān)）并且觀測值個數(shù)M足夠大，那么就可以從一

43、個相似規(guī)模的集合中恢復大系數(shù)集合，繼而也就可以得到信號X。許多對基都滿足不相關(guān)性質(zhì)，例如，三角尖峰和傅里葉基中的正弦波不相關(guān)，傅里葉基和小波基不相關(guān)。重要的是，任意一個固定的基和一個隨機產(chǎn)生的基也以高概率滿足這種不相關(guān)。因此在CS理論中隨機矩陣被廣泛應用于CS觀測中。在框架下或者基下可以找到稀疏表示的信號都可以以同樣的方式從不相關(guān)觀察中恢復。文獻3給出了相關(guān)性度量的具體定義，如下。定義3.2：觀測系統(tǒng)和表示系統(tǒng)之間的相關(guān)性度量用表示，則有如下式子成立： （式3.4）簡單來講，相關(guān)性度量的是兩個矩陣和的元素之間的最大相關(guān)性。如果和包含了相關(guān)的元素，則相關(guān)性很大；否則，就很小。相關(guān)系數(shù)取值范圍為。

44、壓縮采樣研究的是具有低相關(guān)性的兩個系統(tǒng)。下面給出一些例子。（1）是尖峰基，為傅立葉基，則有。進一步講，尖峰信號和正弦信號不僅在一維而且在任何維，例如2D，3D空間都具有最大的不相關(guān)性。（2）為小波基，是noiselet。這里，noiselet和Haar小波基間的相關(guān)系數(shù)是，noiselet和Daubechies db4及db8小波基間的相關(guān)性分別是2.2和2.9。這也可以擴展到高維情況。noiselets也和尖峰信號及傅立葉基高度不相關(guān)。人們對noiselets感興趣基于以下兩個事實：1）它們和為圖像數(shù)據(jù)和其它類型的數(shù)據(jù)提供稀疏表示的系統(tǒng)不相關(guān)；2）它們具有快速算法。noiselet變換的時間

45、復雜度為O(N)，而且類似于傅立葉變換，noiselet矩陣不需要存儲。這一點對于高效的數(shù)字計算是至關(guān)重要的。如果沒有高效的計算，CS的實用性就會大打折扣。（3）為隨機矩陣，則可以是任何固定的基。此時它們之間具有極大不相關(guān)。例如，可以通過在單位球面上獨立均勻地采樣并做規(guī)范正交化得到，此時，和間的相關(guān)性以很高的概率為。各項服從獨立同分布的隨機波形，例如高斯分布或者，也表現(xiàn)出和任何固定基具有很小的相關(guān)性。研究者們通過大量的實驗分析，得出如下結(jié)論：精確重構(gòu)所需要的觀測值個數(shù)依賴于稀疏變換基和觀測基之間的不相關(guān)性。不相關(guān)性越強，所需的個數(shù)越少；反之，相關(guān)性越強，例如，則需要采樣所有的系數(shù)才能保證精確重

46、構(gòu)。3.2.2 三個關(guān)鍵技術(shù)從以上壓縮感知理論的介紹中我們可以看出，壓縮感知理論主要包括以下三個方面的內(nèi)容：（1）信號稀疏表示；（2）信號的編碼測量即觀測矩陣的設(shè)計；（3）信號重構(gòu)算法的設(shè)計。信號的稀疏表示是指當將信號投影到某個正交變換基時，一般情況下絕大多數(shù)的變換系數(shù)的絕對值都是很小的，得到的變換向量也是稀疏的或者是近似稀疏的，這是原始信號的一種簡潔的表達方式，也是壓縮傳感理論的先驗條件。信號必須得在某種變換下才可以進行稀疏表示。通常我們可以選取的變換基有離散傅里葉變換基（DFT）、離散余弦變換基（DCT）、離散小波變換基（DWT）、Curvelet 變換基、Gabor 變換基還有冗余字典等

47、。在信號的編碼測量即觀測矩陣的設(shè)計過程中，要選擇穩(wěn)定的觀測矩陣，觀測矩陣的選取必須滿足受限等距特性(Restricted Isometry Property，RIP)準則，才能保證信號的投影能夠保持原始信號的結(jié)構(gòu)特征。通過原始信號與觀測矩陣相乘我們可以獲得原始信號的線性投影值。最后設(shè)計合適的重構(gòu)算法從所得到的觀測值和原來的觀測矩陣來重構(gòu)原始始號。所以對壓縮感知理論的研究也主要是基于這三個方面的內(nèi)容：（1）信號的稀疏表示。即對于信號 ，如何找到一個合適的正交基或者緊框架，以使得原始信號在上的表示是稀疏的。（2）觀測矩陣的設(shè)計。即如何設(shè)計一個平穩(wěn)且滿足受限等距特性條件或者與變換基 滿足不相關(guān)約束條

48、件的M × N 維觀測矩陣，以保證信號稀疏表示后的向量能從原來的N 維降到M 維時所包含的重要信息沒有受到破壞，從而保證原始信號的準確重構(gòu)。這個過程也就是壓縮感知理論中信號的低速采樣過程。（3）重構(gòu)算法的設(shè)計。即如何設(shè)計快速有效且穩(wěn)定的重構(gòu)算法，從所得到的低維觀測向量中準確地恢復原始信號。下面我們對壓縮感知理論的這三個關(guān)鍵技術(shù)做一個詳細的總結(jié)和分析，以為后文對壓縮感知理論在圖像重構(gòu)方面的研究打下基礎(chǔ)。3.2.3信號的稀疏表示從傅立葉變換到小波變換再到后來興起的多尺度幾何分析（Ridgelet，Curvelet，Bandelet，Contourlet），科學家們的研究目的均是為了研究如

49、何在不同的函數(shù)空間為信號提供一種更加簡潔、直接的分析方式，所有這些變換都旨在發(fā)掘信號的特征并稀疏表示它，進一步研究用某空間的一組基函數(shù)表示信號的稀疏程度或分解系數(shù)的能量集中程度。文獻23給出稀疏的定義：信號X在正交基下的變換系數(shù)向量為，假如對于0<p<2和R> 0，這些系數(shù)滿足： （式3.5）則說明系數(shù)向量在某種意義下是稀疏的。文獻34給出另一種定義：如果變換系數(shù)的支撐域的勢小于等于K，則可以說信號X 是K -項稀疏。如何找到信號最佳的稀疏域？這是壓縮感知理論應用的基礎(chǔ)和前提，只有選擇合適的基表示信號才能保證信號的稀疏度，從而保證信號的恢復精度。在研究信號的稀疏表示時，可以通

50、過變換系數(shù)衰減速度來衡量變換基的稀疏表示能力。Candès 和Tao通過研究發(fā)現(xiàn)，滿足冪定律衰減的信號，可利用壓縮感知理論進行恢復，并且重構(gòu)誤差滿足： （式3.6）其中r=1/p-1/2，0<p<1。 文獻30指出光滑信號的Fourier系數(shù)、小波系數(shù)、有界變差函數(shù)的全變差范數(shù)、振蕩信號的Gabor系數(shù)及具有不連續(xù)邊緣的圖像信號的Curvelet系數(shù)等都具有足夠的稀疏性，可以通過壓縮感知理論恢復信號。如何找到或構(gòu)造適合一類信號的正交基，以求得信號的最稀疏表示，這是一個有待進一步研究的問題。Gabriel Peyré把變換基是正交基的條件擴展到了由多個正交基構(gòu)成的

51、正交基字典。即在某個正交基字典里，自適應地尋找可以逼近某一種信號特征的最優(yōu)正交基，根據(jù)不同的信號尋找最適合信號特性的一組正交基，對信號進行變換以得到最稀疏的信號表示。最近幾年，對稀疏表示研究的另一個熱點是信號在過完備字典下的稀疏分解。字典的選擇應盡可能好地符合被逼近信號的結(jié)構(gòu)，其構(gòu)成可以沒有任何限制。從從過完備字典中找到具有最佳線性組合的K項原子來表示一個信號，稱作信號的稀疏逼近或高度非線性逼近。過完備庫下的信號稀疏表示方法最早由Mallat和Zhang于1993年首次提出， 并引入了MP算法。文獻以淺顯易懂的表達說明了過完備字典對信號表示的必要性，同時還指出字典的構(gòu)成應盡量符合信號本身所固有

52、的特性。目前信號在過完備字典下的稀疏表示的研究集中在兩個方面：（1）如何構(gòu)造一個適合某一類信號的過完備字典；（2）如何設(shè)計快速有效的稀疏分解算法。這兩個問題也一直是該領(lǐng)域研究的熱點，學者們對此已做了一些探索，其中，以非相干字典為基礎(chǔ)的一系列理論證明得到了進一步改進。從非線性逼近角度來講，信號的稀疏逼近包含兩個層面：一是根據(jù)目標函數(shù)從一個給定的基庫中挑選好的或最好的基；二是從這個好的基中挑選最好的K項組合。從過完備字典的構(gòu)成角度來講，文獻38中提出使用局部Cosine基來刻畫聲音信號的局部頻域特性；利用bandlet基來刻畫圖像中的幾何邊緣。還可以把其它的具有不同形狀的基函數(shù)歸入字典，如適合刻畫

53、紋理的Gabor基、適合刻畫輪廓的Curvelet基等等。從稀疏分解算法角度來講，在音視頻信號處理方面，基于貪婪迭代思想的MP算法表現(xiàn)出極大的優(yōu)越性，但不是全局最優(yōu)解。Donoho等人另辟蹊徑，提出了BP算法。BP算法具有全局最優(yōu)的優(yōu)點，但計算復雜度極高，例如對于長度為8192的信號，采用小波字典分解，等價于求解一個長度為8192*212992的線性規(guī)劃。MP算法雖然收斂速度較BP快，但不具備全局最優(yōu)性，且計算復雜度仍然很大。之后又出現(xiàn)了一系列同樣基于貪婪迭代思想的改進算法，如正交匹配追蹤算法（OMP），樹形匹配追蹤（TMP），分段匹配追蹤（StOMP）算法等。3.2.4 觀測矩陣設(shè)計觀測部分

54、的設(shè)計其實就是設(shè)計高效的觀測矩陣，換句話說，就是要設(shè)計一個能捕捉稀疏信號中有用信息的高效的觀測（即采樣）協(xié)議，從而將該稀疏信號壓縮成少量的數(shù)據(jù)。這些協(xié)議是非自適應的，僅僅需要用少量的固定波形和原信號聯(lián)系起來，這些固定波形和為信號提供簡潔表示的基不相關(guān)。此外，觀測過程獨立于信號本身。進一步講，使用優(yōu)化方法可以收集到的少量的觀測值中重構(gòu)信號。壓縮感知理論中，通過變換得到信號的稀疏系數(shù)向量后，需要設(shè)計觀測部分，它圍繞觀測矩陣展開。觀測器的設(shè)計目的是如何采樣得到M個觀測值，并保證從中能重構(gòu)出長度為N的信號X或者基下等價的稀疏系數(shù)向量。顯然，如果觀測過程破壞了X中的信息，重構(gòu)是不可能的。觀測過程實際就是

55、利用觀測矩陣的M個行向量對稀疏系數(shù)向量進行投影，即計算和各個觀測向量之間的內(nèi)積，得到M個觀測值，記觀測向量，即 （式3.7）（b）（a） 圖3.4 觀測矩陣的圖形表示圖3.4（a）是（式3.7）的形象描述。這里，采樣過程是非自適應的，也就是說，無須根據(jù)信號X 而變化，觀測的不再是信號的點采樣而是信號的更一般的線性泛函。圖3.4（a）隨機高斯矩陣作為觀測矩陣，稀疏域選擇DCT變換域，對信號X進行DCT變換后再進行觀測。（b）是（a）圖的另一種表達，變換后的系數(shù)向量是稀疏的，K=3，觀測得到的Y是非零系數(shù)對應的四個列向量的線性組合。對于給定的Y從（式3.7）中求出是一個線性規(guī)劃問題，但由于M<

56、;< N，即方程的個數(shù)少于未知數(shù)的個數(shù)，這一欠定問題一般來講無確定解。然而，如果具有K -項稀疏性（K<<M），則該問題有望求出確定解。此時，只要設(shè)法確定出中的K個非零系數(shù)的合適位置，由于觀測向量Y是這些非零系數(shù)對應的K個列向量的線性組合，從而可以形成一個的線性方程組來求解這些非零項的具體值。對此，有限等距性質(zhì)（restricted isometry property， RIP）給出了存在確定解的充要條件。這個充要條件和Candès、Tao等人提出的稀疏信號在觀測矩陣作用下必須保持的幾何性質(zhì)相一致。即，要想使信號完全重構(gòu)，必須保證觀測矩陣不會把兩個不同的K-項稀疏信

57、號映射到同一個采樣集合中，這就要求從觀測矩陣中抽取的每M個列向量構(gòu)成的矩陣是非奇異的。從中可以看出，問題的關(guān)鍵是如何確定非零系數(shù)的位置來構(gòu)造出一個可解的線性方程組。然而，判斷給定的是否具有RIP性質(zhì)是一個組合復雜度問題。為了降低問題的復雜度，能否找到一種易于實現(xiàn)RIP條件的替代方法成為構(gòu)造觀測矩陣F 的關(guān)鍵。文獻24指出如果保證觀測矩陣和稀疏基不相干，則在很大概率上滿足RIP性質(zhì)。不相干是指向量不能用稀疏表示。不相干性越強，互相表示時所需的系數(shù)越多；反之，相關(guān)性則越強。通過選擇高斯隨機矩陣作為即可高概率保證不相干性和RIP性質(zhì)。例如，可以生成多個零均值、方差為1/ N 的隨機高斯函數(shù)，將它們作為觀測矩陣的元素，使得以很高的概率具有RIP性質(zhì)。隨機高斯矩陣具有一個有用的性質(zhì)：對于一個的隨機高斯矩陣，可以證明當時在很大概率