AnIntroductionToCompressiveSampling全文翻譯

1、An Introduction To Compressive Sampling 番羽譯（全文）一一壓縮采樣導(dǎo)論fy一或圖像采樣的傳統(tǒng)方法遵循香農(nóng)泄理：采樣速率大于等于信號頻率瑕人值（也叫的奈奎斯特速 率）的二倍。事實上，這原理構(gòu)成了音頻和視頻設(shè)備、醫(yī)學(xué)成像設(shè)備和無線電接收器等設(shè)備上的幾丁 所有信號采集協(xié)議的基礎(chǔ)（盡管對于一些信號，比如非帶寬受限的圖像，采樣速率不是通過香農(nóng)定理而 是由時間或空間分辨率決定，然而在這樣的體系里通常要在抽樣前使用抗混疊的低通濾波器進行帶寬限 制，所以香農(nóng)定理依然起到了一個隱式的作用）。例如，在數(shù)據(jù)轉(zhuǎn)換方面，標準的模數(shù)轉(zhuǎn)換器技術(shù)使用 的量化香農(nóng)定理表述為：信號均勻抽樣

2、速率人于等于奈奎斯特速率。木文概括論述了壓縮采樣的理論，也彼稱作壓縮傳感或者CS,是一篇突破了傳統(tǒng)信號獲取理論的 文章。CS理論斷言可以用比傳統(tǒng)方法更少的采樣點或測最值恢復(fù)信號或圖像。為了實現(xiàn)這一點，CS 依賴于兩個原則：稀疏性和非相干性，前者與所感興趣的信號右關(guān)，后者與傳感模式有關(guān)。稀疏性表達的思想是：連續(xù)時間信號的信息速率可能遠小于根據(jù)帶寬所計算出的值，或者說離散信 號取決于遠小于有限長度的一些量值，更明確的說，CS闡述了這樣一個弔實：從某種意義上說，當用 適當?shù)幕硎緯r有簡潔描述的情況下，許多自然信號是稀疏的或口J壓縮的。非相關(guān)性擴充了時域和頻域的二元性，并表達了這樣一種思想在W中有稀疏

3、表示的目標信號在它 們所在的域上是展開的，正如在時域中沖擊函數(shù)或者峰值函數(shù)在頻域中是展開的一樣。換句話說，非相 關(guān)性描述的是：與我們感興趣的信號不同，采樣/傳感信號波形在基W中有一個相當密集的表示。至關(guān)重要的發(fā)現(xiàn)是能夠設(shè)計一個有效的傳感或采樣方案來捕捉內(nèi)嵌在稀疏信號里的有用的信息，再 將其壓縮。這些方法是菲口適應(yīng)的，只需要將信號與少量的與桶疏化的基不相關(guān)的固定波形相關(guān)聯(lián)即町。 更難以芒仁的是這吐采樣方法允許一個傳感器在稀疏佇工中冇效的獲取信息來重建這個佇更進步 來說，可利用數(shù)值優(yōu)化通過少最采樣信號來垂建整個信號。換句話說，CS是一個非常簡單有效的信號 采集方法,通過這個方法，樣本町以不依賴于原

4、始信號利用看起來不完整的數(shù)據(jù)在低速釆樣情況卜使用 計算機重構(gòu)信號。這篇文章的I的是概述CS理論的基本原理，介紹了構(gòu)成這一理論的重要數(shù)學(xué)思想，概述了在這個 領(lǐng)域中的幾個求要成果。CS理論其中一個魅力所在是它涉及到了應(yīng)用數(shù)學(xué)中的多個分支，尤其涉及到 了概率論，文中刻意強調(diào)了這方面，尤其是隨機性能推導(dǎo)出非常有用的傳感機制這一似乎令人驚訝的爭 實。文中還討論了它的Itt嚶恿義，解釋為什么CS對十|可時傳感和丿玉縮數(shù)期是一個實用的方案，并迪過 一些重要的應(yīng)用來證明結(jié)論。信號感知問題在這一部分，我們將討論傳感機制，其中信號f（t）的信息通過線性泛函來獲得，記錄的值如2人=,k = l,.,in（1）將波形

5、與期墊獲得的目標簡單的關(guān)聯(lián)，這是一個標準架構(gòu)，例如，如果傳感波形是單位脈沖函數(shù), 則y是f在時間或空間上的抽樣值的矢量：如果傳感波形是像素的指標函數(shù)，則y是通過數(shù)字攝像機 中的傳感器采集的圖像數(shù)據(jù)：如果感知波形是正弦函數(shù)，則y是傅里葉系數(shù)。核磁共振成像用的就是 這種傳感模式，當然其他的例子也大最存在。盡管可以建立一個持續(xù)時間/空間信號的cs理論，但這里只關(guān)心離散信號f eRn的情況，有兩 方面原因：苗先，概念較為簡單：其次，已仃的離散cs理論己經(jīng)非常成熟了（顯然己經(jīng)為連續(xù)理論鋪 平了道路在“應(yīng)用”部分還會介紹）。因此，我們接下來關(guān)心的是采樣過疏的情況，在這種情況下， 觀測數(shù)H1L匕借號f的維數(shù)

6、n小得多。出丁各種原因，這樣的問題極其普遍，比如，傳感器的數(shù)屋有限, 或若是由于有些通過中子散射成像處理的測量方式非常昂貴，又或者是因為諸如磁共振成像時-樣，由 于傳感處理太慢，導(dǎo)致只能對目標檢測很少的次數(shù)。這些問題的存在導(dǎo)致了重人難題的出現(xiàn)。僅僅通過m1lk. jin通俗的講，相干度測最和中中任意兩個元素之間的最大相關(guān)性。如果和W包含相關(guān)元素, 相干度就很大，否則就很小。但無論有多犬或多小都滿足（，旳wl，&。壓縮采樣主要針對低相干正交基，現(xiàn)在我們給一些這樣的例子：第一個例子中，是沖擊響應(yīng)基 （t-k）, W是傅里葉基0廣由于是感知矩陣，這與時間或空間中的經(jīng)典采樣 格式-致，時間頻率對服從=

7、 因此有最大非相干性。進一步來說，脈沖信號和正弦信號不 僅在一維空間上不相干，在任意維度上（比如二維，三維等等）都不相干。第個例子中，歿是小波變換基，是noiseletso Noiselets與Haar小波基的相十度為血，通過 人范用樣本值n得到noiselets與Daubechies D4和D8小波的相干度分別人約為2 2和29。擴展到高維 數(shù)上也是如此（noiselets與spikes、傅里葉基同樣達到了址人非相干性）。我們対noiselets的興趣來自以 卜幾方而原因：noiselets與提供圖像數(shù)據(jù)和其他形式數(shù)據(jù)的稀疏表示系統(tǒng)不相干；2） noiselets適合 使用快速算法，nois

8、elet變換耗時。），并且與傅里葉變換一樣，noiselet矩陣在形成矢呈時不需要占 用存儲空間，這對于CS實現(xiàn)高效數(shù)值計算是至關(guān)覓要的。最后，隨機矩陣與任何固定基之間均不相干。通過將從單位圓上獨立均勻采樣得到的n個向最標準 正交化，均勻隨機的選擇一個正交基，這樣在很大概率上和空的相干度是丁巫了。通過擴充具 有獨立同分布元素的隨機波形就（t）也展示出與固定表示空有非常低的相干件，例如高斯分布或1二 進制項。注意到這里何一個非常奇特的暗示：如果非相干系統(tǒng)感知是良好的，那么有效的機制就應(yīng)該獲 得與隨機波形的關(guān)聯(lián)，例如白噪聲！欠采樣和稀疏信號的重構(gòu)理論上，我們希塑可以測量f的所有n個系數(shù)，但實際上我

9、們只觀測它的一個子集，采集的數(shù)據(jù)為:yk =,keM（4）其中M是基數(shù)mn的子集。利用這些信息，我們利用I】-范數(shù)極小化來巫構(gòu)信號；所提出的重建廣由f* = Tx*給出，其中x是凸優(yōu)化下的解（|x|l：=工兀|）：niin| x| subject to yk =,VkeM（5）這就是說在所有f = Tx與數(shù)據(jù)一致的對象中，我們挑選其系數(shù)序列具有最小I】范數(shù)的對象。（我們都知道，受限于線性均等式的極小化1】能夠很容易的改寫為一個線性規(guī)劃問題，如此便提供了一種高效的 解決方案算法。）用h范數(shù)作為稀疏提升函數(shù)可以追溯到幾十年前。最早應(yīng)用在反射地震學(xué)，其中的稀疏反射函數(shù)（用 以指示地表卜各層的甫要變化

10、）從帶寬受限的數(shù)據(jù)中得到。然而I】極小化不是求解稀疏解的唯一方法, 其他方法（比如貪婪算法）也己被提出。上述討論結(jié)果證明：當f足夠稀疏時，通過h極小化復(fù)原信號是準確的。定理1固定f eDn,假設(shè)f的系數(shù)序列x在基屮I、是S稀疏的。在域卜均勻隨機的選擇m個測量值。 如果mC7/3（a）.P）Slogn（6）對于正常量C, （5）的解極人概率下是準確的。在此做三點解釋：1）相干性的作用是非簾明顯的：相干度越低，需要的樣本就越少，I人I此我們在前一章節(jié)中重點強 調(diào)了低相干度的系統(tǒng)。2）通過測量任一組m系數(shù)（町能遠小于信號的表面需要）人們不會蒙受信號損失。如果 等丁或接近于1，那么Slogn次采樣就足

11、夠了，而不需要11次采樣。3）在事先不知道x非零坐標個數(shù)、位置的條件卜,信號f町以利用極小化凸泛兩得到的壓縮數(shù)據(jù) 集來重構(gòu)，關(guān)于他們的幅值事先完全未知。這個定理確實提供了一種非常具體的捕獲方案：在非相干域的非自適應(yīng)采樣和在采集之后的線性規(guī) 劃。按照這一方法，町以獲得壓縮形式的信號。所需要的是一個解碼器去解壓數(shù)據(jù)。這就是1極小化 所起的作用。事實上，這個非相干采樣是早先譜稀疏信號采樣結(jié)果的推廣，由此展現(xiàn)了隨機性是-個可靠的證明，并 可以成為一個非常有效的傳感機制，也許正是因此引發(fā)了現(xiàn)在CS蓬勃的發(fā)展。假設(shè)我們對超寬帶采樣 感興趣，但譜稀疏信號的形式為：f（t）=工；嚴7 = O,.,n-1其中I

12、】很大，但非零元素X）小于等于S （我們町以理解為非常?。Ｎ覀儾恢涝谀男╊l率上是活躍的 也不知道其幅值有多人。因為活躍集合不一定是連續(xù)整數(shù)的子集，香農(nóng)/奈奎斯特定理很町能沒有用（因 為不能限制帶寬的先驗，可能導(dǎo)致所有的n時間采樣都是需要的）。在這種待定的情形卞，通過定理1 我們町利用Slogn個抽樣值直建具有任意未知頻率支撐集S的信號。而且，這些樣本不需要楷挑細選, 幾乎任意具有這樣樣本空間大小的樣本都可以?，F(xiàn)在討論概率在以上內(nèi)容中的角色。要點是獲得有用有力的結(jié)果，我們需要借助概率，因為我們不 希望所有大小為m的測量集合都有介適的結(jié)果。一些特殊的桶疏信號幾乎在整個域上都為零，換言 之，我們

13、可以知道稀疏信號f和人小幾乎為n的子集（例如11-S）,對所有kwM , yk=W。因此，町以 使用抽彖模型（7）,其中x是適當基下的系數(shù)序列。約束等距性在這部分，我們介紹一個重要的概念，這個概念已經(jīng)證明對于CS的一般魯棒性的研究非常有用； 被稱作為約束等距行（RIP）。定義2：對每個整數(shù)S=l,2,，定義矩陣A的等距常最心作為滿足下式的最小的數(shù)Q-爲）|X| 討 |做| 迄 Q+4）|x|；對于所有的S稀疏向量x都滿足。如果4不是非常的接近1，我們就寬泛的說矩陣A滿足S階的約束等距性。如果這一性質(zhì)成立， 矩陣A近似保持S稲疏信號的歐式長度，這反過來證明了 S稀疏向量不在矩陣A的零空間中。（這

14、是 有用的，否則無法重建這些向量。）約束等距性的等價描述是：矩陣A的所有S列的子集都近似正交（矩 陣A的列向量不能準確正交，因為列大于行）。為了看到RIP與CS的聯(lián)系，設(shè)想我們用矩陣A獲取S稀疏信號。假設(shè)$充分小。這意味著所有的S稀疏信號之間的成對距離必須很好的保存在測最空鬧中。即滿足所有S-稀疏矢量忌吃。正如卜一節(jié)中所述的，這個令人鼓舞的爭實保證了利用己被壓縮的測 最值高效、穩(wěn)健的識別S-稀疏信號的算法的存在。從欠采樣數(shù)據(jù)中復(fù)原普通信號如果滿足約束等距性，根據(jù)線性規(guī)劃給出了一個精確甫建的式子：niin | x|L s.t.Ax= y（= Ax）（9）xe M 定理2：假設(shè)為s 返-1，（9）

15、的解x*服從(10)l|x*_x|kg|xT Ik zand llx-xllQ-llx-Xs K對T常數(shù)c0其中w是將向最X中所方的除了最人的s外全部設(shè)賈為o后的向氐定理2的結(jié)論比定理1的結(jié)論更有說服力。如果X是S稀疏，則X =卷，那么復(fù)原是準確的。如 果X不是S稀疏,那么(10)式斷肓：復(fù)原信號的質(zhì)量恰如人們提前知道X的S個最大值的位置并直 接測量的結(jié)果那么好。換言乙 重構(gòu)的結(jié)果非常好，就好象仃對X非常了解的先知為我們從S中提取重 要的信息一樣。與我們早先的結(jié)果的另一個驚人差別在于他是確定性的，不涉及概率。如果我們足夠幸運使感知矩 陣A滿足定理的假設(shè)條件，就町以應(yīng)用它，并保證精確恢復(fù)所有的S

16、矢量，其本質(zhì)是復(fù)原所有適量的S 個最大元素：即，不存在失敗的概率。用此方法缺失的是服從假設(shè)的S (町以有效復(fù)原的分最數(shù))與觀測數(shù)m或者矩陣的行數(shù)的關(guān)系。 為了導(dǎo)出更有效的結(jié)果，我們希塑找到滿足RIP條件的使得S接近于m的矩陣。我們能設(shè)計這樣的矩 陣么？在卜一節(jié)中，我們將證明這是可能的，但是卜面將首先考察CS面對數(shù)據(jù)干擾的魯棒性。噪聲信號的穩(wěn)健恢復(fù)我們在(7)中給了一個噪聲數(shù)據(jù)，并利用具有寬松約束的I】范數(shù)極小化來重建min | 利、s.t.| Ax-y|12e(n)其中w限制了噪聲在數(shù)據(jù)中的含最。(我們町以考慮一些復(fù)原方法，比如Dantzig選擇器或者Haupt 和Nowak提出的組合優(yōu)化方案

17、；這兩種算法在方怎仃界的高斯噪川情況下都是町以證明的結(jié)論。)這又 是一個凸優(yōu)化問題(二階錐規(guī)劃問題)，求解此問題有多種有效的算法。定理三：假設(shè)爲s-1，對于常最C。和C, (11)的解X*服從|x*-x|12qj-|x- h /Vs + q-e(p)這已經(jīng)很難更簡單了，覓構(gòu)誤差受到兩項和的限制，第一項是沒有噪聲時的誤差，第二項正比于噪 聲水平。此外，常量C。和是特征小量，例如，在J2S =1/4的情況下，Co C-Slog（n/S）,（13）那么所有這些矩陣服符合RIP,其中C是與具體實例有關(guān)的常量。1） in）用了概率論中相當標準的 結(jié)果，關(guān)于iv）的論證更復(fù)雜一些。在所有這些例子中，抽樣矩

18、陣滿足（13）但不符合RIP的概率是 關(guān)于m的指數(shù)型小最。有趣的是，沒有測最矩陣或重構(gòu)算法可以用比式（13）更少的采樣得出定理2 的結(jié)論。在這個總義上說，使用隨機矩陣與I】極小化相結(jié)介的方式是接近最優(yōu)的感知策略。我們也可以像“非相干性和稲疏信號的傳感”那一節(jié)所述的那樣建立正交基對的RIP。用A= ROP . 其中R隨機均勻地抽取m個坐標，使mCS（logn）4（14）是以極人概率具有該性質(zhì)的充分條件。對于某些00,想要使失敗的概率不人于O（n）,那么 （14）中最介適的指數(shù)應(yīng)該是5而不是4。這證明了可以從非相干域中極度欠采樣數(shù)據(jù)中穩(wěn)定精確的覓 建近稀疏信號。報后，A=DP也町以成立約束等距性（

19、RIP）,其中W是任意正交基，是從適當?shù)姆植贾须S機 取出的mxn的測量矩陣。如果固定按1）iv）所述構(gòu)成測量矩陣，如果滿足（13）,那么矩陣 A=OT將在很人概率上符合rip,其中C為與具體實例有關(guān)的常最。這種隨機測慣爐陣從某種意 義上足普適的；在設(shè)計感測系統(tǒng)時甚至不需耍已知林疏基。什么是壓縮采樣？典型的數(shù)據(jù)獲取過程如卜：人量數(shù)據(jù)被采集，但人部分數(shù)據(jù)在壓縮階段為了便于存儲和傳輸而被去 棄。用本文的話說，我們獲得一個高分辨率像素陳列f,計算完整的變換系數(shù)，編碼最大的系數(shù)并將 其他系數(shù)去棄，本質(zhì)上以結(jié)束。這種人量獲取數(shù)據(jù)再壓縮的過程是極其浪費的（我們町以想象一下 貝有幾百萬像素的數(shù)碼相機，但最后編

20、碼出的圖片僅有幾百KB）。CS的操作則不同了，就好像“可以直接獲取感興趣對彖的最主要信息”一樣。通過如“隨機感知”一 節(jié)所述的那樣進ij O（S10g（n/S）次隨機投影，就可以巫建至少利 一樣準確的信號。換句話說，CS 測量協(xié)議本質(zhì)上將模擬數(shù)據(jù)轉(zhuǎn)換成已壓縮的數(shù)字信號形式，因此至少從原理上講，我們能夠用少量的傳 感器獲得超分辨率信號。獲取之后，只需解壓測量數(shù)據(jù)即町。CS同編碼理論，更梢確的說同Reed-Solomon （RS）碼的理論和實踐中的觀點在表面上有些相似性。 就本文討論內(nèi)容簡單的說，町以采用編碼理論來住立如卜觀點：M以從信號的前2S個或任意相繼的2S 個傅里葉系數(shù)久二工二兀= 0，l

21、，2,.,2S-l9中唯一更建任總的s稀疏信號。這是否意味著能夠利用這項技術(shù)來感知可壓信號？答案是否定的，主 要有以卜兩方面原因：首先，RS解碼是一個代數(shù)問題，不能用于處理卄稀疏信巧（解碼通過求解寒項 式求根）：其次，即便信號完全稀疏，根據(jù)前2S個傅里葉系數(shù)尋找信號支撐集的問題是非常不適合的（這問題就如同利用高度集中的少量數(shù)據(jù)求解高階多項式一樣）。這些系數(shù)的微小干擾都將產(chǎn)生完全不 同的結(jié)果，因此利用有限精度的數(shù)據(jù)對結(jié)果進行可靠估計是幾乎不可能的。然而，純粹代數(shù)方法忽略了 信息的調(diào)節(jié)作用，擁有良態(tài)矩陣是CS所關(guān)注的核心問題，因為良態(tài)矩陣是對信號精確估計的關(guān)鍵。 應(yīng)用信號壓縮可以被與信息水平Sn成

22、正比的若干不相干測鼠量捕獲，這一爭實有著深遠影響并關(guān)系 到許多可能的應(yīng)用：數(shù)搖壓縮。對于數(shù)據(jù)壓縮，在某些條件卜解碼器上桶疏基W町能未知，或者并不能很實用的實際施 用。但是，正如在“隨機測量”中所討論的隨機設(shè)計的可看作普適解碼策略，因為它并不需要設(shè)計的 同時考慮田的結(jié)構(gòu)（只有解碼或恢復(fù)f時才需要和田相關(guān)的知識和實現(xiàn)W的能力）。這種普適性特別 有助于諸如傳感器網(wǎng)絡(luò)之類的多信號裝置的編碼。關(guān)于這個問題請讀者參考Nowak等人及Goyal在 其它地方的論文。信道編碼。正如文獻15所解釋的，圍繞CS的原理（稀疏性，隨機性，和凸優(yōu)化）可以將其用于 設(shè)計快速糾錯碼，防止錯誤信號傳輸?shù)陌l(fā)生。反面難題：仍然還有

23、其它一些情況,求得f的唯一途徑可以是用某個模態(tài)的測定系統(tǒng)e，但需要假 定與不相干的f的桶疏基T是存在的，令效的測量才有町能實現(xiàn)。一種這樣的應(yīng)用與MR血管造影 術(shù)和其它類型MR設(shè)備相關(guān)，其中記錄著f的傅里葉變換子集，所希墊的圖像F在時間域和小波域上 均稀疏。這個難題里的其它領(lǐng)域Lustig等討論得更深入。數(shù)據(jù)采集：有時在一些重要情況下，當最終需5!全部測量模擬信號的n個離散時間樣本時可能難以 實現(xiàn)（并II也難以繼續(xù)壓縮）。但在不相干測量時，這樣町能付助于設(shè)計出能夠直接記錄卜所傳入的離 散的、低采樣率的模擬信號物理采樣設(shè)備。這些應(yīng)用中的最后一個應(yīng)用說明，采用數(shù)學(xué)和計算機方法町能會給傳統(tǒng)硬件設(shè)計有限

24、制的那些領(lǐng)域 產(chǎn)生非常人的影響力。彼如，采用CCD和CMOS技術(shù)的傳統(tǒng)圖像設(shè)備基本上僅限于可視光譜。但是， CS相機用數(shù)字微鏡陣列來集個相干測量值也許能夠明顯擴充其能力。與此同時，我們中的一部分研究者己致力于研究大帶寬模擬信息（A/I）轉(zhuǎn)換的高級設(shè)備（這個問 題也町參加Healy等撰寫的文章）。冃標是幫助減輕傳統(tǒng)模擬數(shù)字（A/D）轉(zhuǎn)換技術(shù)的樂力，當前該技 術(shù)限FlGHz檔次的采樣速度。作為備選方案,我們設(shè)想出兩種特殊的、可以從高帶寬模擬信號中獲得 離散的、低采樣率，不相干測量序列的A/I架構(gòu)。針對高階逼近，每一個測量yk，都町彼認作入射模擬 信號f與模擬測量波形碰的內(nèi)積（f,pk）相當于離散C

25、S框架那樣，初步結(jié)果表明遵循稀疏或可壓縮 模型（在某一模擬詞匯T中）的信號町以被捕獲，使用這些設(shè)備以正比于信息等級而不是奈奎斯特頻 率。當然，如果要利用離散CS方法恢復(fù)出模擬稀疏信號，存在著挑戰(zhàn)性的問題有待克服。全面解釋清 楚這些問題超出了本文的范也，作為首先的一個階段點，供讀者簡單的接受其思想，離散/采樣稲疏詞 匯允許適當?shù)膹?fù)原。本文的兩大主要架構(gòu)如下：1）非均勻采樣器（NUS）我們的第一個架構(gòu)只是把隨機或偽隨機采樣時間點上的信號量化。即yk = f（tk）= （f,6tk）o事實上這些隨機或偽隨機時間點是通過處于抖動規(guī)則格子上的標示（低采樣率）術(shù) 樣點得到的。由于尖峰與正弦信號之間不相干，因此這種架構(gòu)町用于對具冇遠低于那奎斯特頻率的稀疏 頻譜信號采樣。為然這和減少采樣率有關(guān)的益處很大，因為這提供了附加電路穩(wěn)定時間，并貝有降低噪 聲等級的效果。2）隨機預(yù)枳分（RMPI）。我們第二個架構(gòu)可用于更人的桶疏域和大部分在時間-頻率平面有桶疏特 征的最顯著的那些信號。雖然不可能以極高的采樣率把模擬信號數(shù)字化，但非常 可能實現(xiàn)以很高的速率改變它的極性。RMPI