[计算机软件及应用]外文翻译.doc

《[计算机软件及应用]外文翻译.doc》由会员分享，可在线阅读，更多相关《[计算机软件及应用]外文翻译.doc（55页珍藏版）》请在三一办公上搜索。

1、北京化工大学毕业设计（外文翻译）结构化的压缩感知理论与应用Marco F. Duarte Member, IEEE, and Yonina C. Eldar, Senior Member, IEEE摘要压缩感知（CS）是一个新兴的领域，在过去几年里已经吸引了很大一部分人的研究兴趣。在以往介绍压缩感知的文章中，CS限制其使用范围，标准离散到离散的测量架构使用基于标准稀疏随机性质的矩阵和信号模型。近年来，传感技术已经以它独有的方式进入了各种新的应用领域。这反过来，传感技术的基础理论完全有必要重新加以审视。随机矩阵测量的操作必须更换更有条理传感架构，对应可行的数据采集硬件的特点。标准稀疏前将扩大为包

2、括更丰富信号类型和编码更广泛的数据模型，包括连续时间信号。在我们看来，其主要内容是压缩感知技术中信号的利用以及结构的编码。而最重要的一点就是结合理论与实践。也就是说，指出将会在从数学到硬件出现的结构化压缩感知的潜力。我们总结强调出新的方向，以及更多的传统的压缩感知技术，作为一个从业者希望加入这一新兴领域的审查都希望，并作为一个研究人员的参考角度试图把现有的一些想法放到实际应用中。I. 介绍和发展动机 压缩感知技术是一门在信号处理团队中引起广泛兴趣的新兴研究领域。虽然关于压缩感知的介绍只是从几年前开始的1,2，但是就这个领域的研究已经出现了成千的文件、上百次会议、工作室以及一些专门的交流研究。

3、基于对这个领域的丰厚兴趣，因此在压缩感知上存在很多优秀的评论文章3-5。这些文章主要注重于对压缩感知的努力：使用标准离散到基于标准稀疏信号的随机性质，在其信号或表示形式上没有不假定稀疏度以外的任何结构上。为了分析该种设计的恢复方法以及提供性能保障，其设计公司运用了复杂的数学公式和丰富的理论知识。因此，在早期的压缩感知技术发展阶段我们更加应该重视其简化设置。迄今，几乎所有模拟 - 数字转换器（ADC）都遵循要求采样率至少两倍于信号带宽，即：著名的Shannon-Nyquist定理。该定理涵括了大量的数字信号处理应用如音频，视频，无线电接收机，雷达的应用，医疗设备等。在以往日益增加的对数据，以及的

4、无线电频率（RF）技术的需求促进了高带宽信号的使用，这使得Shannon-Nyquist定理决定的利率提高了硬件收购和随后存储以及DSP处理器的挑战性。虽然压缩感知器由采样速率的宽带信号的激励部分的速率远低于Shannon-Nyquist速率，但是它仍然保持着底层信号的编码信息。然而，在实践中，大多数对关于压缩感知的工作集中在使用随机测量来获取有限维稀疏向量上。这就排除了连续时间（即模拟）输入信号的重要性能，同样作为使用硬件结构也是无法避免的。拿到压缩模数转换器的圣杯并得到更高的分辨率需要能够处理更广泛信号模型的框架，如：不同结构类型的连续时间信号和实际测量原理。这些年，压缩感知技术这一领域跨

5、足了许多新的战线并且以自己独特的方式应用于各种领域。这反过来也使得重新审视压缩感知技术变得必要。随机矩阵测量操作，作为压缩感知早起建设的基础，必须被那些更加符合利益的应用的结构化测量操作所取代，如无线频道，模拟抽样硬件，传感器网络和光学成像等。早期工作在传感技术中具有的标准化稀疏特点必须拓展到更加丰富的信号类当中。那些有着低维信号结构的信号并不需要由标准稀疏信号来替代，而同时，那些能够任意变换尺寸的信号也不仅仅是有限维向量。近期信号处理组织正对压缩感知的工作，其意义可以分为两个主要的贡献领域。第一组是由涉及到压缩感知矩阵的理论以及应用组成。该矩阵并不是完全随机并且常表现出丰富的结构化特征。这一

6、点很大程度上源于在实践中获得的模型样本所作出的努力，从而得到从现实世界中模拟他们结构所得到的传感矩阵。第二组意义包括了表现出超越稀疏结构化的结构以及更加广泛的信号类的信号代表。如无穷维表示的时间连续信号。对于很多信号类型，当达到稀疏杠杆顶端的时候这种结构允许信号压缩的高电位。此外，无限维信号交涉为丰富结构化特征提供了一个明显不能由标准稀疏描述的重要例证。因为减少模拟信号的样品速率是压缩感知中的一个驱动力量，所以建立一个能够容纳任何空间中的希尔伯特信号是压缩感知框架中一个不可缺少的部分。这些组件都是由参与实际硬件实现的现实压缩感知器触发。在我们看来，其主要内容是压缩感知技术中的信号的利用以及结构

7、的编码。而最重要的一点就是结合理论与实践。也就是说，通过概括所需要的基础理论，指出将会在从数学到硬件出现的结构化压缩感知的潜力。我们坚信将压缩感知技术带入下一个阶段即实现这个发展中的领域的实际应用这是必不可少的。为了应用压缩感知的理论来解决实际信号采集的挑战，这些年很多研究者都投入了大量的时间努力。同时也产生了平行低速采样定律，这一定律将具有丰富理论样本的定律如创新性有限速率和Xampling框架结合在一起。处理这些广泛想法的文件已经有了几十份论文。在这次审查中，我们致力提供一个连贯的总结，突出了与更多传统压缩感知有关的新的方向以及联系。这份材料为那些想要加入这一新兴领域的人服务同时也提供了一

8、份总结了实际应用工作中的结果的参考。我们希望这能够吸引众多希望加入的数学家或者工程师以实现压缩感知技术的实际应用，并鼓励其在此新领域中更加深远的研究。II 背景我们生活在数字世界。电信，娱乐，医疗器械，小玩意，业务 - 一切都围绕数字媒体。精密的微型黑盒有比特流精准高速运转的过程。如今，媒体播放器显示自己喜欢的电影，或者他们的环绕系统综合纯粹的音响效果，仿佛坐在乐团，而不是客厅，让电子消费者感到自然。在数字世界中起着在我们的日常生活常规的基础性作用，就这么点，我们几乎忘记了，我们不能“听”或“看”到这些比特流，它们在幕后运行。这场革命的核心在于模拟到数字转换。 ADC器件把物理信息通过复杂的软

9、件算法数字化处理转化成数字的流。 ADC的任务是固有的复杂的：它的硬件必须持有获得一个快速变化的输入信号稳定测量。由于这些测量时间间隔，连续快照之间的值都将丢失。在因此，一般情况下，有没有办法恢复的模拟信号，除非其结构上的一些事先被纳入。经过采样，数字或位保留必须储存和后处理。这需要充足的存储设备和足够的处理能力。随着技术的进步，所以要求不断增加大量的数据，对模数转换器和随后的数字信号处理器和存储设备媒体实施前所未有的应对。那么，如何跟上消费类电子产品这些高要求呢？幸运的是，我们所获得的大部分数据可以在没有太多感知损耗的情况下被丢弃。这是明显的，基本上所有的压缩技术都采用到数据。然而，这种压缩

10、的高取样率的典范不能缓解大型采集装置和数字信号处理器的困难。在压缩感知上的开创性工作上，Donoho提出最终目标压缩和采样合并进行：“为什么在经历这么多的努力获得所有数据时，最重要的是会被我们扔掉的？我们为什么不能直接测量不会最终被扔掉的一部分？”。香农-奈奎斯特定理 小型集散控制系统ADC提供了正在录制的模拟信号和一个合适的离散表示之间的接口。一个常见的做法是假设信号是带限的，即谱内容限于最大频率B。有限带宽信号在有限的时间内变化，因此完全重建信号的采样速率不得低于信号带宽的2倍。这种根本性的结果往往是在工程区归因于香农-奈奎斯特11，12，虽然它的历史可以追溯到由惠特克13和Kotelni

11、kov 14的早期工作。定理1如果一个函数X(t)不包含频率高于B赫兹，那么这是完全确定的给予其坐标的一系列点间隔1/(2B)秒。一个根本原因为处理在Nyquist率之间有明确的关系X(t)和其样例X(nt)，使数字操作可轻松取代模拟示波器。数字滤波是这种关系成功被利用例子。自功率谱密度模拟离散随机过程是在一个类似的方式，估计和检测参数的模拟信号可以由数字信号处理器。与此相反，压缩是由一系列的算法步骤，其中，一般情况下，在X(nt)和存储的数据之间表现出复杂的非线性关系。虽然这个结构内，推动了信号采集设备，在过去的半个世纪的发展，对新兴应用的日益复杂，决定了越来越高的采样率，不能总是利用现有的

12、硬件满足。在相关领域，如宽带通信和射频技术的进步打开一个ADC器件相当大的差距。两次信号的最大频率分量的转换速度，已成为越来越难以获取。因此，高取样率的替代方案正在制定在学术界和工业界相当的重视。结构性模拟信号远远比Shannon-Nyquist定理可以更有效地处理没有采取任何结构的考虑。例如，许多宽带通信信号是由几个在高载波频率调制的窄传输。在工程中的一个普遍的做法是在解调输入信号乘以载波频率的波段，为了从高频率的窄带传输的内容转移到原点。然后在低利率的商业ADC的设备使用。然而，解调需要知道确切的载波频率。在这次审查中，我们专注于在定义结构的确切参数是未知的结构模型。例如，在多波段通信的情

13、况下，载波频率可能不知道，或可能会随时间而改变。我们的目标则是建立一个压缩采样，它不依赖于载波频率，但仍然可以获取低于奈奎斯特率和处理这些信号。B压缩感知和发展一个CS的精华是建立采集设备，利用信号结构，以减少采样率，存储和DSP的后续要求。在这样的做法，实际的信息内容决定的采样率，而不是信号所在的环境空间的尺寸。考虑有限维在要测量的信号可以作为一个独立的有限长度的向量表示问题时，可以大幅减少在实现这个任务无论在理论上和在硬件设计方面的挑战。这促使各种传感稀疏的信号，它主要研究离散有限向量的数学和算法方面的研究激增.在其核心，CS是一个数学框架研究由来自MN的测量长度的向量N代表一个信号的准确

14、恢复，有效地执行信号的采集压缩。测量模式由线性预测，或内部的产品，该信号向量为一组精心挑选的投影向量，作为多种探针的信号中所包含的信息。 （第三节和第四节）在本次审查的第一部分，我们调查的CS的基础和表现如何的想法，可以延伸到更详细的测量计划，纳入结构化的测量过程中。考虑现实世界的数据采集方案时，可能测量矩阵的选择取决于应用程序的约束。因此，我们必须从一般的随机结构偏离和应用结构内的投影，可以轻松地通过数据采集硬件实现的载体。第四部分重点选择;我们现有的理论和应用调查为几类结构性CS矩阵。在某些应用中，存在硬件设计，衡量一个Nyquist速率的模拟信号，获得CS通过这样的结构矩阵的有限维的测量

15、信号表示。在本次审查的第二部分（第五和第六部分），我们扩大CS的理论信号量身定做表示超出标准稀疏结构模型。最近新兴的理论框架，可以有效地获得更广泛的信号模型类是合并的子空间模型15-20。我们引入这个框架和一些在有限维在第五节的一些应用，其中包括结构和稀疏的更一般的概念及其应用。在第六节我们能看到从前面的章节和见解相结合的原则，我们延长CS的概念与无穷维表示的模拟信号。这个新的框架，简称作为Xampling9，10，依赖于更一般的信号模型一起就如何利用这些数学结构，以建立传感装置的指引，可以直接获取模拟信号 - 合并的子空间，降低利率。然后，我们调查结果几个压缩的ADC从这个更广泛的框架。II

16、I 压缩感知基础压缩感知（CS）1-5 有限维向量，依赖于线性降维的同时遥感和压缩提供了一个框架。具体来说，在CS中，我们不直接获取X而是获取MN线性测量y=x上使用一个MN CS矩阵。我们提供y作为测量向量。理想的情况下，矩阵设计目的在于减少可能多的测量数据从而收回他们的测量载体信号。然而，事实上，M N呈现的矩阵秩defficient的，这意味着它有一个非空的零空间，这反过来意味着，任何特定的信号，无限数量的信号x将产生相同的测量=为所选CS矩阵。因此，矩阵的背后设计动机是允许不同的信号为x;一类感兴趣的信号从他们的测量结果是唯一可识别= ，= ，即使MN中我们必须作出选择的信号，我们的目

17、标是从CS中恢复测量。 A 稀疏信号稀疏信号的许多压缩算法，采用变换编码的信号结构，是在CS中使用最普遍的信号结构。稀疏也有着丰富的历史应用在信号处理的问题在上个世纪（尤其是在成像），包括去噪，反褶积，恢复和修补21-23。引入稀疏的概念，我们依靠一个信号表示在给定的基础上为。每个信号是N的系数方面表示作为;安排到NN矩阵和到N1的系数向量系数列，我们可以编写简洁，。同样，如果我们用frame1含N的长度与L且（i，e，）的大号单元范列向量，那么对于任意向量存在无限多的分解量，。在一般集合中，我们是指作为sparsifying字典24。虽然我们的论述仅限于实值信号，概念也扩展到复杂的信号25，

18、26。我们说一个信号x是在基础或框架的K-稀疏，如果仅存在K K的任何矩阵设计，因为识别问题有未知数K，即使支持=supp(x)。在这种情况下，我们只是限制其列的矩阵对应的指数，记为，然后使用伪逆恢复X的非零系数： (3)在这里限制向量x的指数集，表示伪矩阵M。在（3）中隐含是的假设是列满秩，因此方程有独特的解决方案。我们首先保证不同的信号x的性质，导致不同的测量向量，换句话说，我们希望每个向量都能满足一个向量x， ，例如。矩阵在这方面的相关属性的一个关键是它的稀疏量。定义 1. 28一个给定矩阵的稀疏量（）的稀疏与最小数列是线性相关的。稀疏量关系到从张量到产品文献kruskal引入秩。这个定

19、义我们在下面有简单的证明。定理 2.28如果稀疏量（）2K，那么每个测量向量在这里都存在至少一个信号x使其。很容易看到稀疏量（）2，M+1，因此定理2成立的必要条件是。虽然代表的唯一性定理2保证的K-稀疏信号，计算一般矩阵的稀疏量组合计算复杂，因为必须验证，具有一定规模的列集是线性无关的。因此，它是最好的使用性能，很容易可计算提供恢复担保。矩阵的一致性是一个这样的属性。定义2.28-31矩阵的相干性绝对是最大内积之间的任意两列。 （4）它可以证明，下界被称为韦尔奇方向。注意当下界大约是，一个可以配合相干性和火花矩阵用人Gershgorin圆定理矩阵。定理3.34一个矩阵的特征值有，在队列中m，

20、集中在，用于半径。这个定理的应用于革兰氏矩阵，导致以下结果。引理1.28对任何矩阵， （5）通过合并定理2和引理1，我们可以对下列条件，保证唯一性。定理4.如果 （6）为每个测量向量这里存在最多一个信号例如。定理4在韦尔奇方向，为系数k提供了一个水平上限以保证它的唯一性：。当测量向量没有出错时，之前的矩阵的属性为其提供了保证唯一性。硬件方面的考虑引入测量误差的两个主要来源：由于噪声不传感阶段（在加性噪声的形式），以及由于在恢复过程中使用的矩阵之间的不匹配， ，和采集过程的实施。（在乘性噪声的形式,）.根据这些误差来源，它不太可能保证唯一性。然而，在理想的测量过程中这两种错误是可以接受的。为了更

21、正式，我们希望测量两个稀疏信号之间的距离， 至原始信号向量和之间的距离成正比。这种属性允许我们保证足够小，噪声，两个相距遥远的稀疏向量，彼此不能导致相同（喧闹）的测量向量。这种行为已正式进入禁区的等距（）的财产。定义.如果一个矩阵 有限制等距财产（），对于所有， （7）在理论上，保证了一个的 的所有子矩阵接近于等距，因此距离保存。我们稍后将显示该属性足以证明复苏是稳定的存在加噪声在某些设置里，介绍了噪声信号的前测量。恢复也在这种情况下稳定。然而，有一个失真的恢复退化因素70此外，RIP也会导致稳定方面推出的CS矩阵乘法噪声错配35,36.可以再一次连接到属性的一致性，Gershgorin圆定理

22、。引理2.41. 如果测量矩阵有单元阵列相关系数，那么有（K，）-RIP中有 一种方法可以很容易的将稀疏基与RIP连接。因为每K-稀疏向量是由它的测量唯一识别的，所以它足存在对于0使得（2K,)-RIP，这意味着所有的矩阵中的2K列集是线性无关的，i.e.,spark() 2K ( 定理2和定理4 )。我们随后会发现RIP将会比基于电火花以及相关连贯性的更能得到恢复。然而，检测压缩感知矩阵是否满足（K，）-RIP具有组合的计算复杂性。现在我们已经定义了一个CS矩阵的有关性质，我们将讨论适合用于CS的具体的矩阵结构。一个M x N 的由N个独特的标量构建Vandermonde矩阵 V 有 spa

23、rk(V)=M+1 27,不幸的是，这些矩阵条件差的N值渲染恢复问题数值表现很不不稳定。相似的有矩阵达到下界相关性满足 （8）正如从从Alltop框架生成序列的Gabor框架和更加一般的equiangular紧凑框架。同样也可以构建M x N确定性CS矩阵，该矩阵存在（K，）-RIP使得43，这些结构限制了需要恢复k-稀疏向量信号为的测量数量，并且在实际运用中，N和K的值通常是不符合要求的。幸运的是，遇到的这些瓶颈可以通过构建随机矩阵来消除。例如，一个M x N 的随机矩阵，在有spark()=M+1的高性能连续分布中，其矩阵相互独立并且确定分布。它也可以显示,当采用零均值分布和有限的方差时，

24、在趋向相关性的一致性收敛为44,45,同样的，随机矩阵如高斯,Rademacher，或者其他一般的分布矩阵。若要得到一个高性能的（K，）-RIP,需满足：46 (9)最后需要指出的是当设置RIP矩阵照以上提供似乎受到了限制，最新的数字结果显示，大多数适合压缩感知技术恢复的矩阵类与在文章中提到的矩阵相似，包括哈达玛变换,subsampled傅里叶变换等。47,48C. CS恢复算法现在起我们将集中于解决CS的恢复问题：给定y和，找出一个信号x使得y=x完全或者近似成立。当我们考虑稀疏信号的时候，CS的恢复过程由依附测量值y的稀疏信号x的搜索过程组成。通过定义矢量|x|0的l0基数为x 的数值为非

25、零的数字，最简单的方法是使用构成恢复算法的优化： （10）公式（10）依靠全程搜索并且当矩阵的稀疏性具有唯一性时对于所有的都是成立的（i.e. 因为M跟2M一样小，看引理2和引理4）。然而，这种算法具有一定的组合复杂度，因为我们必须检查测量矢量值y是否属于矩阵中任意K时对应的值。因此，我们的目标是找出可行的算法计算能够成功地恢复通过最少可能测量M值从y测量矢量得到的稀疏向量x。另一个可替代式（10）中的l0值是l1,定义。公式10的结果适应，被称为基础追踪（BP）22，通常被定义为 当 （11）由于规范是凸的，（11）可以被看作是（10）凸松弛。感谢凸性，该算法可以作为线性规划的实施计划，使得

26、其在信号长度多项式计算复杂49。(11)的优化可以修改，以便测量噪声；我们简单地改变其约束性的解决方案当 （12）在这里是选择适当的约束噪声幅度。此修改优化与不等式约束（BPIC）的基础上追求和被称为是一个二次多项式复杂求解方案。这个二次规划拉格朗日公式写成+ （13）被称为基础上追求去噪（BPDN）的。存在许多有效的求解找到BP，万浦电力投资，和BPDN解决方案概述，看51。通常情况下，范数有界噪声模型是过于模拟化，它可能是合理的，而不是假设噪声是随机的。例如，加性高斯白噪声n是一个普遍的选择。旨在解决随机噪声的方法包括基于复杂的正规化52和贝叶斯估计53。这些方法对先验概率或复杂的，分别观

27、察到信号集。特别是前一起在信号恢复噪声的概率分布，然后加以利用。基于优化的方法也可以在这种情况下制定的；最流行的技术之一是 Dantzig选择54:s.t. (14)在这里表示序列，它提供了在一个向量幅度最大的项和是一个常数参数，控制成功恢复的可能性。稀疏信号恢复的贪婪算法是一种基于优化的方法。这些方法在性质上是重复的并且这些方法根据其确定适当的内积的的测量值y的相关选择列来选择的值。例如：匹配追踪和正交匹配追踪算法通过找到最相关列进行信号残余，这是减去信号y的部分预算的贡献。正交匹配追踪算法正是由算法一定义，其中T（x,k）表示x上的一个阀值运算，该运算设置了所有但是除了x的零与x的最大项的

28、值。表示x的限制索引条目，它被用来找到稀疏表示的收敛准则，从而用于严格的或近似的检查是否包含。请注意，由于设计的原因算法不能超过M次迭代，因为有M行。其他有类似的正交匹配跟踪的贪婪技术包括用CoSaMP,作为定理2和子空间追求来表示。简单的变体被称为迭代硬阈值：它开始于一个最初的信号估计，其中它的算法反复重复一个梯度下降的紧跟硬阈值步骤，即：直到满足收敛准则。压缩感知恢复保证上面许多压缩传感恢复算法伴随着性能上的保证，我们根据保证公有的模型组织这些结果。首先，我们回顾一下依靠一致性的结果。作为第一个例子，当模型满足（6）时，基础追踪和正交匹配追踪从无噪测量中复原k稀疏矢量。此外，还存基于连贯性

29、的基础保证，它的设计是为了测量损坏噪声。定理5【59】让信号，并让，指明，假定k4并且在（12）。然后（12）的输出有一个错误的界限由确定。正交匹配算法的x的输出随着停止准则有一个误差的边界由确定，对于正交匹配跟踪提供伴随着正在积极下界x的非零项的幅度。这儿要注意不等式约束基础追踪必须意识到噪声幅度以使，同时正交匹配追踪必须意识到噪声幅度以设置适当的收敛准则。定理5的误差和噪声幅度成正比。这是因为噪声的唯一假设是它的大小，所以n可能会对其以最大限度的损害估计过程。 在随机噪声事件中，在的界限只能说概率很高，因为总是有小概率即噪声非常大以至于完全压过了信号。例如加性高斯白噪声，定理5的不等式约束

30、追踪的保证有很大的可能当参数，并且表示一个可调参数到控制的|n|2的可能性太大。第二个例子给出一个相关结果为追踪去噪算法。定理6.61 让信号，并让，同时。假设并且考虑到在.然后，可能以为顺序，13的结果x是确定的误差边界由确定并且它的支持是一个真正的K-X支持元素的子集在加性高斯白噪声下，个人需要挑选的的值在定理5中是给出的边界比定理6中的大得多。这表明降噪通过随机噪声模型实现。这种保证接近于给出的的Cramer-Rao界确定。我们完成了正交匹配跟踪的结果，在加性高斯白噪声设置的一致性研究为基础的担保。定理7.61 让信号，并让，同时.假定，并且，其中常数，然后至少可能，k迭代之后的正交匹配

31、跟踪有一个由，引起的错误边界，并且支持符合真正的K-x的元素的支持。正交匹配跟踪的贪婪的性质提出为了让支持能够被正确选择的x的最低限度得值的要求，以用来和与不等式约束的基础追求和追求去噪的比较。一个第二类保证基于限制等距特性，以下正交匹配跟踪提动了一个有意思贪婪算法观点。定理8让信号，并让，假设有-限制等距特性并且有,正交匹配跟踪能够在k迭代中修复一个K稀疏信号。即使有值得注意的更严格的限制等距条件在压缩传感模型上，保证也能够存在于噪声测量设置中。定理9 让信号，和，假设有（31k,）-限制等距特性并有，正交匹配跟踪在30k交互影响下有由|x-|,引起的错误的界。接下来的结果延伸担保，由疏到更

32、一般的信号下的噪声测量。我们在一个单独的定理中收集一系列独立的状态。定理10让信号，和，CoSaMP,SP,迭代硬阀值和与不等式约束上的x的输出运算，并有（CK,）-限制等距特性，遵守： 其中当用测量， 是x响亮的k稀疏近似值，限制等距特性的参数C,的要求和C1，C2和C3的值对每一个运算法则是确定的，例如，对于与不等式约束基础追求运算法则来说，C=2和=-1满足获得保证的需要，定理10中给出的保证类型是统一最优均匀，在某种意义上说，压缩传感复原错误对于x的信号的最好k稀疏近似是成比例的。CoSaMP，SP和迭代硬阀值的规则的用算法则由例如最优性的还没有向匹配跟踪和正交匹配跟踪的贪婪算法的目标

33、驱动，定理10 也同样适用从无噪测量中复原严格稀疏信号。推论11 让信号x，并且。如果有（CK,）限制等距特性，其中限制等距特性的参数c，是确定的对每种法则，则CoSaMP,SP,迭代硬阀值和BP法则能够严格的从Y中复原X。和定理5类似，定理10中的错误是成比例的对噪声幅度|n|2，界限很可能被裁剪成随机噪声。丹其革选择器提高了在加性高斯白噪声设置中错误的数量。定理12 让信号X，并且Y=，其中，假设在（14），有（2K，）和-限制等距特性并有.然后，至少可能，我们有。在加性高斯白噪声下相似的结果已经被作为正交匹配跟踪和阀值运算来证明。第三类担保依赖额外的连贯性和限制等距特性。这个类有一个非均

34、匀的味道，在这个意义上，结果只申请了充分稀疏信号的某些子集。这种灵活性允许从矩阵所需的属性明显放宽。在下一个例子，有一个概率的味道和依靠的连贯性属性。定理13.65 让信号并且支持随机可能抽取均匀进入自独立分布使。写和fix和。如果和那么x是基础追踪的唯一结果，概率至少为。总的来说，该定理只要一致性和的压缩感知矩阵谱范围足够小，我们就能够从测量值y中恢复大部分K-系数矩阵x。依靠概率的结果上是一致的，也可取得追踪去噪算法（13）45。保证完全依靠一致性和那些依赖于限制等距特性和之间的主要区别概率稀疏信号模式是成功的K-稀疏信号恢复所需的测量中号的数量缩放。根据界限（8）和（9），和（定理5,6

35、和7里的确定性保证），允许在定理10,12和13上高概率恢复的稀疏水平是。这就是所谓的平方根瓶颈65给出的一个随机压缩感知矩阵和稀疏信号模型普及的另一个原因。 IV压缩感知矩阵的结构而在压缩感知中最初的工作强调利用进入获得独立于一个标准的概率分布的随机压缩感知矩阵，由于任意矩阵和高维矩阵的乘积，这些矩阵往往对于现实世界的应用是不可行的。其实很多时候，物理传感方式和传感装置的能力限制，可以在一个特定的应用实施压缩感知的矩阵类型。此外，在模拟采样的背景下，对于压缩感知的主要动机之一是要建立导致子奈奎斯特采样率的模拟采样。这涉及到实际的硬件和结构的传感方式。硬件方面的考虑，需要更复杂的信号模式，以尽

36、可能减少复原所需的测量。在这一部分，我们为结构性压缩感知矩阵审查可用的替代品；在每种情况下，我们提供众所周知的履约保证，以及结构呈现的功能领域。在第六部分我们延长压缩感知框架，以便模拟采样这将导致新的硬件实现来减少基于扩展压缩感知的采样比率。请注意，本书给出的压缩感知设备的调查绝不是详尽的。我们的重点是对理论和implementational观点研究矩阵。A 二次采样非相干基底关键帧的连贯性的概念可以扩展到双正交基。这使得新的选择：选择一个在稀疏基上的正交基，并通过选择在所选的基础上的信号系数的一个子集的压缩感知测量69。我们注意到，由于选择所选的代表为压缩感知测量的系数，所以某种程度的随机性

37、任然在这个计划中。1）构想：在形式上，我们假设基础由测量提供，的每一列对应一个不同的基础元素。让成为NM列的子矩阵，和维持基本矢量的并设。在此设置下，粗线不同的度量来评估压缩感知的表现。定义4 28,69 N维正交基底和的相互连贯性和两个基地元素的最大绝对值： ，其中。相互一致性在范围内有值。例如，当在离散傅里叶变换的基础上或傅里叶矩阵，并是在规范的基础上或身份矩阵并且当两个基地至少共享同一个行或列。还要注意的是连贯性的概念和通过平等，相互连贯连接。也可以相互连贯的定义延伸到无穷维表示表示的连续时间信号（模拟）33,70。2）理论保证：下面的定理提供了一个相互连贯性的基础上恢复保证。定理14.

38、 69让作为在中的K-稀疏信号和支持， ，随着条目有迹象均匀分布随机选择，挑选一个子集在随机观察测量是一致的，随着。假设和作为的固定的值。至少是（11）的结果。定理14所要求的测量方法的数量从到。它是可能的定理14的保证扩大可压缩信号适应71一个Rudelson和Vershynin的参数链接的连贯性和限制等距常数。定理15.71，标记3.5.3挑选一个子集作为观察测量的设置，并且。假设 作为C的固定值。然后大概至少，在常量下，矩阵有限制等距特性。利用这个定理，我们获得定理10保证的可压缩型号测量和连贯性价值支配。3）应用：二次不连贯取样基底的应用程序有两种主要类别。在第一类，收购是有限的硬件建

39、设，在变换域的直接测量。最相关的例子是磁共振成像（MRI）72和层析成像73，以及光学显微镜74，75。在所有情况下，从硬件获得的测量对应图像的2-D连续傅立叶变换系数，但通常不会随机选择流行由于傅立叶功能，相应的正弦曲线，将与功能，无次序的本地化的支持，在实践中这种成像方法行之有效稀疏/可压缩，如小波变换69，总的变化73，标准的典型代表74。在光学显微镜的情况下，傅立叶系数，测量对应的低通制度。高通值完全丧失。当底层的信号x可以改变的标志，标准稀疏复苏如BP算法通常不会成功恢复真正的基本载体。复原的情况下从低通系数恢复，特殊目的稀疏的恢复方法开发的名义下，非局部硬阈值（NLHT）74。这项

40、技术，尝试分配稀疏信号的场外支持在执行阈值的步骤取决于邻近位置的值迭代时尚第二类包括购置新硬件的设计，可以得到信号的预测对一类向量。矩阵设计步骤的目标是要找到其元素属于基础一流的，可以在硬件上实现的载体。例如，基于一类的单像素成像光调制器60，76（1）在图中看到一个例子。可以对图像的载体，获得预测有二进制进入。例如基底，以满足这个标准包括沃尔什 - 阿达玛和noiselet基地77。后者是特别有趣的成像应用，因为它是已知与Haar小波的基础上最大限度的无序图一。单一像素的摄像头图。事件对光（对应到所需的图像x）反映了一个数字微反射镜器件（DMD）阵列提供的伪随机数发生器（RNG）模式调制的镜

41、子方向。每个不同的镜像模式产生一个对应一个测量Y（M）单个光电二极管的电压。重复这个过程M次不同的模式，以获得完整的测量向量y（76）。相比之下，由于其极大支持，沃尔什 - 阿达玛的基础上的某些元素的高度与小波相干在粗尺度的功能。置换的基础载体的条目（随机或伪时尚）有助于减少之间的计量基础和小波的基础上的连贯性。因为单一像素的摄像头，通过光聚合的光场调节，比标准多传感器计划时获得的测量提高了信号的信噪比 78。类似的成像硬件架构已开发中79，80另一个例子是一个可配置的采集设备ADC81，其目的是随机抽样收购周期，多频模拟信号的频率成分属于一个统一的网格（同样以随机第四节-B3的解调器）。信号

42、的稀疏的基础上，再次选择离散傅里叶变换的基础上。计量基准的选择是认同的基础，因此，测量对应在随机抽取的标准信号。在特定的时间，硬件实现采用随机时钟驱动传统的低速率ADC采样输入信号。正如图2所示。根据一组定时模式伪算术级数，使用FPGA输出一个预先确定的伪随机时钟脉冲序列指示信号进行采样的时间。这个过程重复循环，建立一个窗口采集任意长度的信号。这个随机ADC使用的测量和稀疏的框架也兼容信号在频域稀疏设计素描算法81，82。B结构二次采样矩阵在某些应用中，获得的测量采集硬件不直接对应感觉到在一个特定的变换信号的系数。相反的意见是一个多元线性组合系数的信号。由此产生的压缩感知矩阵已经称为一个结构二

43、次采样矩阵83。1） 公式：考虑可用的测量向量矩阵，可作为该产品的描述其中R是的混合矩阵和U是基底。压缩感知矩阵的P行选择随机获得，并所产生的二次采样矩阵的列正常化。有两种可能采样阶段：首先R能提供PN矩阵为可利用测量； 图2. 图随机采样ADC。由FPGA产生一个伪随机时钟驱动低速率的标准ADC采样输入信号在预定的伪倍。取得的样本，然后送入一个CS恢复算法或傅立叶稀疏信号估计音调的频率和幅度上的信号（81）的恢复算法。第二，我们仅仅利用维持可用矩阵M2，在z1并且任何， 存在绝对正常量以使如果 则矩阵有等距特性并有至少.同样以而此情况下的无序基底，的可能的值提供给我们是要求的测量数字M从到。3)应用：压缩的ADC是CS的一个广阔的应用前景，我们第六节B6的