壓縮感知 外文文獻(xiàn)翻譯

.畢業(yè)設(shè)計(jì)(論文)外文資料翻譯題 目: 基于壓縮感知的信號(hào)重構(gòu)算法研究 院系名稱： 信息科學(xué)與工程學(xué)院 專業(yè)班級(jí)： 電信0702 指導(dǎo)教師： 教師職稱： 學(xué)生姓名： 學(xué) 號(hào)： 附 件： 1.外文資料翻譯譯文；2.外文原文。 指導(dǎo)教師評(píng)語： 簽名： 年 月 日 外文資料翻譯譯文壓縮采樣Emamnuel J. Cands摘要：從頻域數(shù)據(jù)中采集和重構(gòu)圖像的傳統(tǒng)思想和方法遵循的是奈奎斯特定理這一基本原則。這一原則認(rèn)為：為了重建圖像，需要獲取的傅里葉采樣的數(shù)量必須匹配圖像的預(yù)期分辨率，即圖像的像素點(diǎn)數(shù)。本文介紹了一種名為“壓縮采樣”或“壓縮感知”的新興理論，該理論認(rèn)為傳統(tǒng)的觀念是不正確的?；蛟S令人吃驚的是，它有可能從遠(yuǎn)遠(yuǎn)小于圖像/信號(hào)預(yù)期分辨率的若干采樣中精確地重構(gòu)原始圖像或數(shù)據(jù)。毫無疑問，壓縮采樣具有深遠(yuǎn)的意義。例如，它提出一種可能的新數(shù)據(jù)采集協(xié)議，能比傳統(tǒng)認(rèn)為所必須的傳感器更少的情況下把模擬信息轉(zhuǎn)化成數(shù)字形式。這個(gè)新的抽樣理論可能會(huì)造成數(shù)據(jù)的采樣和壓縮過程同時(shí)進(jìn)行。在這個(gè)簡(jiǎn)短的概述中，我們提供一些有關(guān)這一新理論的關(guān)鍵數(shù)學(xué)見解，并且給出了一些壓縮采樣和其他領(lǐng)域的交叉，如統(tǒng)計(jì)學(xué)、信息論、編碼理論以及理論計(jì)算科學(xué)。關(guān)鍵詞：壓縮采樣，稀疏，一致不確定性原理，不定線性方程組，最小L1范數(shù)，線性規(guī)劃，信號(hào)恢復(fù)，糾錯(cuò)。1. 引言信號(hào)處理的一個(gè)中心原則是奈奎斯特/香農(nóng)抽樣定理:無差錯(cuò)的重構(gòu)一個(gè)信號(hào)所需的采樣數(shù)目取決于它的帶寬包含該信號(hào)有效頻譜的最小間隔。在過去兩年左右的時(shí)間里，出現(xiàn)了另一種“壓縮采樣”理論。這個(gè)理論表明超分辨信號(hào)和圖像可以從遠(yuǎn)遠(yuǎn)少于通常所認(rèn)為的必要的數(shù)據(jù)/測(cè)量尺寸中重構(gòu)出來。本文的目的在于探究并提供一些有關(guān)這種新理論的關(guān)鍵數(shù)學(xué)見解。壓縮采樣吸引人的地方在于它與某些應(yīng)用科學(xué)和工程諸如統(tǒng)計(jì)學(xué)、信息理論、編碼理論、理論計(jì)算科學(xué)等領(lǐng)域有著顯著的交叉和連接作用。我們將試著通過幾個(gè)精選的例子來解釋這些聯(lián)系。從廣義的觀點(diǎn)，更一般地說，稀疏性和可壓縮性在許多科學(xué)領(lǐng)域發(fā)揮著并將繼續(xù)發(fā)揮基礎(chǔ)性的作用。稀疏性帶來了有效估計(jì)；例如，由閾值分割或壓縮算法獲得的近似估計(jì)的質(zhì)量取決于我們希望估計(jì)的信號(hào)的稀疏度。稀疏性帶來了高效壓縮；例如，一種變換編碼器的精度取決于我們希望編碼的信號(hào)的稀疏度24。稀疏性帶來了降維和高效建模。這里的新穎之處在于稀疏性成了數(shù)據(jù)采集過程的核心，而且?guī)砹烁咝У臄?shù)據(jù)采集協(xié)議。事實(shí)上，壓縮采樣提出了如何更經(jīng)濟(jì)地將模擬數(shù)據(jù)轉(zhuǎn)換成壓縮數(shù)字形式20,7。這里的關(guān)鍵詞是“經(jīng)濟(jì)地”。眾所周知，因?yàn)榈湫偷男盘?hào)的結(jié)構(gòu)特性，它們可以在沒有太多感性損失的前提下被高效壓縮。例如，現(xiàn)代的轉(zhuǎn)換編碼器如JPEG2000就是利用許多信號(hào)在某些固定基上的稀疏表示，這意味著編碼器可以僅存儲(chǔ)或傳輸少數(shù)的自適應(yīng)選擇轉(zhuǎn)換系數(shù)而不是所有的信號(hào)樣本。它的典型工作方式是獲取一個(gè)完整的信號(hào)，計(jì)算一系列完整的變換系數(shù)，對(duì)最大的系數(shù)編碼并丟棄所有其它的系數(shù)。對(duì)大量的數(shù)據(jù)采集然后進(jìn)行壓縮的過程是極其浪費(fèi)的(你可以想一想，數(shù)碼相機(jī)有數(shù)百萬的成像傳感器，但最終卻只把照片的像素編碼為幾百kb大小)。這就提出了一個(gè)基本的問題：因?yàn)榇蠖鄶?shù)信號(hào)是可壓縮的，為什么當(dāng)我們知道它的大部分?jǐn)?shù)據(jù)將會(huì)被放棄時(shí)還要花這么大的努力獲取所有的數(shù)據(jù)呢？有沒有可能獲取壓縮形式的數(shù)據(jù)從而不需要丟棄任何東西呢？“壓縮采樣”，也稱為“壓縮感知”20表明這的確是有可能的。本文絕不是一篇關(guān)于壓縮采樣的詳盡的概述文獻(xiàn)。這僅僅是作者自己在這一領(lǐng)域的作品和思想，其中也包括對(duì)別人作品的大量參考以及和這些作品相關(guān)的偶爾探討。我們已經(jīng)盡力把我們的思想組織成與早期發(fā)表的這一主題的論文相銜接的邏輯續(xù)接。在我們開始之前，我們想邀請(qǐng)感興趣的讀者也查閱一下Ronald Devore他也在對(duì)此進(jìn)行研究對(duì)于該領(lǐng)域的一篇互補(bǔ)性調(diào)研文章17(第5節(jié))。2. 欠抽樣測(cè)量考慮一個(gè)從線性測(cè)量y中重構(gòu)一個(gè)向量的一般性問題，其中關(guān)于x和y的形式為 (2.1)也就是說，我們通過測(cè)量對(duì)維向量kRN的映射來獲取未知信號(hào)的信息。我們感興趣的是在“欠定”條件下，我們有比未知信號(hào)變量少的多的測(cè)量值。在無數(shù)的應(yīng)用中都出現(xiàn)這種類型問題。例如在放射醫(yī)學(xué)及生物醫(yī)學(xué)成像中，人們對(duì)圖像感興趣部分收集到的測(cè)量數(shù)據(jù)要比對(duì)它無用像素的測(cè)量數(shù)據(jù)少得多。在寬帶無線電頻率信號(hào)分析中，由于當(dāng)前在模/數(shù)轉(zhuǎn)換器技術(shù)方面的局限性，你可能僅僅能在遠(yuǎn)低于奈奎斯特頻率下獲得一個(gè)信號(hào)。最后，基因表達(dá)的研究也提供了這樣的例子。在此，人們會(huì)想從一組較少的特別是數(shù)百的觀察值中推斷出成千上萬基因表達(dá)水平。乍一看，求解欠定方程組似乎是不可能的，因?yàn)槲覀兛梢院苋菀椎牧信e出它顯然無法求解的例子。但是現(xiàn)在我們?cè)O(shè)想一個(gè)信號(hào)是可壓縮的,也就是說它實(shí)質(zhì)上由一些小于N的自由度決定的。例如，假設(shè)我們的信號(hào)是稀疏的，意味著它可以看成由一些固定基上的少數(shù)向量的疊加來準(zhǔn)確或者精確地描述。然后，在這個(gè)前提下，問題就發(fā)生根本性的變化，使求解成為可能。事實(shí)上，通過求解一個(gè)簡(jiǎn)單凸優(yōu)化問題來精確的或者有時(shí)準(zhǔn)確的恢復(fù)信號(hào)是可能的。2.1非線性采樣定理我們最好先來考慮一個(gè)具體的例子。假設(shè)現(xiàn)在我們采集到了長(zhǎng)度為N的離散信號(hào)的一套不完整的頻率樣值。(為了簡(jiǎn)化論述，我們考慮一個(gè)一維的典型問題。這個(gè)理論可以很容易的擴(kuò)展到更高的維度。例如，我們可能對(duì)從欠抽樣的傅里葉數(shù)據(jù)中重建二維或三維物體也同樣感興趣。) 我們的目標(biāo)是在只給出傅里葉變換域的個(gè)樣本條件下重建完整的信號(hào)f (2.2)式子中“可見的”頻率是所有頻率 0,N1 的一個(gè)子集(長(zhǎng)為K)。磁共振成像的原理就是通過測(cè)量被選擇的頻率系數(shù)來感知一個(gè)物體，而且這一原理普遍應(yīng)用于許多科學(xué)領(lǐng)域，包括天文學(xué)。在一般問題的表達(dá)式(2.1)中，傳感矩陣是通過采樣的離散傅里葉變換變換矩陣的行獲取的。如果向量x中i : xi 0集的勢(shì)少于或等于S，我們就說向量x是S-稀疏的。這樣，Cands、Romberg和Tao6給出了幾乎總能通過求解凸優(yōu)化問題來完全恢復(fù)信號(hào)的公式() (P1) (2.3)定理2.1(6) 假設(shè)是S-稀疏的，并且給出了頻率均勻下隨機(jī)抽樣的K個(gè)傅里葉系數(shù)。假設(shè)觀察值的數(shù)量服從K C S log N. (2.4)這樣就能以極大的概率準(zhǔn)確地重構(gòu)。具體而言，如果在式(2.4)中常數(shù)C的形式是22( +1)，那么它的成功概率就超過了。第一個(gè)結(jié)論是，我們可以僅僅通過測(cè)量任意設(shè)定下的頻率系數(shù)就能夠使信息不失真。第二個(gè)結(jié)論是，信號(hào)可以通過一個(gè)未設(shè)定任何關(guān)于非零數(shù)值的凸函數(shù)的最小化來準(zhǔn)確地恢復(fù)，我們假設(shè)它們的位置和幅度都是事先完全未知的。雖然這似乎是一個(gè)偉大的壯舉，可人們?nèi)詴?huì)問它是否是最佳的，或者我們能否用更少的樣本來恢復(fù)信號(hào)。答案是，一般來說，我們不能用更少的樣本來重構(gòu)S-稀疏信號(hào)。有很多例子證明，無論是什么情況，采取什么方法，為準(zhǔn)確的重構(gòu)信號(hào)所需的最少樣本數(shù)必須約是S logN。因此，這個(gè)定理是苛刻的，而且最小范數(shù)幾乎只有在有希望通過算法實(shí)現(xiàn)的時(shí)候才能得到。讀者一定很熟悉奈奎斯特/香農(nóng)采樣理論，我們可以將我們的結(jié)果用另一種表達(dá)形式與其建立簡(jiǎn)單的聯(lián)系。通過轉(zhuǎn)變上例中時(shí)間和頻率的作用，我們可以把定理1重寫為一個(gè)新的非線性采樣定理。假設(shè)一個(gè)信號(hào)在頻域范圍內(nèi)。如果是一個(gè)連續(xù)的集合，那么我們可以把作為的帶寬。此外，如果集合是已知的，那么由傳統(tǒng)的奈奎斯特/香農(nóng)采樣定理可知，信號(hào)可以從頻域的等時(shí)間間隔的抽樣中完美重構(gòu)出來。重構(gòu)可通過一個(gè)簡(jiǎn)單的sinc插植核進(jìn)行線性插值獲得?，F(xiàn)在，假設(shè)集合大小仍為，未知并且不一定是連續(xù)的。在這種情況下奈奎斯特/香農(nóng)定理是無助的，我們只能假設(shè)這個(gè)連續(xù)的頻率集合是個(gè)完整的空間，也就是說，準(zhǔn)確的重構(gòu)信號(hào)需要所有的N個(gè)時(shí)域采樣。然而定理2.1卻斷定用少得多的樣本是必然的。求解出(P1)就可以從約B logN倍的時(shí)域樣本中完全恢復(fù)出信號(hào)。此外,這些樣本沒有必要精心挑選；幾乎任何這種尺寸的樣本集合都可以使用。因此我得到一個(gè)對(duì)奈奎斯特/香農(nóng)定理的非線性模擬(這樣描述是由于重建過程(P1)是非線性的)：我們可以選定任意且未知的頻率集合B，從時(shí)域中任意選取約B logN個(gè)樣本來重構(gòu)信號(hào)。外文原文.