压缩采样介绍.doc

压缩采样介绍一个与传统数据采集不同的传感、采样范例Emmanuel J. Cands and Michael B. WakinIEEE信号处理杂志 2008年3月对信号和图像采样的传统方法遵循著名的香农定理：采样速率必须至少是当前信号最大频率的两倍（也称奈奎斯特速率）。事实上，这个定理几乎是所有信号采集方式的基础，被大规模应用在消费性音频视频电子设备、医学成像设备、收音机等等。（对于某些信号，例如并非是原始的天然影像，采样率就不是由香农定理所规定，而是取决于需要的空间或时间分辨率。然而，这些系统经常在采样前使用反锯齿低通滤波器保持信号，使得香农定理扮演一个幕后的角色。）例如在数据转换领域，标准模数转换器（ADC）技术使用量化香农定理：信号一律以大于或等于奈奎斯特速率来采样。这篇论文研究了压缩采样的理论，该理论亦被称为压缩传感或CS，是一项新颖的与传统数据采集不同的传感、采样技术。CS理论声称可以比传统方法使用更少的采样信号和测量来恢复特定信号和图形。为了实现这一点，CS依靠两个准则：稀疏性，不连贯性。u 稀疏性，表示连续时间信号的信息率可能比由带宽决定的还要小，或者离散时间信号自由度远小于其有限的长度。更准确的说，CS方法发现许多自然信号是十分稀疏并可压缩的，当用适当的基础表述时，他们就能有简明的表达。u 传感形式不连贯延续了时间和频率的二元性，并表明目标在有一个稀少的特征并一定会在他们已得的范围内扩展，正如时域里面的狄拉克或冲击信号在频域也可展开表示。另外，不连贯表明它与信号特征不同，采样、传感的波形在有一个非常密集的表示。最重要的是我们可以设计有效的传感、采样规则，来获取有用的信息并将其嵌入到稀疏的信号中，加入到一小段数据中。这些规则仅十分简单的要求把信号同一些固定的波形相关联，这些波形也都没什么根据。关于这些采样规则，最不同寻常的是它们可以使用一个传感器，从稀疏的信号中高效的获取信息，并且也不需要分析这些信号。甚至它还能使用数字化最优方法，仅依靠一小段获得的数据来重建全部信号。换句话说，CS是一种非常简单并高效的数据获取方法，它采用信号独立方式，采样率低，依靠看起来不完整的一系列测量，经过计算来重建信号。我们这篇论文意图概述13中出现的基本的CS理论，展现该理论所包含的关键数学思想，并调查该领域一些重要的结论。我们的目标是尽可能清楚的解释CS理论，因而这篇文章主要是指导性的。该理论最吸引人之处是它涉及了许多不同的学科分支，包括应用数学、概率论。在本文中，我们决定突出这一方面，特别是随意性可以导致有效的感觉机制。我们也会讨论重要的含义，解释为何CS是同步传感、压缩数据的明确规则（如题所言），通过回顾重要的应用来总结我们的探索。传感问题在本文中，我们将讨论一种传感机制，该机制由线性泛函获取记录信息的信号f(t). , k=1,m. (1)我们简单的将想要取得的目标同波形相联系。这是一个标准的方案。如果传感波形是狄拉克-德尔塔函数（尖形），例如，y是f在时域或空间域的一个矢量采样值。如果传感波形是像素的指标函数，那么y是由数码相机传感器收集的典型图像数据。如果传感波形是正弦曲线，那么y就是一个傅里叶系数的矢量；这是磁共振成像（MRI）使用的传感形式。还有很多其他的实例。虽然人们可以对连续的时域或空间域信号发展一种CS理论，但是我们的注意力集中在离散信号。原因是两方面的：第一它在概念上较简单；第二，现有的离散CS理论还不成熟（但是显然为连续理论铺平了道路也被视为“应用”）。说到这里，我们由此对正在采样的情形颇感兴趣，此时测量的数值m比信号f的度量n要小得多。由于多方面的原因，这类问题十分常见。例如，传感器的数量可能受到限制。或者由于特定成像过程需经过中子散射，使得测量过程极其昂贵。又或者传感过程十分缓慢，人们只能在IMR中对目标进行有限次测量。诸如此类。 这些情况蕴含重要的问题。是否只能在mn时才能精确重建？是否可能设计mn的传感波形来获取几乎全部的关于f的信息？人们如何能够由这些信息得到近似的f？诚然，这种情况看起来很让人畏缩，因为这样就需要求解线性待定方程组。用A表示mn的传感矩阵，以矢量为一行（是a的复变换），当mn时，从中恢复的过程一般是不稳定的：满足的信号有无穷多。但是我们或许能够依靠目标f存在的实际模型，来找出一种解决办法。香农定理告诉我们，如果f(t)带宽实际上很低，那么少量的采样就能满足恢复的需要。下文我们就将看到，信号恢复实际上可以在更宽的信号模式上成功。非连续及稀疏信号传感本部分展示CS理论包含的两个基本前提：稀疏和间断性。稀疏当以适当的基础表达时，许多自然信号有着简明的表示。例如，在图1（a）中的图片和它在（b）中的小波变换。虽然几乎所有的图片像素都为非零值，波形系数提供了一个简明的摘要：大部分系数都很小，因而少数相对较大的系数就包含了大部分信息。波形参数图1：（a）一个原始百万像素图像，像素为0，255，(b)它的波形参数变换（为增强清晰度而随机扩展）。相对来说少量波形参数获得了大部分信号能量；许多这类图像可以深度压缩。（c）对除了25000较大值的小波形扩展参数进行清零而完成重构后的图片（像素值为0，255）。几乎看不出与原始图片有差别。正如我们在“采样过疏和稀疏信号重建”中描述的，图片可以仅依靠96，000个非连续测量实现完美的重建。从数学上讲，我们有一个矢量（例如图1中的图像像素），可将其在规范正交基（例如小波基）=内扩展如下： （2）这里x是f的一项参数，。可以方便的将f表示为（是以为一列的nn矩阵）。稀疏的含义现在清楚了：当信号扩展时，我们可以将较小的参数丢弃而不会有大的误差。一般认为，通过保持与式（2）中的最大值S的相应关系，可以得到。根据定义，在此及下文，是参数的矢量，S的最大值设定为零。这个矢量严格的说是稀疏的，它的少数值为零；在S几乎为非零值时，将这些目标称为S-稀少。既然是标准正交基，我们有，如果x是稀疏或可压缩的衰减很快，那么x就由很好的近似，因此，的误差很小。简单说来，我们可以舍弃一大部分参数而没有较大误差。图1（c）展示了一个例子，舍弃了97.5%的参数而获得的近似图像，同原百万像素图片几乎分辨不出差别。 这个规则构成了现代有损编码标准，如JPEG2000以及其他标准，数据压缩的一个很简单的方法就可以从f计算出x，然后把重要参数S的位置、大小进行编码。这样一个过程需要知道参数x所有的n，重要信息的位置可能提前并不知道（它们依赖于信号）；在我们的例子中，它们一般唯一图像的边缘。更普遍的是，稀疏是一个基本建模工具，它允许高效的基本信号变换；例如，准确的统计学估计和分类，高效数据压缩等等。本文是关于更加令人震惊而深远的影响，然而，稀疏在获得程序本身上有重要的支持作用。稀疏决定究竟多么高效地非自适应地获得信号。间断性采样假设我们有一对属于的正交的（、）。第一个用于传感式（1）中的目标f,第二个用于表示f。对这对正交基的限制并不是必须的，仅仅会简化我们的研究。定义一和之间的连系是： 式（3）在通俗英语中，相关性度量和的任何元素之间关系；也可见5。如果和包含相关的元素，相关性就大。否则就小。不管多大多小，它都按照线性代数的规定。 压缩采样主要被认为是低相关的，我们这就给出这样的例子。在我们的第一个例子中，是标准基，而是傅里叶基，。由于是传感矩阵，对应在时域和空间域的经典采样方法。时间-频率遵守，因此，我们可以有最大化的间隔。还有，锥形和正弦曲线在多个方面达到最大化间隔， 我们的第二个例子用小波形、noiselets表示。这里，Noiselets和Harr小波之间的一致性为，Noiselets与Daubechies D4和 D8小波间的一致性分别为2.2，2.9。这也可以延伸到更高的维数。（Noiselets与Spikes，傅里叶基同样达到最大非一致性）。我们对Noiselets的兴趣来自以下事实（1）它们与提供图像数据和其他类型数据稀疏表达的系统有非一致性（2）它们来自快速算法；Noiselet变换运行时间为o(n)时间，正如傅里叶变换，Noiselets矩阵不必存储成向量应用。这对于CS有效的数值计算是至关重要的。最后，随机矩阵与任何固定基间均有较大的非一致性。均匀随机的选择一个正交基，这可以通过独立均匀的在单位球面上采样n个正交化的向量得到。然后很大概率上，和间的一致性大约为。还有，具有独立同分布项（i.i.d.）的随机波形（），高斯或者二值项，将与任意固定表述之间具有较低的一致性。注意这里很奇怪的指示；如果非相干系统的传感很好，那么高效的机制应当取得与随机小波形的相互关系，例如白噪声！采样过疏及稀疏信号重建理想的，我们想测量f的所有n个系数，但是我们只能观测这些数据的子集，并获取数据 （4）其中是m0，然后（14）已知的最好的指数是5而不是4(14中只有logn)。这证明可以稳定而且精确的，从非一致域的未采样数据中重建几乎稀疏的信号。最后，RIP仍然有感知矩阵，其中为任意正交基，是从适当分布中随机抽取的测量矩阵。如果固定基，利用1）-4）组装测度矩阵，那么很大概率上，矩阵服从RIP特性，并满足（13），其中C为依赖于每一情形的常数。这些随机观测矩阵，在某种意义下是通用的23；即使设计观测系统的时候，稀疏基也不必已知。什么是压缩采样？典型的数据获取过程如下：搜集到大量的数据，在压缩阶段大部分数据被丢弃，这对于存储和传输目的是必须的。用本文的语言讲，我们获得一个高分辨率像素阵列f，计算传输系数的完整集合，编码最大的系数并除去其他系数，本质上以告终。这种大量获取数据，然后压缩的过程相当浪费（可以设想具有百万像素的数码相机，像素，最后编码图片之使用几百KB）。CS操作则不同了，它是“如果能够直接获取感兴趣物体的重要信息”。通过采取0()随机投影如“随机传感”，我们拥有足够的信息重建信号，具有的精度和提供的一样；目标有最好的S近似，最好的压缩表示。换句话说，CS数据获取协议本质上，将模拟数据翻译为已压缩的数字信号形式，最起码在原理上，从少数传感器获取已压缩信号。在获取步骤后，需要的是解压观测的数据。CS与编码理论中的观点有一些表面上的相似性，正似里-所罗门理论（RS）与实践26。简而言之在本文内容中，我们可以将编码理论中的观点改写过来：我们可以采用其前2S个傅里叶系数，k=0,1,2,2S-1，唯一的重建任意S稀疏信号，或者利用任意2S个连续频率（恢复问题的计算成本为求解一个 Toeplitz系统和取一个n点傅里叶变形）。这是否意味着我们可以利用这个技术感知可压缩信号呢？答案是否定的，主要的两个原因如下。首先，RS解码是一个算术技术，不能处理非稀疏信号（解码通过求解多项式求根）；第二，寻找信号的支撑的问题-即使当信号准确稀疏时-从前2S个傅里叶系数是格外病态的（问题如同利用高度聚簇的少量数据外推一个高自由度的多项式）。这些系数的小扰动将给出完全不同的结果，这样对于有限精度数据，可信赖的支撑集估计实践上是不可能的。尽管完全代数方法忽略了信息操作符的条件作用，拥有良好条件矩阵，对于精确估计是必须的，这是CS中的核心考虑，正如RIP扮演的角色。应用事实上可压缩信号可以通过与其信息级成比例的，非一致性测量有效采集，这意味着大量可能的应用。n 数据压缩。在某些情形下，稀疏基在解码端可能是未知的，或者对于数据压缩来说是难以实际执行的。正如我们在“随机传感”讨论的，然而，一个随机设计的可以被认为是一个通用的编码方案，因为它不需要根据的结构进行设计。（对于的知识和能力，只有载解码恢复的时候需要）。这种通用性对于像传感器网络27一类的分布式多信号编码十分有用。我们建议读者查阅Nowak和Goyal的文章中相关的讨论。n 信道编码。正如15钟讨论的，CS原理（稀疏性，随机性，Convex最优化）可以转向并且应用于设计快速纠错码，以防止传输过程中出现的错误。n 逆问题。在其他条件下，获取f的唯一方式是使用特定形态的观测系统。然而，假设信号f的稀疏基存在且与非一致，那么有效的感知是可能的。这样的应用包括MR血管造影术1和其他类型的MR设置28，其中记录了傅里叶变换的子集，需要的图像f在时域或者小波域是稀疏的。Lustig等人更加深刻的讨论了这个问题。n 数据获取。最后，在某些重要条件下，对于模拟信号完全采集n个离散时间样本是困难得（可能对于随后的压缩也是困难的）。这里，设计直接记录离散、低码率的非一致性观测是有益的。最后这些应用表明，数学和计算方法可以在常规的硬件设计具有显著限制的领域，发挥重要的作用。例如，使用CCD或者CMOS的常规成像设备，被限制在感知可见光光谱。然而，一个CS相机使用数字微镜阵列采集非一致测量（只需要一个感光元器件而不是百万个），可以显著的拓展这些特性。（参见【29】）沿着同样的思路，我们的部分研究注重在对于宽带信号进行“模拟-信息”转换得设备（见Healy等人的文章）。我们的目标是减轻对于常规ADC技术的压力，现在受限制到采样率为1GHZ。作为一个选项，我们提出了两种用于A/I的特定结构，在其中离散、低码率非一致测量序列从宽带模拟信号采集而来。在很大程度上近似，每一个测量值可以解释为入射模拟信号f与模拟测量波形的内积c。在离散CS框架下，我们的初步结果表明服，稀疏或者可压缩模型的模拟信号（在某个模拟字典）可以通过以与其信息级别，而不是奈奎斯特速率，成比例的采样率来获取。当然，我们必须提到，应用离散CS方法恢复稀疏模拟信号时面临的挑战。对于这些事情的彻底讨论超过了本文的范围，作为一个初步研究，我们可以简单的接受这样一个观点：在很多情况下，对于稀疏字典的离散化/采样有合适的恢复。我们的两个结构如下：1）非均匀采样器（NUS）：我们的第一个结构，简单的在随机时间点上对信号进行数字化。就是说，。有效的是，这些时间点是通过位于规则格子上的点低速采样而得到的。由于冲击函数与正弦函数之间的非一致性，这种结构可以用于采样稀疏频谱在奈奎斯特速率之下的信号。这样可以带来很大的好处，包括降低采样率，增加电路设置时间，降低噪声等级。2）随机预先综合调整（RMPI）。我们的第二种结构适用于更为广泛的稀疏域，最值得注意的是，那些在时间-频率平面具有稀疏特性的信号。尽管不大可能用很高的速率数字化模拟信号，却非常有可能在很高的码率改变其极性。M结构的想法（见图4（a）是将信号与的伪随机序列相乘，在时间窗口上对积进行积分，数字化每一个时间段内的积分。这是一个并行结构，我们可以并行运行多个乘法器积分器对，它们采用独特的或者几乎独立的伪随机信号序列。事实上，M结构将信号与序列进行相关，其中的一个随机测量过程是通用的，因此RMPI测量将会同任何固定时间-频率字典比如下文描述的加伯字典都不连贯。对于以上任何一种结构，我们已经在数字上（某些情况下物理上）确信，这样的系统对于受到热噪声、时钟误差、干涉和放大器非线性影响的非理想电路是具有鲁棒性的。图4模拟-信息变换。（a）随机预先综合调整系统（RMPI）(b)原始双脉冲信号（蓝色）和从随机测试经过1综合后的重建信号（红色）(c)经过1分析后重新测定的双脉冲信号及其恢复信号结构在实际获取场景中的应用，将要求算法和理论的继续发展，包括模信号的合适的稀疏表示集合。我们用一个离散实例进行总结，强调一些最近的有前景的方向。对于这个实例，我们选择一个长度n为512点包含个调制脉冲的维信号f（见图4(b)蓝色曲线）。从这个信号，我们采集m=30次测量，应用一个由独立同分布的贝努力项组成的观测矩阵。这是不合理的少量数据，对应着为超过的采样因子。对于重建，我们考虑一个时频加伯基，包含了大量受到高斯窗限制的正弦波形，具有不同的位置和尺度。全面地字典近似43超完成，并且不包含组成f的两个脉冲。图4（b）的红色曲线显示了最小化的结果。重建结果明显很差，我们看到。然而，我们可以通过对于恢复程序的两项改变来优化结果。首先我们代之以最小化，并服从（这项改变在为正交基时没有影响）。其次，在得到一个估计后，我们改变范数的权值并进行重建，低的惩罚施加于我们希望比较大的系数上。图4（c）的显示了四次变权值循环后的结果；我们看到。我们建议读者可以从中获得更多的关于这些方向的信息。这里的一点是即使数据量相当小，我们仍然获得了信号中包含的大部分信息。总而言之，这就是对于现在和将来的应用具有广阔前景的原因。