壓縮傳感的講座

1、壓縮傳感報告理查德.巴拉尼克萊斯大學發(fā)表在IEEE信號處理雜志,2007 年7月背景香農/奈奎斯特采樣定理告訴我們，為了不丟失信息均勻采樣信號時，我們 必須采取至少兩倍的帶寬的采樣頻率。在許多應用程序中，包括數(shù)字圖像和視頻 攝像頭，奈奎斯特采樣頻率會很高，我們最終得到的采樣信息太多，必須壓縮存 儲或傳輸。在其他應用程序,包括成像系統(tǒng)(醫(yī)學掃描儀，雷達)和高速數(shù)模轉換器， 增加采樣率或密度超出了，當前最先進設備的采樣范圍，并且非常昂貴。在篇論文中，我們將學習一種新的使用壓縮傳感技術，來解決這些問題【1,2】。 我們將以一個更一般的線性測量方案取代傳統(tǒng)的采樣和重建方法，加以優(yōu)化。以 明顯低于奈奎斯

2、特速率的采樣頻率，獲得某些種類的信號。相關這里提出的方法可以用來說明本科或研究生數(shù)字信號處理的統(tǒng)計數(shù)據(jù)和應 用數(shù)學中遇到的，數(shù)據(jù)采集、線性代數(shù)、擴展基礎、逆問題、壓縮降維等各種優(yōu) 化問題之間的聯(lián)系。先決條件理解和教學這種方法所需的先決條件是線性代數(shù)、優(yōu)化知識和概率知識。問題說明奈奎斯特抽樣利用其頻帶限制，完全描述了信號。我們的目標是減少測量的 數(shù)量，通過利用其壓縮性完整地描述一個信號。轉折是我們的測量不是點樣品， 但是一般較之線性泛函更具普遍意義的信號?？紤]一個圓，實值finite-length、一 維離散時間信號x,我們認為這是一個NX1列向量與元素xNRN,N = 1,2,。，N。 我們對

3、待一個圖像或更高維的數(shù)據(jù)vectorizing成一長一維向量。任何信號RN可以在NX 1的基礎上向量我 N i = 1。為簡單起見，假設是正 交的基礎。形成NXN基礎矩陣:=1 I 2 I。我 I N通過疊加向量作為列，我們可 以表達任何信號x，x =XNi=1si i or x = s其中年代是NX1列向量的權重系數(shù)si = hx,2 = T我x和T表示 厄密共軛轉置操作。顯然,x和年代是等價表示相同的信號，與x在時間域和域。我們將重點討論信號稀疏表示,x是一個線性組合的K基礎向量，與KN。也就是說，只有K的si(1)非零和(N?K)為零。稀疏是出于這樣一個事實，許多自然 和人造的信號是可壓

4、縮的，存在著基礎的表示(1)有幾大系數(shù)和許多小的系數(shù)?？?壓縮信號K-sparse來近似表示,這是變換編碼的基礎3。例如,自然圖像往往是可 壓縮的離散余弦變換(DCT)和小波基礎3的JPEG壓縮和JPEG - 2000標準為基 礎。音頻信號和通信信號在局部傅里葉計算可壓縮。變換編碼的過程中扮演著重要的角色在數(shù)據(jù)采集系統(tǒng)，如數(shù)碼相機，樣本的數(shù) 量很高，但信號是可壓縮的。在這個框架中，我們獲得完整的N-sample x信號，計算 轉換系數(shù)的完整通過年代 si = Tx;定位最大K系數(shù)和丟棄(N?K)系數(shù)最小;和編 碼的最大系數(shù)K值和位置。(在實踐中，我們還和位置的值轉換為數(shù)字)。不幸的是,samp

5、le-then-compress框架患有三種固有的低效率:首先，我們必須 先從一種潛在的大量的樣品氮即使最終所需的鉀很小。其次，編碼器必須計算所有的N轉換系數(shù)si ，即使它會丟棄所有但K。第三,編碼器面臨編碼的開銷大系 數(shù)的位置。作為替代,我們將研究一個更一般的數(shù)據(jù)采集方法，凝結的信號直接在壓縮表 示沒有經歷的中間階段N樣本?？紤]更一般的線性測量計算的過程MN內部產 品之間x和一個向量的集合 .疊加yj進去X1的測量向量y和測量向量 行成一個MXN.S 一一一一一一一一一(a)(b)圖1:(a)壓縮傳感測量過程(隨機高斯)測量矩陣A和離散余弦變換(DCT)矩陣。 系數(shù)向量稀疏與K = 4。(b

6、)測量過程的產品矩陣XXX四列對應的非零si高亮顯 示。y測量向量的線性組合這四列。矩陣X(1)替代，我們可以寫XXXX.見圖1(a)(2) 的圖形描述。請注意，測量過程非自適應性;即，X不以任何方式依賴于x信號。我們在接下來的目標是設計一個測量矩陣X和K-sparse和可壓縮信號重建 算法,只需要M約等于N或者稍微測量，大約的數(shù)量盡可能多的測量系數(shù)編碼在 傳統(tǒng)轉換編碼器。我們的方法是基于壓縮傳感理論的介紹最近在1、2。解決方案解決方案包括兩個步驟。在第一步中，我們設計一個穩(wěn)定的測量矩陣入確保 重要信息在任何K-sparse或可壓縮信號不是破壞的降維x 2 RN down to y 2 RM.

7、 在第二步中,我們開發(fā)一個重建算法恢復x從測量。起初，我們關注到底K-sparse 信號。5.1穩(wěn)定的測量矩陣首先,我們設計了測量的數(shù)據(jù)采集系統(tǒng),它是基于矩陣X。我們的目標是，讓米 測量向量(y),我們可以穩(wěn)定重建length-N信號x,或相當于其稀疏系數(shù)向量年代x 的基礎。顯然不可能重建如果x的測量過程損失的信息。不幸的是,一般是這樣: 由于測量過程是線性和中定義的術語矩陣X和Y,解決年代給定y(2)只是一個線 性代數(shù)問題，和M N,方程有少于未知，使解決方案一般病態(tài)。然而,K-sparsity年代來到我們的救援。在這種情況下，測量向量y只是一個線 性組合的X的K列對應的XXX(b)(參見圖

8、1)。因此，如果我們知道先驗K條目的 年代是零，然后我們可以形成一個MXK線性方程組解出這些非零項,在現(xiàn)在的數(shù) 量方程米的數(shù)量等于或超過未知K。確保一個充分必要條件這米XK系統(tǒng)狀態(tài)良 好的，因此運動穩(wěn)定逆這對于任何向量v共享相同的K非零項年代XXXX 在詞，矩陣X必須保持這些特定K-sparse的長度向量。當然,在實踐中我們不會知 道K非零項的位置年代。有趣的是,一個可以顯示K-sparse穩(wěn)定逆的充分條件 和可壓縮信號是X滿足(3)任意3 sparse向量v .這是所謂的限制等容屬(RIP1。穩(wěn)定的另一種方法是確保測量矩陣X是不連貫的與sparsifying基礎X,向 j 不能稀疏表示向量我

9、,反之亦然(1、2、4)。經典的例子功能三角洲和傅立葉正 弦曲線峰值扮演的角色 j 和我;傅里葉不確定性原理立即收益率不連貫。所以，給定一個sparsifying基礎X,我們如何構建一個測量矩陣X,X =XX撕嗎?不幸的是，僅僅是驗證給定的X combinatorially RIP復雜的;我們必須驗 證(3)為每個X K的非零項的可能的組合length-N向量v。在壓縮傳感,我們回避這個問題通過選擇X隨機矩陣。例如，我們畫出矩陣元 素X作為獨立和恒等分布的隨機變量(iid)從零均值,1 / N-variance高斯密度(白噪 聲)(1、2、5)。然后，測量y僅僅是M x的元素的不同隨機加權線性

10、組合(記得圖 1(a)和注意x)的隨機結構。一個高斯X有兩個有趣的和有用的屬性。首先,X是語無倫次的基礎X =我 三角洲峰值高概率，因為它需要完全N峰值代表X的每一行。更嚴格，使用濃度的 測量參數(shù)，一個MXN iid高斯矩陣X =我=X可以展示概率高的RIP如果M cK 日志(N / K)，在一個小的常數(shù)c1、2、5。因此，我們可以預期恢復length-N K-sparse 高概率和可壓縮信號從justM cK日志(N / K)N隨機高斯測量。其次，由于iid高斯 分布的屬性產生X，矩陣X = XX也iid高斯不管(正交)sparsifying基礎矩陣X的選 擇。因此，隨機高斯測量X是普遍,X

11、 = XX RIP高概率為每一個可能的x。在眾多 國家中，隨處矩陣隨機1項也可以顯示RIP和普遍性屬性5。5.2信號重建算法RIP提供了理論保證K-sparse或可壓縮信號可以完全米所描述的測量在y, 但它并沒有告訴我們如何恢復它。信號重建一步必須測量y,隨機測量矩陣X(或 隨機的生成)的種子,sparsifying依據(jù)X X和再生length-N信號，或相當于其稀疏系 數(shù)向量。我們再次開始關注K-sparse信號。XXXXXX因此,我們的目標是找到信號的稀疏系數(shù)向量翻譯后的空的空間。XXX當p = 0我們獲得“0 “常態(tài)”，非零項的數(shù)量;因此K-sparse向量“0 K。最低的2規(guī)范重建:這

12、種類型的解決逆問題的經典方法是最小二乘法;也就是 說，我們選擇翻譯零空間中的向量H與最小的2范數(shù)(能源)：甚至有一個方便的封閉的solutionb XXX。但是不幸的是當我們所尋求的向 量年代K-sparse,X最小化幾乎永遠不會發(fā)現(xiàn)它。我們得到相反的是nonsparseb X 的響在6.1節(jié)(更多內容見下文)。最小X標準重建:自從X規(guī)范(4)不能反映信號稀疏，一個合乎邏輯的選擇是 尋找翻譯零空間H sparsest向量:XXX可以證明，只有M = K + 1 iid高斯測量，這種優(yōu)化將恢復K-sparse信號高概率 6。但不幸的是解決(5)兩個數(shù)值不穩(wěn)定,是一個np完全問題，需要一個詳盡的X

13、X 枚舉所有可能的組合在年代的非零項的位置。最小X標準重建:壓縮傳感令人吃 驚的是，從XXX iid高斯測量我們可以完全reconstructK-sparse高概率向量和密切 近似可壓縮向量穩(wěn)定通過X優(yōu)化1、2XXXX這是一個凸優(yōu)化問題，方便減少線 性程序稱為基礎追求1、2的計算復雜度是O(N3)?？偠灾?，壓縮傳感數(shù)據(jù)采集系統(tǒng)由基于X的隨機測量線性規(guī)劃重建獲得X 緊隨其后。討論6, 1幾何解釋壓縮傳感的幾何問題RN幫助我們想象X重建成功,X重建失敗的原因。首 先,注意的所有K-sparse向量在RN是一個高度非線性的空間組成的所有 K-dimensional超平面與坐標軸一致(見圖2(a)。

14、因此，稀疏向量生活接近RN的坐 標軸。想象為什么X重建失敗，注意翻譯零空間H = N()+ s的維度(NM)和面向隨 機角由于矩陣X的隨機性。參見圖2(b)，但在實踐中注意,XXX，所以你需要推斷你 的直覺到高維度。(4)的Xminimizerb X點H接近原點。我們能找到這一點通過 炸毀一個超球面球(X),直到它觸及到h .由于隨機的方向,最接近pointbs將概率高 的生活遠離坐標軸,因此既不會少，也不會接近正確的答案。在X球X形成強烈的反差,XX球在圖2(c)是“尖”點對齊沿著坐標軸(和它成 為pointier隨著環(huán)境維度N)。因此，當我們炸毀X球，它會首先聯(lián)系翻譯零空間H 在靠近坐標軸

15、，這正是稀疏向量X所在地。6.2模擬信號雖然我們都集中在離散時間信號,壓縮傳感也適用于模擬信號x(t)可以僅使 用稀疏表示的K的N元素從一些持續(xù)或詞典我(t)倪=1。雖然每個我(t)(因此可 能大帶寬奈奎斯特率高)，信號x(t)只有K自由度，我們可以應用上面理論來衡量它 的速度低于奈奎斯特。實際模擬壓縮感知的一個例子系統(tǒng)一一一個所謂的“ analog-to-information ”轉換器-7 中給出了;有有趣連接8。圖2:(a)一個稀疏向量年代躺在K-dimensional超平面與RN的坐標軸從而接近軸。通過X(b)壓縮感知恢復最小化不找到正確的稀疏解年代翻譯零空 間(綠色超平面)，而是no

16、n-sparse向量X(c)有足夠的測量，通過X最小化并找到正 確的稀疏恢復解決方案。實際的例子考慮圖3的單像素”“實線壓數(shù)碼相機(a),直接獲得隨機線性測量沒有首先收 集N像素值9。這一事件lightfield對應于所需的圖像x不是集中到CCD或CMOS采樣數(shù)組而反射數(shù)字微鏡器件 (DMD)組成的一個數(shù)組的N小鏡子。(分布式監(jiān)測是發(fā)現(xiàn)在許多計算機投影儀和 投影電視。)反射的光通過第二個鏡頭收集起來，然后集中到一個光電二極管(單一 像素)。每個鏡子可以向獨立的光電二極管(對應于1)或消失從光電二極管(對應于一個0)。每個測量獲得的圖是如下:隨機數(shù)發(fā)生器(RNG)鏡 子在偽隨機取向模式0/1創(chuàng)建

17、測量向量X。光電二極管的電壓等于劉曉波,內部產 品X X和所需的圖像之間。這個過程是重復M次獲得所有的條目在y。圖3(b)和(c)說明一個目標對象和一個圖像X單像素相機拍攝的原型實線9 使用隨機測量比重構像素少約60%。在這里重建通過執(zhí)行總變差優(yōu)化1,這是在 小波域X重建密切相關。單像素，主要利用實線壓縮傳感的方法是，這款相機可以適應圖像波長困難或 昂貴的地方創(chuàng)建一個大型陣列的傳感器。它還可以獲得數(shù)據(jù)隨著時間的推移，使 視頻重建9。8.結論在這節(jié)課中,我們已經了解到獲得信號采樣并不是唯一的途徑。感興趣的信 號是可壓縮的或稀疏時,它可以更有效和流線型的采用隨機測量和優(yōu)化只為了獲 得我們需要的測量

18、。我們還了解到，重建我們的老朋友最小二乘我們失敗，我們需要看看其他口味的凸優(yōu)化線性規(guī)劃（參見4、10）?？箟簜鞲腥匀皇且粋€新興的領域, 保持開放的心態(tài)和許多有趣的研究問題。一個相當詳盡的參考/cs目 前的研究方向是可用的。lUJUi T-LI_fhikr:| | | | | I |n圖3:單像素，（a）實線壓縮傳感攝像頭。（b）傳統(tǒng)數(shù)碼相機圖像的足球球。（c）64X64黑白圖像相同的軟球（N = 4096像素）從M = 1600中恢復過來 隨機測量了 （a）。圖像的相機（b）和（c）不應該是一致的。參考文獻:E. Candes, J. Romberg, and T. Tao, “Robust

19、uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, vol. 52,no. 2, pp. 489-509, Feb. 2006.D. Donoho, “Compressed sensing, IEEE Trans. Inform. Theory, vol. 52, no. 4, pp. 1289-1306, April 2006.S. Mallat, A Wavelet Tour of Signa

20、l Processing. Academic Press, 1999.J. Tropp and A. C. Gilbert, “Signal recovery from partial information via orthogonal matching pursuit, April 2005,/_jtropp/papers/TG05-Signal-Recovery.pdf.R. G. Baraniuk, M. Davenport, R. DeVore, and M. B. Wakin, “The Johnson-Lindenstrauss lemma meets compressed se

21、nsing, 2006, /cs/jlcs-v03.pdf.D. Baron, M. B. Wakin, M. Duarte, S. Sarvotham, and R. G. Baraniuk, “Distributed compressed sensing, 2005, /cs/DCS112005.pdf.S. Kirolos, J. Laska, M. Wakin, M. Duarte, D. Baron, T. Ragheb, Y. Massoud, and R. G. Baraniuk, “Analog-to-information conversion via random demodulation, in IEEE Dallas Circuits and Systems Workshop, Oct. 2006.M. Vetterli, P. Marziliano, and T. Blu, “Sampling signals with finite rate of innovation, IEEE Trans. Signal Processing, vol. 50, no. 6, pp. 1417-1428, June