壓縮采樣介紹

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

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

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

4、低，依靠看起來(lái)不完整的一系列測(cè)量，經(jīng)過(guò)計(jì)算來(lái)重建信號(hào)。我們這篇論文意圖概述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)致有效的感覺(jué)機(jī)制。我們也會(huì)討論重要的含義，解釋為何CS是同步傳感、壓縮數(shù)據(jù)的明確規(guī)則（如題所言），通過(guò)回顧重要的應(yīng)用來(lái)總結(jié)我們的探索。傳感問(wèn)題在本文中，我們將討論一種傳感機(jī)制，該機(jī)制由線性泛函獲取記錄信息的信號(hào)f(t). , k=1,m. (1)我們簡(jiǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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