壓縮感知 外文文獻翻譯

《壓縮感知 外文文獻翻譯》由會員分享，可在線閱讀，更多相關《壓縮感知 外文文獻翻譯（9頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、?次*琴 畢業(yè)設計（論文）外文 資料翻譯 題 目: 基于壓縮感知的信號重構算法研究 院系名稱： 信息科學與工程學院 專業(yè)班級： 電信0702 指導教師： 教師職稱： 學生姓名：學 號： 外文資料翻譯譯文 壓縮采樣 Emamnuel J. Candes 摘要：從頻域數(shù)據(jù)中采集和重構圖像的傳統(tǒng)思想和方法遵循的是奈奎斯特定理這一 基本原則。這一原則認為：為了重建圖像，需要獲取的傅里葉采樣的數(shù)量必須匹配 圖像的預期分辨率，即圖像的像素點數(shù)。本文介紹了一種名為“壓縮采樣”或“壓 縮感知”的新興理論，該理論認為傳統(tǒng)的觀念是不正確的。或許令人吃驚的是，它 有可能從遠遠小于

2、圖像/信號預期分辨率的若干采樣中精確地重構原始圖像或數(shù)據(jù)。 毫無疑問，壓縮采樣具有深遠的意義。例如，它提出一種可能的新數(shù)據(jù)采集協(xié) 議，能比傳統(tǒng)認為所必須的傳感器更少的情況下把模擬信息轉化成數(shù)字形式。這個 新的抽樣理論可能會造成數(shù)據(jù)的采樣和壓縮過程同時進行。 在這個簡短的概述中，我們提供一些有關這一新理論的關鍵數(shù)學見解，并且給 出了一些壓縮采樣和其他領域的交叉，如統(tǒng)計學、信息論、編碼理論以及理論計算 科學。 關鍵詞：壓縮采樣，稀疏，一致不確定性原理，不定線性方程組，最小”范數(shù)，線 性規(guī)劃，信號恢復，糾錯。 1.引言 信號處理的一個中心原則是奈奎斯特/香農(nóng)抽樣定理：無差錯的重構一個信號

3、所需的采樣數(shù)目取決于它的帶寬一一包含該信號有效頻譜的最小間隔。在過去兩年 左右的時間里，出現(xiàn)了另一種“壓縮采樣”理論。這個理論表明超分辨信號和圖像 可以從遠遠少于通常所認為的必要的數(shù)據(jù)/測量尺寸中重構出來。本文的目的在于 探究并提供一些有關這種新理論的關鍵數(shù)學見解。壓縮采樣吸引人的地方在于它與 某些應用科學和工程諸如統(tǒng)計學、信息理論、編碼理論、理論計算科學等領域有著 顯著的交叉和連接作用。我們將試著通過幾個精選的例子來解釋這些聯(lián)系。 從廣義的觀點，更一般地說，稀疏性和可壓縮性在許多科學領域發(fā)揮著并將繼 續(xù)發(fā)揮基礎性的作用。稀疏性帶來了有效估計；例如，由閾值分割或壓縮算法獲得 的近似估計的質(zhì)量

4、取決于我們希望估計的信號的稀疏度。稀疏性帶來了高效壓縮； 例如，一種變換編碼器的精度取決于我們希望編碼的信號的稀疏度［24］。稀疏性帶 來了降維和高效建模。這里的新穎之處在于稀疏性成了數(shù)據(jù)采集過程的核心，而且 帶來了高效的數(shù)據(jù)采集協(xié)議。 事實上，壓縮采樣提出了如何更經(jīng)濟地將模擬數(shù)據(jù)轉換成壓縮數(shù)字形式 [20],[7]。這里的關鍵詞是“經(jīng)濟地”。眾所周知，因為典型的信號的結構特性，它 們可以在沒有太多感性損失的前提下被高效壓縮。例如，現(xiàn)代的轉換編碼器如 JPEG2000就是利用許多信號在某些固定基上的稀疏表示，這意味著編碼器可以僅存 儲或傳輸少數(shù)的自適應選擇轉換系數(shù)而不是所有的信號樣本。

5、它的典型工作方式是 獲取一個完整的信號，計算一系列完整的變換系數(shù)，對最大的系數(shù)編碼并丟棄所有 其它的系數(shù)。對大量的數(shù)據(jù)采集然后進行壓縮的過程是極其浪費的（你可以想一想， 數(shù)碼相機有數(shù)百萬的成像傳感器，但最終卻只把照片的像素編碼為幾百炒大?。?。 這就提出了一個基本的問題：因為大多數(shù)信號是可壓縮的，為什么當我們知道它的 大部分數(shù)據(jù)將會被放棄時還要花這么大的努力獲取所有的數(shù)據(jù)呢？有沒有可能獲 取壓縮形式的數(shù)據(jù)從而不需要丟棄任何東西呢？ “壓縮采樣”，也稱為“壓縮感知” [20]表明這的確是有可能的。 本文絕不是一篇關于壓縮采樣的詳盡的概述文獻。這僅僅是作者自己在這一領 域的作品和思想，其中也包括對

6、別人作品的大量參考以及和這些作品相關的偶爾探 討。我們已經(jīng)盡力把我們的思想組織成與早期發(fā)表的這一主題的論文相銜接的邏輯 續(xù)接。在我們開始之前，我們想邀請感興趣的讀者也查閱一 TRonald Devore——他 也在對此進行研究——對于該領域的一篇互補性調(diào)研文章[17]（第5節(jié)）。 2.欠抽樣測量 考慮一個從線性測量y中重構一個向量x e RN的一般性問題，其中關于x和y的 形式為 > =（x,中），k = 1, ,K, or y = Ox （2.1） 也就是說，我們通過測量X對K維向量k€RN的映射來獲取未知信號的信息。 ? ? ? 我們感興趣的是在“欠定”條件K口 N下，我們有比未

7、知信號變量少的多的測量值。 在無數(shù)的應用中都出現(xiàn)這種類型問題。例如在放射醫(yī)學及生物醫(yī)學成像中，人們對 圖像感興趣部分收集到的測量數(shù)據(jù)要比對它無用像素的測量數(shù)據(jù)少得多。在寬帶無 線電頻率信號分析中，由于當前在模/數(shù)轉換器技術方面的局限性，你可能僅僅能 在遠低于奈奎斯特頻率下獲得一個信號。最后，基因表達的研究也提供了這樣的例 子。在此，人們會想從一組較少的特別是數(shù)百的觀察值中推斷出成千上萬基因表達 水平。 乍一看，求解欠定方程組似乎是不可能的，因為我們可以很容易的列舉出它顯 然無法求解的例子。但是現(xiàn)在我們設想一個信號X是可壓縮的,也就是說它實質(zhì)上由 一些小于N的自由度決定的。例如，假設我們的信

8、號是稀疏的，意味著它可以看成 由一些固定基上的少數(shù)向量的疊加來準確或者精確地描述。然后，在這個前提下， 問題就發(fā)生根本性的變化，使求解成為可能。事實上，通過求解一個簡單凸優(yōu)化問 題來精確的或者有時準確的恢復信號是可能的。 2.1.非線性采樣定理 我們最好先來考慮一個具體的例子。假設現(xiàn)在我們采集到了長度為N的離散信 號x的一套不完整的頻率樣值。(為了簡化論述，我們考慮一個一維的典型問題。這 個理論可以很容易的擴展到更高的維度。例如，我們可能對從欠抽樣的傅里葉數(shù)據(jù) 中重建二維或三維物體也同樣感興趣。)我們的目標是在只給出傅里葉變換域的k 個樣本條件下重建完整的信號f 1 N -1 (2.2

9、) =「= ￡ X e - j 2 歡 / N JN t t=0 式子中“可見的”頻率wk是所有頻率｛ 0,…,N-1 ｝的一個子集Q (長為K)。磁 共振成像的原理就是通過測量被選擇的頻率系數(shù)來感知一個物體，而且這一原理普 遍應用于許多科學領域，包括天文學。在一般問題的表達式(2.1)中，傳感矩陣中是 通過采樣N X N的離散傅里葉變換變換矩陣的k行獲取的。 如果向量x中｛,?: X’豐0｝集的勢少于或等于S，我們就說向量x是S-稀疏的。這樣， Candes> Romberg和Tao[6]給出了幾乎總能通過求解凸優(yōu)化問題來完全恢復信號的 公式(風廣^ \|xj) (P1) min

10、|| x || ①x = y (2.3) XeRN 1 定理2.1([6])假設x是S-稀疏的，并且給出了頻率均勻下隨機抽樣的K個傅里 葉系數(shù)。假設觀察值的數(shù)量服從 K > C - S ? log N. (2.4) 這樣就能以極大的概率準確地重構x。具體而言，如果在式(2.4)中常數(shù)C的形式 是22( ^+1),那么它的成功概率就超過了 1 -O(N書)。 第一個結論是，我們可以僅僅通過測量任意設定K下的頻率系數(shù)就能夠使信息 不失真。第二個結論是，信號x可以通過一個未設定任何關于x非零數(shù)值的凸函數(shù) 的最小化來準確地恢復，我們假設它們的位置和幅度都是事先完全未知的。 雖然這似乎是一

11、個偉大的壯舉，可人們?nèi)詴査欠袷亲罴训?，或者我們能?用更少的樣本來恢復信號。答案是，一般來說，我們不能用更少的樣本來重構S-稀 疏信號。有很多例子證明，無論是什么情況，采取什么方法，為準確的重構信號所 需的最少樣本數(shù)必須約是S logN。因此，這個定理是苛刻的，而且最小/］范數(shù)幾乎 只有在有希望通過算法實現(xiàn)的時候才能得到。 讀者一定很熟悉奈奎斯特/香農(nóng)采樣理論，我們可以將我們的結果用另一種表 達形式與其建立簡單的聯(lián)系。通過轉變上例中時間和頻率的作用，我們可以把定理 1重寫為一個新的非線性采樣定理。假設一個信號在頻域范圍B = |。|內(nèi)。如果。是 一個連續(xù)的集合，那么我們可以把B作為x的帶

12、寬。此外，如果集合。是已知的， 那么由傳統(tǒng)的奈奎斯特/香農(nóng)采樣定理可知，信號x可以從頻域B的等時間間隔的抽 樣中完美重構出來。重構可通過一個簡單的sinc插植核進行線性插值獲得。 現(xiàn)在，假設集合。大小仍為B，未知并且不一定是連續(xù)的。在這種情況下奈奎 斯特/香農(nóng)定理是無助的，我們只能假設這個連續(xù)的頻率集合是個完整的空間，也 就是說，準確的重構信號需要所有的N個時域采樣。然而定理2.1卻斷定用少得多的 樣本是必然的。求解出(P1)就可以從約B logN倍的時域樣本中完全恢復出信號x。 此外，這些樣本沒有必要精心挑選；幾乎任何這種尺寸的樣本集合都可以使用。因 此我得到一個對奈奎斯特/香農(nóng)定理的非線

13、性模擬(這樣描述是由于重建過程(P1) 是非線性的)：我們可以選定任意且未知的頻率集合B，從時域中任意選取約B logN 個樣本來重構信號。 外文原文 Compressive sampling Emamnuel J. Candes* Abstract. Conventional wisdom and common practice in acquisition and reconstruction of images from frequency data follow the basic principle of the Nyquist density sampling theory

14、. This principle states that to reconstruct an image, the number of Fourier samples we need to acquire must match the desired resolution of the image, the number of pixels in the image. This paper surveys an emerging theory which goes by the name of ^compressive sampling" or ^compressed sensing," an

15、d which says that this conventional wisdom is inaccurate^ Perhaps surprisingly, it is possible to reconstruct images or signals of scientific interest accurately and sometimes even exactly from a number of samples which is far smaller than the desired resolution of the iniage/signal, e.g< the number

16、 of pixels in the image. It is believed that compressive sampling has far reaching implications. For example, it suggests the possibility of new data acquisition protocols that translate analog information into digital form with fewer sensors than what was considered necessary. This new sampling th

17、eory may come to underlie procedures for sampling and compressing data simultaneously. In this short survey, we provide some of the key niathematical insights underlying this new theory, and explain some of the interactions between compressive sampling and other fields such as statistics, informati

18、on theory, coding theory, and theoretical computer science. Mathematics Subject Classification (2000). Primary 00A69,41 -02,68P30; Secondary 62C65. Keywords. Compressive sampling, sparsity, uniform uncertainty principle, underdertennined systems of linear equations, -minimization, linear programmi

19、ng, signal recovery, error correction. 1. Introduction One of the central tenets of signal processing is the Nyquist/Shannon sampling theory: the number of samples needed to reconstruct a signal without error is dictated by its bandwidth - the length of the shortest interval which contains the su

20、pport of the spectrum of the signal under study. In the last two years or so, an alternative theory of "compressive sampling" has emerged which shows that super-resolved signals and images can be reconstructed from far fewer data/measurements than what is usually considered necessary. The purpose of

21、 this paper is to survey and provide some of the key mathematical insights underlying this new theory. An enchanting aspect of compressive sampling it that it has significant interactions and bearings on some fields in the applied sciences and engineering such as statistics, information theory, codi

22、ng *The author is partially supported by an NSF grant CCF-515362. ftoceedings of the International Congress of Mathematicians, Madrid, Spain, 2006 ? 2006 European Mathematical Society theory, theoretical computer science, and others as well. We will try to explain these connections via a few sele

23、cted examples. From a general viewpoint, sparsity and, more generally, compressibility has played and continues to play a fundamental role in many fields of science. Sparsity leads to efficient estimations; for example, the quality of estimation by thresholding or shrinkage algorithms depends on t

24、he sparsity of the signal we wish to estimate. Sparsity leads to efficient compression; for example, the precision of a transform coder depends on the sparsity of the signal we wish to encode [24], Sparsity leads to dimensionality reduction and efficient modeling. The novelty here is that sparsity h

25、as bearings on the data acquisition process itself, and leads to efficient data acquisition protocols. In fact, compressive sampling suggests ways to economically translate analog data into already compressed digital form |20], |7|. The key word here is "economically.** Everybody knows that because

26、 typical signals have some structure, they can be compressed efficiently without much perceptual loss. For instance, modern transform coders such as JPEG2000 exploit the fact that many signals have a sparse representation in a fixed basis, meaning that one can store or transmit only a small number

27、 of adaptively chosen transform coefficients rather than all the signal samples. The way this typically works is that one acquires the full signal, computes the complete set of transform coefficients, encode the largest coefficients and discard all the others. This process of massive data acquisitio

28、n followed by compression is extremely wasteful (one can think about a digital camera which has millions of imaging sensors, the pixels, but eventually encodes the picture on a few hundred kilobytes). This raises a fundamental question: because most signals are compressible, why spend so much effor

29、t acquiring all the data when we know that most of it will be discarded? Wouldn't it be possible to acquire the data in already compressed form so that one does not need to throw away anything? "Compressive sampling" also known as "compressed sensing" |20] shows that this is indeed possible. This p

30、aper is by no means an exhaustive survey of the literature on compressive sampling. Rather this is merely an account of the author's own work and thinking in this area which also includes a fairly large number of references to other people's work and occasionally discusses connections with these wor

31、ks. We have done our best to organize the ideas into a logical progression starting with the early papers which launched this subject. Before we begin, we would like to invite the interested reader to also check the article 117] by Ronald DeVore - also in these proceedings - for a complementary surv

32、ey of the field (Section 5). 2. Undersampled measurements Consider the general problem of reconstructing a vector x € RA，from linear measurements y about x of the form (2,1) yk = {x, (pk), k = , K, or y = x. Compressive sampling 3 That is, we acquire information about the unknown signal by

33、 sensing x against K vectors 例 W 呻. We are interested in the "underdetermined” case K《N, where we have many fewer measurements than unknown signal values. Problems of this type arise in a countless number of applications. In radiology and biomedical imaging for instance, one is typically able to col

34、lect far fewer measurements about an image of interest than the number of unknown pixels. In wideband radio frequency signal analysis, one may only be able to acquire a signal at a rate which is far lower than the Nyquist rate because of current limitations in Analog-to-Digital Converter technology.

35、 Finally, gene expression studies also provide examples of this kind. Here, one would like to infer the gene expression level of thousands of genes - that is, the dimension N of the vector x is in the thousands - from a low number of observations, typically in the tens. At first glance, solving the

36、 underdertermined system of equations appears hopeless, as it is easy to make up examples for which it clearly cannot be done. But suppose now that the signal x is compressible, meaning that it essentially depends on a number of degrees of freedom which is smaller than N. For instance, suppose our s

37、ignal is sparse in the sense that it can be written either exactly or accurately as a superposition of a small number of vectors in some fixed basis. Then this premise radically changes the problem, making the search for solutions feasible. In fact, accurate and sometimes exact recovery is possible

38、by solving a simple convex optimization problem. 2.1. A nonlinear sampling theorem. It might be best to consider a concrete example first. Suppose here that one collects an incomplete set of frequency samples of a discrete signal x of length N. (To ease the exposition, we consider a model problem i

39、n one dimension. The theory extends easily to higher dimensions. For instance, we could be equally interested in the reconstruction of 2- or 3-dimensional objects from undersampled Fourier data.) The goal is to reconstruct the full signal f given only K samples in the Fourier domain 1 N-\ 咒=方匚為廠眼如

40、* (2.2) where the 'visible'frequencies ①上 are a subset Q (of size K)ofthesetofall frequencies {0,..., N — 1}. Sensing an object by measuring selected frequency coefficients is the principle underlying Magnetic Resonance Imaging, and is common in many fields of science, including Astrophysics. In th

41、e language of the general problem (2.1), the sensing matrix is obtained by sampling K rows of the N by N discrete Fourier transform matrix. We will say that a vector x is S -sparse if its support {/ : x, 0} is of cardinality less or equal toS, Then Cand^s, Romberg and Tao |6] showed that one co

42、uld almost always recover the signal x exactly by solving the convex program1 (||%||^ := ￡；=] |i( |) (Pi) min ||5||幻 subject to ^>.r = y. (2.3) (Pj) can even be recast as a linear program [3], [15]. Theorem 2.1 ([6]). Assume that x is S-sparse and that we are given K Fourier coefficients with fre

43、quencies selected uniformly at random. Suppose that the number of observations obeys K >C S ■ logN. (2,4) Then minimizing t [ reconstructs x exactly with overwhelming probability. In details, if the constant C is of the fonn 22(6 + 1) in (2.4), then the probability of success exceeds 1 — O(N~S，).

44、 The first conclusion is that one suffers no information loss by measuring just about any set of K frequency coefficients. The second is that the signal .r can be exactly recovered by minimizing a convex functional which does not assume any knowledge about the number of nonzero coordinates of x, the

45、ir locations, and their amplitudes which we assume are all completely unknown a priori. While this seems to be a great feat, one could still ask whether this is optimal, or whether one could do with even fewer samples. The answer is that in general, we cannot reconstruct S-sparse signals with fewer

46、 samples. There are examples for which the iiiinimuin number of samples needed for exact reconstruction by any method, no matter how intractable, must be about S log N. Hence, the theorem is tight and ￡)-minimization succeeds nearly as soon as there is any hope to succeed by any algorithm. The read

47、er is certainly familiar with the Nyquist/Shannon sampling theory and one can reformulate our result to establish simple connections. By reversing the roles of time and frequency in the above example, we can recast Theorem 1 as a new nonlinear sampling theorem. Suppose that a signal x has support Q

48、in the frequency domain with B = |Q|. If Q is a connected set, we can think of B as the bandwidth of x. If in addition the set Q is known, then the classical Nyquist/Shannon sampling theorem states that x can be reconstructed perfectly from B equally spaced samples in the time domain2. The reconstru

49、ction is simply a linear interpolation with a "sine” kernel. Now suppose that the set Q, still of size B, is unknown and not necessarily connected. in this situation, the Nyquist/Shannon theory is unhelpful - we can only assume that the connected frequency support is the entire domain suggesting t

50、hat all N time-domain samples are needed for exact reconstruction. However, Theorem 2.1 asserts that far fewer samples are necessary. Solving (Pi) will recover x perfectly from about B log N time samples. What is more, these samples do not have to be carefully chosen; almost any sample set of this

51、size will work. Thus we have a nonlinear analog (described as such since the reconstruction procedure (P[) is nonlinear) to Nyquist/Shannon: we can reconstruct a signal with arbitrary and unknown frequency support of size B from about B log N arbitrarily chosen samples in the time domain. Finally, we would like to emphasize that our Fourier sampling theorem is only a special instance of much more general statements. As a matter of fact, the results 2Fbr the sake of comenience, we make the assumption lhat lhe bandwidth B divides lhe signal length N evenly;