压缩感知-外文文献翻译.doc

毕业设计(论文)外文资料翻译

题 目: 基于压缩感知的信号重构算法研究
院系名称： 信息科学与工程学院
专业班级： 电信0702
指导教师： 教师职称：
学生姓名： 学 号：

附 件： 1.外文资料翻译译文；2.外文原文。
指导教师评语：

签名： 年 月 日

² 外文资料翻译译文
压缩采样
Emamnuel J. Candès
摘要：从频域数据中采集和重构图像的传统思想和方法遵循的是奈奎斯特定理这一基本原则。这一原则认为：为了重建图像，需要获取的傅里叶采样的数量必须匹配图像的预期分辨率，即图像的像素点数。本文介绍了一种名为“压缩采样”或“压缩感知”的新兴理论，该理论认为传统的观念是不正确的。或许令人吃惊的是，它有可能从远远小于图像/信号预期分辨率的若干采样中精确地重构原始图像或数据。
毫无疑问，压缩采样具有深远的意义。例如，它提出一种可能的新数据采集协议，能比传统认为所必须的传感器更少的情况下把模拟信息转化成数字形式。这个新的抽样理论可能会造成数据的采样和压缩过程同时进行。
在这个简短的概述中，我们提供一些有关这一新理论的关键数学见解，并且给出了一些压缩采样和其他领域的交叉，如统计学、信息论、编码理论以及理论计算科学。
关键词：压缩采样，稀疏，一致不确定性原理，不定线性方程组，最小L1范数，线性规划，信号恢复，纠错。
1. 引言
信号处理的一个中心原则是奈奎斯特/香农抽样定理:无差错的重构一个信号所需的采样数目取决于它的带宽——包含该信号有效频谱的最小间隔。在过去两年左右的时间里，出现了另一种“压缩采样”理论。这个理论表明超分辨信号和图像可以从远远少于通常所认为的必要的数据/测量尺寸中重构出来。本文的目的在于探究并提供一些有关这种新理论的关键数学见解。压缩采样吸引人的地方在于它与某些应用科学和工程诸如统计学、信息理论、编码理论、理论计算科学等领域有着显著的交叉和连接作用。我们将试着通过几个精选的例子来解释这些联系。
从广义的观点，更一般地说，稀疏性和可压缩性在许多科学领域发挥着并将继续发挥基础性的作用。稀疏性带来了有效估计；例如，由阈值分割或压缩算法获得的近似估计的质量取决于我们希望估计的信号的稀疏度。稀疏性带来了高效压缩；例如，一种变换编码器的精度取决于我们希望编码的信号的稀疏度[24]。稀疏性带来了降维和高效建模。这里的新颖之处在于稀疏性成了数据采集过程的核心，而且带来了高效的数据采集协议。
事实上，压缩采样提出了如何更经济地将模拟数据转换成压缩数字形式[20],[7]。这里的关键词是“经济地”。众所周知，因为典型的信号的结构特性，它们可以在没有太多感性损失的前提下被高效压缩。例如，现代的转换编码器如JPEG2000就是利用许多信号在某些固定基上的稀疏表示，这意味着编码器可以仅存储或传输少数的自适应选择转换系数而不是所有的信号样本。它的典型工作方式是获取一个完整的信号，计算一系列完整的变换系数，对最大的系数编码并丢弃所有其它的系数。对大量的数据采集然后进行压缩的过程是极其浪费的(你可以想一想，数码相机有数百万的成像传感器，但最终却只把照片的像素编码为几百kb大小)。这就提出了一个基本的问题：因为大多数信号是可压缩的，为什么当我们知道它的大部分数据将会被放弃时还要花这么大的努力获取所有的数据呢？有没有可能获取压缩形式的数据从而不需要丢弃任何东西呢？“压缩采样”，也称为“压缩感知”[20]表明这的确是有可能的。
本文绝不是一篇关于压缩采样的详尽的概述文献。这仅仅是作者自己在这一领域的作品和思想，其中也包括对别人作品的大量参考以及和这些作品相关的偶尔探讨。我们已经尽力把我们的思想组织成与早期发表的这一主题的论文相衔接的逻辑续接。在我们开始之前，我们想邀请感兴趣的读者也查阅一下Ronald Devore——他也在对此进行研究——对于该领域的一篇互补性调研文章[17](第5节)。
2. 欠抽样测量
考虑一个从线性测量y中重构一个向量的一般性问题，其中关于x和y的形式为
(2.1)
也就是说，我们通过测量对维向量ϕk∈RN的映射来获取未知信号的信息。我们感兴趣的是在“欠定”条件下，我们有比未知信号变量少的多的测量值。在无数的应用中都出现这种类型问题。例如在放射医学及生物医学成像中，人们对图像感兴趣部分收集到的测量数据要比对它无用像素的测量数据少得多。在宽带无线电频率信号分析中，由于当前在模/数转换器技术方面的局限性，你可能仅仅能在远低于奈奎斯特频率下获得一个信号。最后，基因表达的研究也提供了这样的例子。在此，人们会想从一组较少的特别是数百的观察值中推断出成千上万基因表达水平。
乍一看，求解欠定方程组似乎是不可能的，因为我们可以很容易的列举出它显然无法求解的例子。但是现在我们设想一个信号是可压缩的,也就是说它实质上由一些小于N的自由度决定的。例如，假设我们的信号是稀疏的，意味着它可以看成由一些固定基上的少数向量的叠加来准确或者精确地描述。然后，在这个前提下，问题就发生根本性的变化，使求解成为可能。事实上，通过求解一个简单凸优化问题来精确的或者有时准确的恢复信号是可能的。
2.1．非线性采样定理
我们最好先来考虑一个具体的例子。假设现在我们采集到了长度为N的离散信号的一套不完整的频率样值。(为了简化论述，我们考虑一个一维的典型问题。这个理论可以很容易的扩展到更高的维度。例如，我们可能对从欠抽样的傅里叶数据中重建二维或三维物体也同样感兴趣。) 我们的目标是在只给出傅里叶变换域的个样本条件下重建完整的信号f
(2.2)
式子中“可见的”频率是所有频率{ 0,…,N−1 }的一个子集(长为K)。磁共振成像的原理就是通过测量被选择的频率系数来感知一个物体，而且这一原理普遍应用于许多科学领域，包括天文学。在一般问题的表达式(2.1)中，传感矩阵是通过采样×的离散傅里叶变换变换矩阵的行获取的。
如果向量x中{i : xi 0}集的势少于或等于S，我们就说向量x是S-稀疏的。这样，Candès、Romberg和Tao[6]给出了几乎总能通过求解凸优化问题来完全恢复信号的公式()
(P1) (2.3)
定理2.1([6]) 假设是S-稀疏的，并且给出了频率均匀下随机抽样的K个傅里叶系数。假设观察值的数量服从
K ≥ C · S · log N. (2.4)
这样就能以极大的概率准确地重构。具体而言，如果在式(2.4)中常数C的形式是22(δ +1)，那么它的成功概率就超过了。
第一个结论是，我们可以仅仅通过测量任意设定下的频率系数就能够使信息不失真。第二个结论是，信号可以通过一个未设定任何关于非零数值的凸函数的最小化来准确地恢复，我们假设它们的位置和幅度都是事先完全未知的。
虽然这似乎是一个伟大的壮举，可人们仍会问它是否是最佳的，或者我们能否用更少的样本来恢复信号。答案是，一般来说，我们不能用更少的样本来重构S-稀疏信号。有很多例子证明，无论是什么情况，采取什么方法，为准确的重构信号所需的最少样本数必须约是S logN。因此，这个定理是苛刻的，而且最小范数几乎只有在有希望通过算法实现的时候才能得到。
读者一定很熟悉奈奎斯特/香农采样理论，我们可以将我们的结果用另一种表达形式与其建立简单的联系。通过转变上例中时间和频率的作用，我们可以把定理1重写为一个新的非线性采样定理。假设一个信号在频域范围内。如果是一个连续的集合，那么我们可以把作为的带宽。此外，如果集合是已知的，那么由传统的奈奎斯特/香农采样定理可知，信号可以从频域的等时间间隔的抽样中完美重构出来。重构可通过一个简单的sinc插植核进行线性插值获得。
现在，假设集合大小仍为，未知并且不一定是连续的。在这种情况下奈奎斯特/香农定理是无助的，我们只能假设这个连续的频率集合是个完整的空间，也就是说，准确的重构信号需要所有的N个时域采样。然而定理2.1却断定用少得多的样本是必然的。求解出(P1)就可以从约B logN倍的时域样本中完全恢复出信号。此外,这些样本没有必要精心挑选；几乎任何这种尺寸的样本集合都可以使用。因此我得到一个对奈奎斯特/香农定理的非线性模拟(这样描述是由于重建过程(P1)是非线性的)：我们可以选定任意且未知的频率集合B，从时域中任意选取约B logN个样本来重构信号。

外文原文