壓縮采樣介紹

1、壓縮采樣介紹一個與傳統(tǒng)數(shù)據(jù)采集不同的傳感、采樣范例Emmanuel J. Candès and Michael B. WakinIEEE信號處理雜志 2008年3月對信號和圖像采樣的傳統(tǒng)方法遵循著名的香農(nóng)定理：采樣速率必須至少是當(dāng)前信號最大頻率的兩倍（也稱奈奎斯特速率）。事實上，這個定理幾乎是所有信號采集方式的基礎(chǔ)，被大規(guī)模應(yīng)用在消費性音頻視頻電子設(shè)備、醫(yī)學(xué)成像設(shè)備、收音機等等。（對于某些信號，例如并非是原始的天然影像，采樣率就不是由香農(nóng)定理所規(guī)定，而是取決于需要的空間或時間分辨率。然而，這些系統(tǒng)經(jīng)常在采樣前使用反鋸齒低通濾波器保持信號，使得香農(nóng)定理扮演一個幕后的角色。）例如在數(shù)據(jù)轉(zhuǎn)

2、換領(lǐng)域，標(biāo)準(zhǔn)模數(shù)轉(zhuǎn)換器（ADC）技術(shù)使用量化香農(nóng)定理：信號一律以大于或等于奈奎斯特速率來采樣。這篇論文研究了壓縮采樣的理論，該理論亦被稱為壓縮傳感或CS，是一項新穎的與傳統(tǒng)數(shù)據(jù)采集不同的傳感、采樣技術(shù)。CS理論聲稱可以比傳統(tǒng)方法使用更少的采樣信號和測量來恢復(fù)特定信號和圖形。為了實現(xiàn)這一點，CS依靠兩個準(zhǔn)則：稀疏性，不連貫性。u 稀疏性，表示連續(xù)時間信號的信息率可能比由帶寬決定的還要小，或者離散時間信號自由度遠小于其有限的長度。更準(zhǔn)確的說，CS方法發(fā)現(xiàn)許多自然信號是十分稀疏并可壓縮的，當(dāng)用適當(dāng)?shù)幕A(chǔ)表述時，他們就能有簡明的表達。u 傳感形式不連貫延續(xù)了時間和頻率的二元性，并表明目標(biāo)在有一個稀少的

3、特征并一定會在他們已得的范圍內(nèi)擴展，正如時域里面的狄拉克或沖擊信號在頻域也可展開表示。另外，不連貫表明它與信號特征不同，采樣、傳感的波形在有一個非常密集的表示。最重要的是我們可以設(shè)計有效的傳感、采樣規(guī)則，來獲取有用的信息并將其嵌入到稀疏的信號中，加入到一小段數(shù)據(jù)中。這些規(guī)則僅十分簡單的要求把信號同一些固定的波形相關(guān)聯(lián)，這些波形也都沒什么根據(jù)。關(guān)于這些采樣規(guī)則，最不同尋常的是它們可以使用一個傳感器，從稀疏的信號中高效的獲取信息，并且也不需要分析這些信號。甚至它還能使用數(shù)字化最優(yōu)方法，僅依靠一小段獲得的數(shù)據(jù)來重建全部信號。換句話說，CS是一種非常簡單并高效的數(shù)據(jù)獲取方法，它采用信號獨立方式，采樣率

4、低，依靠看起來不完整的一系列測量，經(jīng)過計算來重建信號。我們這篇論文意圖概述13中出現(xiàn)的基本的CS理論，展現(xiàn)該理論所包含的關(guān)鍵數(shù)學(xué)思想，并調(diào)查該領(lǐng)域一些重要的結(jié)論。我們的目標(biāo)是盡可能清楚的解釋CS理論，因而這篇文章主要是指導(dǎo)性的。該理論最吸引人之處是它涉及了許多不同的學(xué)科分支，包括應(yīng)用數(shù)學(xué)、概率論。在本文中，我們決定突出這一方面，特別是隨意性可以導(dǎo)致有效的感覺機制。我們也會討論重要的含義，解釋為何CS是同步傳感、壓縮數(shù)據(jù)的明確規(guī)則（如題所言），通過回顧重要的應(yīng)用來總結(jié)我們的探索。傳感問題在本文中，我們將討論一種傳感機制，該機制由線性泛函獲取記錄信息的信號f(t). , k=1,m. (1)我們簡

5、單的將想要取得的目標(biāo)同波形相聯(lián)系。這是一個標(biāo)準(zhǔn)的方案。如果傳感波形是狄拉克-德爾塔函數(shù)（尖形），例如，y是f在時域或空間域的一個矢量采樣值。如果傳感波形是像素的指標(biāo)函數(shù)，那么y是由數(shù)碼相機傳感器收集的典型圖像數(shù)據(jù)。如果傳感波形是正弦曲線，那么y就是一個傅里葉系數(shù)的矢量；這是磁共振成像（MRI）使用的傳感形式。還有很多其他的實例。雖然人們可以對連續(xù)的時域或空間域信號發(fā)展一種CS理論，但是我們的注意力集中在離散信號。原因是兩方面的：第一它在概念上較簡單；第二，現(xiàn)有的離散CS理論還不成熟（但是顯然為連續(xù)理論鋪平了道路也被視為“應(yīng)用”）。說到這里，我們由此對正在采樣的情形頗感興趣，此時測量的數(shù)值m比信

6、號f的度量n要小得多。由于多方面的原因，這類問題十分常見。例如，傳感器的數(shù)量可能受到限制?；蛘哂捎谔囟ǔ上襁^程需經(jīng)過中子散射，使得測量過程極其昂貴。又或者傳感過程十分緩慢，人們只能在IMR中對目標(biāo)進行有限次測量。諸如此類。 這些情況蘊含重要的問題。是否只能在m<<n時才能精確重建？是否可能設(shè)計m<<n的傳感波形來獲取幾乎全部的關(guān)于f的信息？人們?nèi)绾文軌蛴蛇@些信息得到近似的f？誠然，這種情況看起來很讓人畏縮，因為這樣就需要求解線性待定方程組。用A表示m×n的傳感矩陣，以矢量為一行（是a的復(fù)變換），當(dāng)m<n時，從中恢復(fù)的過程一般是不穩(wěn)定的：滿足的信號有無窮多

7、。但是我們或許能夠依靠目標(biāo)f存在的實際模型，來找出一種解決辦法。香農(nóng)定理告訴我們，如果f(t)帶寬實際上很低，那么少量的采樣就能滿足恢復(fù)的需要。下文我們就將看到，信號恢復(fù)實際上可以在更寬的信號模式上成功。非連續(xù)及稀疏信號傳感本部分展示CS理論包含的兩個基本前提：稀疏和間斷性。稀疏當(dāng)以適當(dāng)?shù)幕A(chǔ)表達時，許多自然信號有著簡明的表示。例如，在圖1（a）中的圖片和它在（b）中的小波變換。雖然幾乎所有的圖片像素都為非零值，波形系數(shù)提供了一個簡明的摘要：大部分系數(shù)都很小，因而少數(shù)相對較大的系數(shù)就包含了大部分信息。波形參數(shù)圖1：（a）一個原始百萬像素圖像，像素為0，255，(b)它的波形參數(shù)變換（為增強清晰

8、度而隨機擴展）。相對來說少量波形參數(shù)獲得了大部分信號能量；許多這類圖像可以深度壓縮。（c）對除了25000較大值的小波形擴展參數(shù)進行清零而完成重構(gòu)后的圖片（像素值為0，255）。幾乎看不出與原始圖片有差別。正如我們在“采樣過疏和稀疏信號重建”中描述的，圖片可以僅依靠96，000個非連續(xù)測量實現(xiàn)完美的重建。從數(shù)學(xué)上講，我們有一個矢量（例如圖1中的圖像像素），可將其在規(guī)范正交基（例如小波基）=內(nèi)擴展如下： （2）這里x是f的一項參數(shù)，?？梢苑奖愕膶表示為（是以為一列的n×n矩陣）。稀疏的含義現(xiàn)在清楚了：當(dāng)信號擴展時，我們可以將較小的參數(shù)丟棄而不會有大的誤差。一般認(rèn)為，通過保持與式（2）

9、中的最大值S的相應(yīng)關(guān)系，可以得到。根據(jù)定義，在此及下文，是參數(shù)的矢量，S的最大值設(shè)定為零。這個矢量嚴(yán)格的說是稀疏的，它的少數(shù)值為零；在S幾乎為非零值時，將這些目標(biāo)稱為S-稀少。既然是標(biāo)準(zhǔn)正交基，我們有，如果x是稀疏或可壓縮的衰減很快，那么x就由很好的近似，因此，的誤差很小。簡單說來，我們可以舍棄一大部分參數(shù)而沒有較大誤差。圖1（c）展示了一個例子，舍棄了97.5%的參數(shù)而獲得的近似圖像，同原百萬像素圖片幾乎分辨不出差別。 這個規(guī)則構(gòu)成了現(xiàn)代有損編碼標(biāo)準(zhǔn)，如JPEG2000以及其他標(biāo)準(zhǔn)，數(shù)據(jù)壓縮的一個很簡單的方法就可以從f計算出x，然后把重要參數(shù)S的位置、大小進行編碼。這樣一個過程需要知道參數(shù)x

10、所有的n，重要信息的位置可能提前并不知道（它們依賴于信號）；在我們的例子中，它們一般唯一圖像的邊緣。更普遍的是，稀疏是一個基本建模工具，它允許高效的基本信號變換；例如，準(zhǔn)確的統(tǒng)計學(xué)估計和分類，高效數(shù)據(jù)壓縮等等。本文是關(guān)于更加令人震驚而深遠的影響，然而，稀疏在獲得程序本身上有重要的支持作用。稀疏決定究竟多么高效地非自適應(yīng)地獲得信號。間斷性采樣假設(shè)我們有一對屬于的正交的（、）。第一個用于傳感式（1）中的目標(biāo)f,第二個用于表示f。對這對正交基的限制并不是必須的，僅僅會簡化我們的研究。定義一和之間的連系是： 式（3）在通俗英語中，相關(guān)性度量和的任何元素之間關(guān)系；也可見5。如果和包含相關(guān)的元素，相關(guān)性就

11、大。否則就小。不管多大多小，它都按照線性代數(shù)的規(guī)定。 壓縮采樣主要被認(rèn)為是低相關(guān)的，我們這就給出這樣的例子。在我們的第一個例子中，是標(biāo)準(zhǔn)基，而是傅里葉基，。由于是傳感矩陣，對應(yīng)在時域和空間域的經(jīng)典采樣方法。時間-頻率遵守，因此，我們可以有最大化的間隔。還有，錐形和正弦曲線在多個方面達到最大化間隔， 我們的第二個例子用小波形、noiselets表示。這里，Noiselets和Harr小波之間的一致性為，Noiselets與Daubechies D4和 D8小波間的一致性分別為2.2，2.9。這也可以延伸到更高的維數(shù)。（Noiselets與Spikes，傅里葉基同樣達到最大非一致性）。我們對Noi

12、selets的興趣來自以下事實（1）它們與提供圖像數(shù)據(jù)和其他類型數(shù)據(jù)稀疏表達的系統(tǒng)有非一致性（2）它們來自快速算法；Noiselet變換運行時間為o(n)時間，正如傅里葉變換，Noiselets矩陣不必存儲成向量應(yīng)用。這對于CS有效的數(shù)值計算是至關(guān)重要的。最后，隨機矩陣與任何固定基間均有較大的非一致性。均勻隨機的選擇一個正交基，這可以通過獨立均勻的在單位球面上采樣n個正交化的向量得到。然后很大概率上，和間的一致性大約為。還有，具有獨立同分布項（i.i.d.）的隨機波形（），高斯或者二值項，將與任意固定表述之間具有較低的一致性。注意這里很奇怪的指示；如果非相干系統(tǒng)的傳感很好，那么高效的機制應(yīng)當(dāng)取

13、得與隨機小波形的相互關(guān)系，例如白噪聲！采樣過疏及稀疏信號重建  理想的，我們想測量f的所有n個系數(shù)，但是我們只能觀測這些數(shù)據(jù)的子集，并獲取數(shù)據(jù) （4）其中是m<n的子集。有了這樣的信息，我們決定通過范數(shù)最小恢復(fù)信號；提出的重建為，其中是凸面最優(yōu)規(guī)劃的解（ ）        服從               （5）這就是說，在所有與數(shù)據(jù)組成目標(biāo)中，我們選擇范數(shù)最小的系數(shù)序列。（眾所周

14、知，最小的服從線性方程約束，如同線性方程使得更多的有效運算法則達到應(yīng)用一樣，改進非常容易。）使用范數(shù)作為稀疏促進方程可以追溯到幾十年前。一個早期的應(yīng)用是反射地震學(xué)，從數(shù)據(jù)組7,8中尋找出稀疏反射函數(shù)(標(biāo)志著地層中有意義的變化)。然而最小化范數(shù)不是恢復(fù)稀疏結(jié)果的唯一方法，其他方式比如貪婪算法9也已經(jīng)提出了。我們的第一個結(jié)果斷言，當(dāng)f足夠稀疏時，經(jīng)過范數(shù)最小的恢復(fù)是準(zhǔn)確的。原理110固定，假設(shè)在基下f的系數(shù)序列x是S稀疏的。在域均勻隨機的選擇m個測度。然后如果           

15、60;                             （6）對于正常量C，（5）的解在極大概率下是準(zhǔn)確的。（如果，那么成功的可能性就會超過1-。）還有，結(jié)果只是保證幾乎所有信號x序列有固定支點，詳見10。我們作三個注釋：（1）一致性的角色是非常顯然的；一致性越小，需要的樣本越小，因此我們的重點在前面部分的低一致性系統(tǒng)。

16、（2）我們可以無損的利用任意m個系數(shù)，這些系數(shù)可能遠小于信號大小顯然需要的。如果等于或者接近1，那么按足夠樣本Slogn順序的代替n。（3）通過最小化凸面函數(shù)，信號f可以從我們壓縮的數(shù)據(jù)中準(zhǔn)確恢復(fù)，這個函數(shù)沒有假設(shè)關(guān)于非零坐標(biāo)x的任何先驗信息，他們的位置，或他們的幅度我們假設(shè)全部沒有先驗知識。我們只是運行算法，如果信號正好是足夠稀疏的，那么精確恢復(fù)就可實現(xiàn)。這個定理事實上表明了一個具體的獲取協(xié)議：在非一致域中非自適應(yīng)的采樣，在采樣后調(diào)用線性規(guī)劃。按照這樣的協(xié)議將獲取到具有壓縮形式的信號。我們需要的是一個解碼器去解壓數(shù)據(jù)，這是最小范數(shù)的角色。事實上，這個非一致采樣理論拓展了早期關(guān)于稀疏信號采樣的

17、結(jié)果1，表明隨機1）可以成為一個非常有效的傳感機制，2）經(jīng)得起嚴(yán)密論證的考驗，因而這觸發(fā)了很多我們見到的、現(xiàn)在仍然見證的CS發(fā)展者。假設(shè)我們對采樣超寬帶信號但是譜稀疏形式，t=0,n-1,感興趣，其中n很大但是非零項的數(shù)量小于等于S（我們可以想的比較?。?。我們不知道在哪些頻率上是活躍的，而且不知道其幅度。因為活躍集合不一定是連續(xù)整數(shù)的子集，奈奎斯特/香農(nóng)采樣定理很可能沒有用（因為無法在初始時限制帶寬，可能導(dǎo)致所有的n時間采樣都是需要的）。在這種特定情形下，原理1主張我們可以重建具有任意未知頻率支撐集S的信號，利用Slogn時間采樣順序，見【1】。更多的是，這些采樣是不必仔細選擇的；幾乎任何具有

18、這樣采樣集合大小的采樣都可以。圖2顯示了一個實例。對于這方面的其他類型使用完全不同的觀點，見【11】【12】。圖2（a）一個稀疏真實取值信號（b）由最小60傅里葉系數(shù)（復(fù)值）重建后。重建是準(zhǔn)確的。（c）通過用范數(shù)取代范數(shù)完成最小能量重建；和有許多不同答案。的解并不提供一個合理的原信號近似。現(xiàn)在是討論以上內(nèi)容中概率角色的時候了。關(guān)鍵是為了得到有用而且有說服力的結(jié)果，我們需要訴諸于概率，因為我們不能希望所有大小為m的測量集合都有合適的結(jié)果。這就是原因。存在著位于域內(nèi),幾乎處處消失的稀疏信號。換句話說，我們可以找到稀疏信號f和規(guī)模幾乎為n(例如n-S)的大量子集，對于滿足。感興趣的讀者可能想檢查在【

19、13】【11】中討論的狄拉克梳子實例。一方面，給定這樣的子集，我們看到一串0，沒有算法可以重建信號。另一方面，理論保證集合的小部分精確恢復(fù)不發(fā)生的概率是可以忽略的（n的一個巨大負(fù)極能量）。這樣，我們只需要忍受一個很小的失敗概率。對于實際應(yīng)用，假設(shè)采樣數(shù)量足夠大，那么失敗的概率基本為0. 有趣地是，對于特定稀疏信號的研究表明我們至少需要階采樣。（我們的確知道，在時域存在著2S的子集，它們能在頻域重建任意S稀疏信號。僅僅抽取2S連貫時間點，實例參見“什么是采樣壓縮”以及【11】【12】。但這不是我們所要表述的。我們想讓大多數(shù)確定型號提供精確重建。）如果采樣更少，信息損失的概率會很高，重建算法無論多

20、么復(fù)雜，都是不可能完成的?？偨Y(jié)來說，當(dāng)一致性為1時，我們不需要多于采樣，但是也不能更少。我們采用一個非一致性采樣的例子總結(jié)這一部分，考慮圖1（c）所示的稀疏圖像，我們發(fā)現(xiàn)它只有25000個非零小波系數(shù)。我們?nèi)缓笸ㄟ^采取96000非一致測量（我們推薦讀者到10中看測量細節(jié)）并且求解（5）獲取圖像。最小化重建十分成功；。這個實例表明大約4倍于稀疏系數(shù)的采樣是足夠的。很多研究人員都在實驗中得出了相同結(jié)論。這就是著名的4-1實際規(guī)則，對于精確恢復(fù)，我們至少需要大約4倍的非一致采樣。完全壓縮采樣我們已經(jīng)展示可以利用少量的測量恢復(fù)稀疏信號，但是為了真正有說服力，CS需要能夠處理近稀疏信號和具有噪聲的信號。

21、首先，感興趣的普通物體都是近似稀疏而不是準(zhǔn)確稀疏。這里的問題是，利用高度稀疏采樣測量，能不能獲得這些物體準(zhǔn)確的重建。其次，在任何實際應(yīng)用中，測量數(shù)據(jù)將總是至少受到少量噪聲的干擾，因為感知設(shè)備不可能是無限精度的。因此CS需要對于這樣的非理想情形具有完全適應(yīng)能力?？偨Y(jié)為一點，數(shù)據(jù)中的小擾動應(yīng)該引起重建中的小擾動。這部分同時調(diào)查這兩件事情。在我們開始之前，然而，考慮恢復(fù)信號的抽象問題將會使研究簡化 ，矢量來自數(shù)據(jù) y=Ax+z， （7）其中A為傳感矩陣，給我們關(guān)于x的信息，z為隨機或者確定性未知誤差項。上一部分的設(shè)置利用這種形式表述，因為和 （R為M中提取中采樣坐標(biāo)的矩陣）?？梢詫憺閥=Ax，其中。

22、因此，我們可以處理抽象模型（7），考慮著x是物體在合適基下的系數(shù)序列。受限制的等距性在這一部分，我們引入一個關(guān)鍵的表示，這個表示被證明是研究CS中一般魯棒性的有效工具；所謂的受限制的等距特性（RIP）15。定義2對于每一個整數(shù)S=1,2,定義矩陣A的等距常量為滿足下式的最小數(shù)字，對于所有的s稀疏向量都滿足。 （8）我們將寬松地說矩陣A服從s階的RIP如果不是非常接近1。當(dāng)具有這個特性的時候，A矩陣近似保存了s稀疏信號的歐幾里得長度，這意味著s稀疏向量不能在矩陣A的零空間中（這是有用的，否則無法重建這些向量）。一個等價的RIP描述是來自矩陣A的所有s列子集，事實上幾乎正交。（因為矩陣的列比行多，

23、矩陣A的列不會精確正交。）為了看到RIP與CS之間的聯(lián)系，設(shè)想我們用矩陣A獲得S稀疏信號。首先假設(shè)遠小于1。這表示所有兩個S稀疏信號間的距離必須在測量空間很好的維持。這就是，對所有的S稀疏信號矢量，。正如下文所說，這個促進性的事實保證了高效的，完全的，用于鑒別基于壓縮測量S稀疏信號的算法。從稀疏采樣數(shù)據(jù)的一般信號恢復(fù)如果滿足RIP特性，那么通過求解下面的線性規(guī)劃，得到的重建是準(zhǔn)確的： 服從于 （9）原理2（16）假設(shè)，那么（9）的解滿足， 和 （10）對于某個常數(shù)，其中是將向量x中除最大的S成分外，全部設(shè)置為0。（正如所言，這個結(jié)果是由于第一作者【17】和尚未出版的，參見【16】【18】。）原

24、理2的結(jié)論比原理1的結(jié)論強。如果向量x是S稀疏的，那么向量x=，因此,重建是準(zhǔn)確的。但是這個新原理處理所有的信號。如果向量x不是S稀疏的，那么如果我們事先知道S最大值的位置x并且決定直接測量，（10）就可斷言重建的信號的質(zhì)量會很好。換句話說，重建就像預(yù)言般一樣好，具有完善的關(guān)于x的信息，將為我們提取S最重要的信息。另一項與之前結(jié)果不同的顯著結(jié)果是它是確定性的；它不涉及概率。如果我們幸運的擁有一個滿足原理假設(shè)條件的感知矩陣A，我們可以應(yīng)用它，我們保證可以恢復(fù)所有S稀疏向量，當(dāng)然是S最大向量，不存在失敗的概率。在這一點上，缺失的是S（可以有效恢復(fù)的分量數(shù)量）服從假設(shè)與觀測數(shù)量m或者矩陣行數(shù)的關(guān)系。

25、為了得到強大的結(jié)果，我們想尋找滿足RIP具有S值接近m的矩陣。我們能設(shè)計這樣的矩陣嗎？在下面一部分，我們將證明這是可能的，但是首先我們將驗證CS對數(shù)據(jù)污染的魯棒性。從噪聲數(shù)據(jù)中魯棒的恢復(fù)信號我們給定（7）中描述的噪聲數(shù)據(jù)，使用具有松弛約束的最小進行重建： 服從于         （11）其中e限制了數(shù)據(jù)中噪聲的強度。(也可以考慮諸如過濾選擇器【19】，或由Haupt 和 Nowak 20提出的組合最優(yōu)化程序；當(dāng)噪聲為高斯有限變化時，這兩種算法都能得出可靠結(jié)果。)問題（11）也可以在21后稱為LASSO；見22。按照我們最好的

26、理解，這是在8中首次引入的。這又是一個Convex問題，（一個二階錐規(guī)劃問題）存在很多有效的算法求解。原理3（16）     假設(shè)，那么（11）的解，對于某個常量和滿足，     （12）（這個理論同樣未被發(fā)表，他是【16】中結(jié)果的一個變形。）這很難再簡化。重建誤差受到兩項和的限制。第一項是沒有噪聲時發(fā)生的誤差，第二項與噪聲水平成正比。進一步，常數(shù)和一般較小。對于 的例子，和。圖3顯示了對于噪聲干擾數(shù)據(jù)的重建。原始信號重建圖3信號x（水平軸）通過【11】獲取了它的恢復(fù)（垂直軸）。在這個例子中，n=512,m=256

27、。信號是64稀疏的。在模型【17】，傳感矩陣是i.i.d.N(0,1/m),z是調(diào)整后的高斯白噪聲矢量，。這里 。這個最后的結(jié)果將CS建立為實用而且有效的感知機制。它是魯棒的。因為它不僅可以處理各類不一定稀疏的信號，而且很好的能夠處理噪聲信號。尚待完善的是設(shè)計有效的感知矩陣來滿足RIP。這是下一部分討論的內(nèi)容。隨機感知回到RIP的定義，我們想尋找具有任選列向量子集近似正交的感知矩陣。這些子集越大越好。    這里隨機性再次進入畫面。考慮一下感知矩陣：1）  通過在空間的單位球上均勻隨機采樣n個列向量形成；2）  通過從A采樣具有零均值，方差為1

28、/m的正態(tài)分布獨立同分布形成；3）  通過從A采樣隨機投影 P作為間斷采樣，并將其標(biāo)準(zhǔn)化為；4）  通過采樣對稱二項分布（P）或者其他子高斯分布。然后以壓倒性優(yōu)勢的概率，所有這些矩陣服從RIP（例如我們定理的條件），滿足 （13） 其中C是依賴于每一個情形的常數(shù)。1）2）3）使用概率論中相當(dāng)標(biāo)準(zhǔn)化的結(jié)果；對于4）則更加精妙一些，參見2324。所有這些實例中，采樣到滿足（13）而不滿足RIP的矩陣的概率是m的指數(shù)次小。有意思的，無論如何給出定理2的結(jié)論并采用少于（13）左端的采樣23，也不存在測量矩陣和重建算法。這樣，使用上面的傳感矩陣以及最小，是一種近似最優(yōu)感知策略。我們可

29、以采用第三部分中的正交基對，在“不連續(xù)傳感稀疏信號”建立RIP。對于,R隨機抽取m個坐標(biāo)，可以得到                                        （14）使得RIP很大概率上保證，見252

30、。如果要求失敗的概率不大于0(),對于某個>0，然后（14）已知的最好的指數(shù)是5而不是4(14中只有l(wèi)ogn)。這證明可以穩(wěn)定而且精確的，從非一致域的未采樣數(shù)據(jù)中重建幾乎稀疏的信號。最后，RIP仍然有感知矩陣，其中為任意正交基，是從適當(dāng)分布中隨機抽取的測量矩陣。如果固定基，利用1）-4）組裝測度矩陣，那么很大概率上，矩陣服從RIP特性，并滿足（13），其中C為依賴于每一情形的常數(shù)。這些隨機觀測矩陣，在某種意義下是通用的23；即使設(shè)計觀測系統(tǒng)的時候，稀疏基也不必已知。什么是壓縮采樣？典型的數(shù)據(jù)獲取過程如下：搜集到大量的數(shù)據(jù)，在壓縮階段大部分?jǐn)?shù)據(jù)被丟棄，這對于存儲和傳輸目的是必須的。用本文的

31、語言講，我們獲得一個高分辨率像素陣列f，計算傳輸系數(shù)的完整集合，編碼最大的系數(shù)并除去其他系數(shù)，本質(zhì)上以告終。這種大量獲取數(shù)據(jù)，然后壓縮的過程相當(dāng)浪費（可以設(shè)想具有百萬像素的數(shù)碼相機，像素，最后編碼圖片之使用幾百KB）。CS操作則不同了，它是“如果能夠直接獲取感興趣物體的重要信息”。通過采取0()隨機投影如“隨機傳感”，我們擁有足夠的信息重建信號，具有的精度和提供的一樣；目標(biāo)有最好的S近似，最好的壓縮表示。換句話說，CS數(shù)據(jù)獲取協(xié)議本質(zhì)上，將模擬數(shù)據(jù)翻譯為已壓縮的數(shù)字信號形式，最起碼在原理上，從少數(shù)傳感器獲取已壓縮信號。在獲取步驟后，需要的是解壓觀測的數(shù)據(jù)。CS與編碼理論中的觀點有一些表面上的相

32、似性，正似里-所羅門理論（RS）與實踐26。簡而言之在本文內(nèi)容中，我們可以將編碼理論中的觀點改寫過來：我們可以采用其前2S個傅里葉系數(shù)  ，k=0,1,2,2S-1，唯一的重建任意S稀疏信號，或者利用任意2S個連續(xù)頻率（恢復(fù)問題的計算成本為求解一個 Toeplitz系統(tǒng)和取一個n點傅里葉變形）。這是否意味著我們可以利用這個技術(shù)感知可壓縮信號呢？答案是否定的，主要的兩個原因如下。首先，RS解碼是一個算術(shù)技術(shù)，不能處理非稀疏信號（解碼通過求解多項式求根）；第二，尋找信號的支撐的問題-即使當(dāng)信號準(zhǔn)確稀疏時-從前2S個傅里葉系數(shù)是格外病態(tài)的（問題如同利用高度聚簇的少量數(shù)據(jù)外推一個高

33、自由度的多項式）。這些系數(shù)的小擾動將給出完全不同的結(jié)果，這樣對于有限精度數(shù)據(jù)，可信賴的支撐集估計實踐上是不可能的。盡管完全代數(shù)方法忽略了信息操作符的條件作用，擁有良好條件矩陣，對于精確估計是必須的，這是CS中的核心考慮，正如RIP扮演的角色。應(yīng)用事實上可壓縮信號可以通過與其信息級成比例的，非一致性測量有效采集，這意味著大量可能的應(yīng)用。n 數(shù)據(jù)壓縮。在某些情形下，稀疏基在解碼端可能是未知的，或者對于數(shù)據(jù)壓縮來說是難以實際執(zhí)行的。正如我們在“隨機傳感”討論的，然而，一個隨機設(shè)計的可以被認(rèn)為是一個通用的編碼方案，因為它不需要根據(jù)的結(jié)構(gòu)進行設(shè)計。（對于的知識和能力，只有載解碼恢復(fù)的時候需要）。這種通用

34、性對于像傳感器網(wǎng)絡(luò)27一類的分布式多信號編碼十分有用。我們建議讀者查閱Nowak和Goyal的文章中相關(guān)的討論。n 信道編碼。正如15鐘討論的，CS原理（稀疏性，隨機性，Convex最優(yōu)化）可以轉(zhuǎn)向并且應(yīng)用于設(shè)計快速糾錯碼，以防止傳輸過程中出現(xiàn)的錯誤。n 逆問題。在其他條件下，獲取f的唯一方式是使用特定形態(tài)的觀測系統(tǒng)。然而，假設(shè)信號f的稀疏基存在且與非一致，那么有效的感知是可能的。這樣的應(yīng)用包括MR血管造影術(shù)1和其他類型的MR設(shè)置28，其中記錄了傅里葉變換的子集，需要的圖像f在時域或者小波域是稀疏的。Lustig等人更加深刻的討論了這個問題。n 數(shù)據(jù)獲取。最后，在某些重要條件下，對于模擬信號完

35、全采集n個離散時間樣本是困難得（可能對于隨后的壓縮也是困難的）。這里，設(shè)計直接記錄離散、低碼率的非一致性觀測是有益的。最后這些應(yīng)用表明，數(shù)學(xué)和計算方法可以在常規(guī)的硬件設(shè)計具有顯著限制的領(lǐng)域，發(fā)揮重要的作用。例如，使用CCD或者CMOS的常規(guī)成像設(shè)備，被限制在感知可見光光譜。然而，一個CS相機使用數(shù)字微鏡陣列采集非一致測量（只需要一個感光元器件而不是百萬個），可以顯著的拓展這些特性。（參見【29】）沿著同樣的思路，我們的部分研究注重在對于寬帶信號進行“模擬-信息”轉(zhuǎn)換得設(shè)備（見Healy等人的文章）。我們的目標(biāo)是減輕對于常規(guī)ADC技術(shù)的壓力，現(xiàn)在受限制到采樣率為1GHZ。作為一個選項，我們提出了兩種用于A/I的特定結(jié)構(gòu)，在其中離散、低碼率非一致測量序列從寬帶模擬信號采集而來。在很大程度上近似，每一個測量值可以解釋為入射模擬信號f與模擬測量波形的內(nèi)積c。在離散CS框架下，我們的初步結(jié)果表明服，稀疏或者可壓縮模型的模擬信號（在某個模擬字典）可以通過以與其信息級別，而不是奈奎斯特速率，成比例的采樣率來獲取。當(dāng)然，我們必須提到，應(yīng)用離散CS方法恢復(fù)稀疏模擬信號時面臨的挑戰(zhàn)。對于