稀疏信号在gabor基下的压缩感知与重构

摘要多年来，指导信号采样的理论基础一直是著名的Nyquist采样定理，Nyquist采样定理指出，采样速率达到信号带宽的两倍以上时，才能由采样信号精确重建原始信号。然而随着人们对信息需求量的增加，携带信息的信号带宽越来越宽,于是很自然地引出一个问题：能否在保证信息不损失的情况下，用远低于Nyquist采样定理要求的速率采样信号，同时又可以完全恢复信号。本论文说明了压缩感知的基本理论和核心问题，还介绍了基于压缩的重构算法：基追踪算法（BP算法）和正交匹配跟踪算法（OMP算法）。其次分析了信号稀疏表示的基本原理,介绍了当前信号稀疏表示的主要方法,并重点阐述了基于gabor字典的稀疏表示方法及其在压缩感知中的应用,最后总结了稀疏表示所面临的问题和未来发展方向。最后研究和实验验证自行设计的信号在选择多大的稀疏度K最为理想；在测量矩阵方面，对测量矩阵采用QR分解；在重构算法方面，我们运用OMP和BP算法，并给出了算法的描述以及实验结果，最终在相同情形下，BP算法比OMP算法有更好的重构效果。关键词：压缩感知；稀疏表示；gabor字典；观测矩阵；重构算法

ABSTRACTOvertheyears,thetheoreticalbasisofguidancesignalsamplinghasbeenwell-knownNyquistsamplingtheorem,Nyquistsamplingtheoremstatesthatthesamplingratemorethantwicethesignalbandwidthinordertoaccuratelyreconstructtheoriginalsignalbythesamplingsignal.Withtheincreasingindemandofinformation,theinformation-carryingsignalbandwidthiswiderandwider,sonaturallyappearingaquestion:Canyouensurethattheinformationisnotthelossofcaserate,farbelowtheNyquistsamplingtheoremrequirementssamplingthesignalatthesametimecancompletelyrestorethesignal.Inthisthesis.Firstly,introducingthebackgroundoftheresearch,meaningandcurrentsituationbriefly.Andthecompressingsensingtheoryandcoreissues,andalsodescribesthereconstructionalgorithmbasedoncompressedsensing:Basedtrackingalgorithm(BPalgorithm)andorthogonalmatchingpursuitalgorithm(OMPalgorithm).Secondly,itanalyzesthesignalsparserepresentationofthebasicprinciples,thenthecurrentsignalsparserepresentation,andfocusesonthesparserepresentationbasedongabordictionarycompressedperception.finally,thesparserepresentationoftheproblemsfacedbyandfuturedevelopmentdirections.Finally,studyingandexperimentingvalidationofself-designedsignalinthechoiceofhowsparseKisideal;inthemeasurementmatrix,measurementmatrixusingQRdecomposition;inthereconstructionalgorithm,weusetheOMPandBPalgorithmandthealgorithmisgivendescriptionandexperimentalresults,andultimatelyinthesamecircumstances,BPalgorithmisbetterreconstructionresultsthantheOMPalgorithms.Keywords：Compressedsensing；Sparserepresentation；gabordictionary；Observationmatrix；Reconstructionalgorithm

目录TOC\o"1-3"\h\uABSTRACT II第一章绪论 51.1课题来源及研究的目的和意义 51.2压缩感知基本理论框架 51.3压缩感知的基本理论和核心问题 61.3.1信号的稀疏表示 71.3.2信号的观测矩阵 71.3.3信号的重构算法 81.4最小范数算法 91.5本文的内容安排 10第二章信号的稀疏表示 112.1信号的稀疏性 112.2压缩感知中的信号稀疏表示 132.3压缩感知中信号稀疏表示的主要方法 132.3.1正交基展开方法 132.3.2过完备字典表示方法 142.4gabor变换基 152.4.1gabor变换的基本原理 152.4.2gabor变换的应用领域 162.4.3实值离散信号的gabor变换 162.5稀疏表示所面临的问题和发展 182.5.1模型定阶准则问题 182.5.2正则化参数选择问题 192.5.3稀疏表示的发展 19第三章基于压缩感知的稀疏重建算法实现 203.1测量矩阵的设计 203.2OMP算法 223.3BP算法 263.3.1理论背景 263.3.2基追踪方法原理 283.4算法实验结果及分析 303.5本章小结 31第四章结论 314.1本文工作总结 314.2展望 32参考文献 33前言随着现代信息技术的飞速发展，人们对信息量的需求越来越大，需要处理的数据量也不断增多。信号处理的一个重要任务就是如何对信号进行压缩，并对压缩后的信号进行处理，如信号检测、特征提取、解码重构等。传统的奈奎斯特（Nyquist）采样定理指出，信号的采样速率必须达到信号最高频率的两倍以上才能精确重构出源信号。然而在很多场合下，人们对信息量的需求增加，所携带信号的频率和带宽也越来越高，这样就会产生巨量的采样数据，对硬件的采样速度以及存储要求提出了巨大的挑战。另一方面，在很多实际信号的压缩处理中，通常是先接收源信号，再压缩，然后传输、处理。于是很自然地引出一个问题：能否把源信号直接投影到一个低维空间，在这个低维空间中建立新的信号描述以及处理框架，在不损失源信号信息量的情况下，以远低于Nyquist采样率的速度对信号进行观测，并且能精确重构出源信号?如果这个问题可以被解决，那么可以大大降低数据采集设备的负担以及数据存储和传输代价，显著节省硬件设备的资源。近年来出现的一种新的信号采样理论压缩感知（CompressedSensing,CS）表明这是可能的。CS理论指出，在信号满足稀疏性的条件下，能以远低于Nyquist采样率的速度进行全局观测，将压缩和采样合并进行，然后通过适当的重构算法恢复出源信号。CS理论最振奋人心的地方就是把压缩和采样合并进行，突破了Nyquist采样定理的极限，能以全局观测的采样方式获取更少的数据点，来完美重构出源信号。由于CS的特殊性质以及对传统理论的颠覆，因此在信号处理领域带来了一场大的变革，具有广阔的应用前景。第一章绪论1.1课题来源及研究的目的和意义压缩感知理论于2004年由E.Candès、T.Tao等人发现并创立理论基础，直到2006年E.Candès、T.Tao、J.Romberg以及D.L.Donoho发表了关于CS理论的一些列奠基性文章。压缩感知被提出后，引起广大信号处理专家以及数学家的重视，迅速为信号处理领域的一个研究热点。压缩感知经过短短几年的发展，理论基础不断被填充，同时也展开了对压缩感知各方面的深入研究。目前压缩感知的研究主要包括以下几个方面：信号的稀疏表示、测量矩阵的设计、重构算法以及压缩感知应用。信号的稀疏表示是将信号投影到另一个空间，使得信号在此空间中绝大部分信号值为零或者很小，只有少数信号值占优，所得到的变换向量是稀疏的。这种表示是信号在另一个空间中的简洁表达，但并不损失信号的信息量。测量矩阵是指将源信号映射到低维空间的一个投影矩阵。测量矩阵需满足有限等距性质（RestrictedIsometryProperty,RIP），测量矩阵通过对源信号进行全局观测得到观测信号，最后利用重构算法从测量矩阵和观测信号中恢复出源信号，而如何设计精确且高效的重构算法是压缩感知问题的研究热点。压缩感知应用也是目前一大热点，比如模拟信息转换（AnalogtoInformationConverter,AIC），AIC是压缩感知理论走向实际不可以避免的问题，如何在前端获取信号的过程中使得通道数少、实时性高以及构造高效重构算法是目前研究的重点。目前，压缩感知的研究尚处于初步阶段，理论还不够完善，实际应用也比较少，国内起步也相对较晚，因此继续这一领域的研究有着及其重要的理论价值和应用意义。本文重点研究压缩感知重构算法，力图从理论分析、算法精度及效率等方面对该问题作全面的研究，并探讨这些重构算法在模拟信息转换中的应用。综上可见，从理论和应用两方面来看，开展压缩感知重构算法这一领域的研究，不仅具有重要的学术意义，而且具有广阔的应用前景。因此，本课题具有较强的理论意义和应用价值。1.2压缩感知基本理论框架传统的信号采集、编解码过程：编码端先对信号进行采样，再对所有采样值进行变换，并将其中重要系数的幅度和位置进行编码，最后将编码值进行存储或传输：信号的解码过程仅仅是编码的逆过程，接收的信号经解压缩、反变换后得到恢复信号。采用这种传统的编解码方法，由于信号的采样速率不得低于信号带宽的2倍，使得硬件系统面临着很大的采样速率的压力。此外在压缩编码过程中，大量变换计算得到的小系数被丢弃，造成了数据计算和内存资源的浪费。压缩感知理论对信号的采样、压缩编码发生在同一个步骤，利用信号的稀疏性，以远低于Nyquist采样率的速率对信号进行非自适应的测量编码。测量值并非信号本身，而是从高维到低维的投影值，从数学角度看，每个测量值是传统理论下的每个样本信号的组合函数，即一个测量值已经包含了所有样本信号的少量信息。解码过程不是编码的简单逆过程，而是在盲源分离中的求逆思想下。利用信号稀疏分解中已有的重构方法在概率意义上实现信号的精确重构或者一定误差下的近似重构。解码所需测量值的数目远小于传统理论下的样本数。Y接收信号Y接收信号解码重构恢复信号X测量编码YX稀疏信号编码端解码端图1.1压缩感知理论的编解码框图1.3压缩感知的基本理论和核心问题假设有一信号，长度为，基向量为，对信号进行变换：(1-1)显然是信号在时域的表示，是信号在域的表示。信号是否具有稀疏性或者近似稀疏性是运用压缩感知理论的关键问题，若(1－1)式中的只有个是非零值者仅经排序后按指数级衰减并趋近于零，可认为信号是稀疏的。信号的可稀疏表示是压缩感知的先验条件。在已知信号是可压缩的前提下，压缩感知过程可分为两步：设计一个与变换基不相关的维测量矩阵对信号进行观测，得到维的测量向量。⑵由维的测量向量重构信号。1.3.1信号的稀疏表示文献[4]给出稀疏的数学定义：信号在正交基下的变换系数向量为，假如对于和，这些系数满足：(1-2)则说明系数向量在某种意义下是稀疏的。给出另一种定义：如果变换系数的支撑域的势小于等于，则可以说信号是项稀疏。如何找到信号最佳的稀疏域?这是压缩感知理论应用的基础和前提，只有选择合适的基表示信号才能保证信号的稀疏度，从而保证信号的恢复精度。在研究信号的稀疏表示时，可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Candes和Tao研究表明，满足具有幂次(power-law)速度衰减的信号，可利用压缩感知理论得到恢复。最近几年，对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解。这是一种全新的信号表示理论：用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子。字典的选择应尽可能好地符合被逼近信号的结构，其构成可以没有任何限制。从从冗余字典中找到具有最佳线性组合的K项原子来表示一个信号，称作信号的稀疏逼近或高度非线性逼近。目前信号在冗余字典下的稀疏表示的研究集中在两个方面：(1)如何构造一个适合某一类信号的冗余字典；(2)如何设计快速有效的稀疏分解算法．这两个问题也一直是该领域研究的热点，学者们对此已做了一些探索，其中以非相干字典为基础的一系列理论证明得到了进一步改进。西安电子科技大学的石光明教授也对稀疏表示问题进行了认真研究，并基于多组正交基级联而成的冗余字典提出一种新的稀疏分解方法。1.3.2信号的观测矩阵用一个与变换矩阵不相关的测量矩阵对信号进行线性投影，得到线性测量值：(1-3)测量值是一个维向量，这样使测量对象从维降为维。观测过程是非自适应的即测量矩阵少的选择不依赖于信号。测量矩阵的设计要求信号从转换为的过程中，所测量到的个测量值不会破坏原始信号的信息，保证信号的精确重构。由于信号是是可稀疏表示的，上式可以表示为下式：(1-4)其中是一个矩阵。上式中，方程的个数远小于未知数的个数，方程无确定解，无法重构信号。但是，由于信号是K稀疏，若上式中的满足有限等距性质(RestrictedIsometryProperty，简称RIP)，即对于任意K稀疏信号和常数，矩阵满足：(1-5)则K个系数能够从M个测量值准确重构。RIP性质的等价条件是测量矩阵和稀疏基不相关。目前，用于压缩感知的测量矩阵主要有以下几种：高斯随机矩阵，二值随机矩阵(伯努力矩阵)，傅立叶随机矩阵，哈达玛矩阵，一致球矩阵等。1.3.3信号的重构算法当矩阵满足RIP准则时。压缩感知理论能够通过对上式的逆问题先求解稀疏系数，然后将稀疏度为K的信号从维的测量投影值中正确地恢复出来。解码的最直接方法是通过范数下求解的最优化问题：(1-6)从而得到稀疏系数的估计。由于上式的求解是个NP—HARD问题。而该最优化问题与信号的稀疏分解十分类似，所以有学者从信号稀疏分解的相关理论中寻找更有效的求解途径。文献表明，最小范数下在一定条件下和最小范数具有等价性，可得到相同的解。那么上式转化为最小范数下的最优化问题：(1-7)最小范数下最优化问题又称为基追踪(BP)，其常用实现算法有：内点法和梯度投影法。内点法速度慢，但得到的结果十分准确：而梯度投影法速度快，但没有内点法得到的结果准确。二维图像的重构中，为充分利用图像的梯度结构。可修正为整体部分(TotalVariation，TV)最小化法。由于最小范数下的算法速度慢，新的快速贪婪法被逐渐采用，如基追踪算法（BP算法）和正交匹配追踪法(OMP算法)。此外，有效的算法还有迭代阈值法以及各种改进算法。1.4最小范数算法前面主要对压缩感知的一些基本现状做了综述，如前所述，重构算法是压缩感知的核心内容，本节将重点针对压缩感知信号重构算法进行较全面地综述，具体主要包括最小化范数算法、匹配追踪类算法、迭代阈值算法、梯度类算法、压缩感知问题拓展的其他算法以及AIC重构算法等。这些方法是压缩感知中较主流的重构算法，基于这些算法的研究具有较强的实用性。文献[10]中证明了范数和范数的等价性，因此可以转化为求解以下优化问题：，s.t.＝(1-8)这是一个凸优化问题，可以通过线性规划（LinearProgram,LP）求解，典型的求解方法称为基追踪（BasisPursuit,BP）方法[9]。BP方法的优点是精度高，且需要的测量次数较少，但是BP法的计算复杂度为O()，即使对于常见的图像尺寸，BP法的计算量也是非常大的。另外，由于范数无法确定信号支撑集，所以尽管整体上能重构或逼近源信号，但存在低尺度位置的能量搬移到了高尺度位置的现象，从而对于一些频率较高的一维信号重构，容易出现高频振荡。鉴于传统BP方法的缺点，S.J.Kim等提出了内点法（Inner-pointMethod），内点法在重构精度较高的同时，把计算复杂度低到了O()，但仍然较高。随后，D.L.Donoho等又提出了同伦算法（HomotopyAlgorithm），同伦算法适合解决小尺度问题。此外，为进一步减少测量时噪声对重构算法的影响，E.Candès等提出了加权最小化范数（ReweightedMinimization）算法，该算法通过重新设置等价的最小化范数问题来提高稀疏信号的重构质量。1.5本文的内容安排近几年来信号处理领域诞生的新的压缩感知理论，针对可以稀疏表示的信号，将数据采集和压缩合二为一，这使得压缩感知理论在信号的处理领域具有突出的优点和广阔的前景。目前该领域中仍然有着许多值得研究的问题，其中重建算法是最为关键的一部分。它关系到信号压缩之后的精确重构和压缩感知过程精确性的验证。将压缩感知理论和语音信号相结合，是此文的研究方向。本文主要通过对压缩感知理论的理解进行展开的，开始通过介绍压缩感知理论的起源以及该理论产生的必要性。采用gabor基作为信号稀疏化的变换基，掌握gabor变换的基本特性。熟悉基追踪算法和正交匹配追踪算法，基于稀疏信号（如正弦信号）gabor变换系数的近似稀疏性，分别利用基追踪算法（BP算法）和正交匹配追踪算法（OMP算法）重构原信号，分析了稀疏度及观测序列点数对重构效果的影响，对两种重构算法下的稀疏信号压缩感知结果进行对比。第一章：绪论。首先简单的介绍一下本文的研究背景，研究意义和研究现状，说明了压缩感知的基本理论和核心问题，还介绍了基于压缩的重构算法（BP算法和OMP算法）。最后作了具体工作和全文内容的安排。第二章：信号的稀疏表示。文章首先分析了信号稀疏表示的基本原理,然后介绍了当前信号稀疏表示的主要方法,并重点阐述了基于gabor字典的稀疏表示方法及其在压缩感知中的应用,最后总结了稀疏表示所面临的问题和未来发展方向。第三章：研究和实验验证了自行设计的信号在选择多大的稀疏度K最为理想；在测量矩阵方面，对测量矩阵采用QR分解；在重构算法方面，介绍了目前已有的典型的重构算法，给出了算法的描述以及实验结果。主要使用了OMP算法，BP算法。第四章：总结与展望。对全文所进行的工作进行了总结，对本文的不足之处提出了改进，且对展望了下一步的研究方向。

第二章信号的稀疏表示随着现代传感器技术的发展,许多领域面临着日益膨胀的海量数据,如地球物理数据、视频数据、天文数据、基因数据等。如何实现对这些数据更为灵活、简洁的表达已成为一个倍受关注的问题。传统的信号表示方法通常是基于正交基(如傅里叶基,小波基)的展开。为了实现信号的灵活简洁和自适应的表示,一种更好的信号分解方式是根据信号本身的特点,自适应地选择合适的基函数,来完成信号的分解,从而得到信号的一个非常简洁的表达,即稀疏表示。由于信号的稀疏表示能在一定程度上自然地贴近信号的本质特征,因而对稀疏分解的研究有极其重要而深远的理论意义和广泛的应用价值。目前,稀疏表示被广泛应用于信号处理和图像处理的各个领域,如图像压缩、音频压缩、噪声抑制、盲信号分离、地震数据处理、系统辨识、雷达成像处理等等。尤其是近年来新兴起的压缩感知(compressedsensing)理论,其优点就是针对可稀疏表示的信号,将传统的数据采集与数据压缩合二为一,在获取信号同时对数据进行压缩。压缩感知理论的一个重要基础和前提就是选择信号的稀疏域,只有选择合适的基矩阵才能保证信号的稀疏度,从而保证信号的恢复精度。由于压缩感知理论的提出和蓬勃发展,稀疏表示越来越表现出它的优越性,许多人将目光投向这个领域,并进行了大量的研究,取得了广泛而深入的研究成果。2.1信号的稀疏性考虑空间一个实值的有限长一维离散时间信号，假设{︱＝，…,}是的一维基向量，则空间的任何信号可以线性表示为＝或＝ (2-1)其中，＝[︱…︱]是的基矩阵，是在域的变换向量，＝<,>。显然，在和是同一个信号的等价表示，是信号在时域的表示，如果s仅仅有K个非零项,且K《N,或者s中的各个分量按一定量级呈现指数衰减,具有非常少的大系数(K个)和许多小系数,则称s是K项稀疏的,或x在域是K项稀疏的。图1是信号x在域稀疏表示的形象描述,图中s为信号x在域的变换向量,且s仅包含三个非零分量(用图中的非空白格子表示),即信号s是3项稀疏的。图2.1信号在域稀疏表示参考文献[1]给出信号稀疏性的另一种定义:如果信号x在域的变换系数=〈x,〉的支撑域{i;≠0}的势小于等于K,则可以说信号x在域是K项稀疏的。通常时域内的自然信号都是非稀疏的,但在某些变换域可能是稀疏的。例如,自然图像在小波变换域具有稀疏性。图2为基于小波变换的图像稀疏表示示意图。其中图2.2(a)是一幅大小为512×512的原始图像,图中几乎所有的像素值都是非零的;图2(b)为原始图像的小波变换系数,为便于观察,图中将这些系数随机排列,从中可以看出,大多数小波系数的绝对值都接近于零,取其中绝对值最大的10%部分系数进行小波重构,得到的重构图像如图2(c)所示,从中可以看出,重构图像与原始图像差别很小,由此可得出结论有限的大系数包含了原始图像的绝大部分信息,可用于近似表示图像。目前广泛采用的JPEG2000图像编码标准正是以此为基础,通过小波变换实现图像压缩的。图2.2基于小波变换的图像稀疏表示2.2压缩感知中的信号稀疏表示信号的稀疏性是压缩感知的重要前提和理论基础。因此,对信号稀疏表示的研究是压缩感知理论的首要任务。稀疏表示对于压缩感知的基础性作用主要体现在:只有选择合适的稀疏矩阵,才能保证表示系数具有足够的稀疏性或衰减性,才能在减少压缩测量的同时保证压缩感知的重建精度。(1)根据压缩感知理论,高概率重构稀疏信号的充分条件是感知矩阵（）必须满足约束等距性RIP(RestrictedIsometryProperty)条件，即对于任意K稀疏信号x（x）和常数， （1-）≤≤（1+） （2-2）成立，其中T{1,…,N},且≤K,为中由索引所指示的相关列构成的大小为K的子矩阵。从上式可以看出,信号的稀疏度K越小,即信号越稀疏,约束等距性条件越容易满足。(2)Candes等进一步指出,在感知矩阵满足约束等距性条件的前提下,如果要精确重构K稀疏信号x,测量次数M必须满足M≥O(Klog(N))。因此,信号的稀疏度K越小,稀疏性越强,保证信号重构所需的测量次数越少。在研究信号的稀疏表示时,可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Candes和Tao研究表明,满足具有幂次衰减速度的信号,可利用压缩感知理论得到恢复。2.3压缩感知中信号稀疏表示的主要方法目前,信号的稀疏分解已经发展了多种算法。从信号展开的基的选择出发,概括起来说可以分为三大类:正交基展开方法、多尺度几何分析方法和基于过完备字典的展开方法。2.3.1正交基展开方法正交基展开方法主要基于调和分析理论。常用的正交分解包括傅里叶变换、短时傅里叶变换和小波变换。从傅里叶变换到小波分析,信号分析处理能力不断加强。傅里叶变换只对频率空间进行均匀划分;短时傅里叶变换增加了时间轴的划分,具有时频局部特性,但是各个时频窗口的形状大小都是一致的;小波变换的时频窗口可变,时频局部化能力大大增强,但是小波分析在一维时所具有的优良特性并不能简单地推广到二维或者更高维。它们共同的特点就是对于给定信号的表示形式唯一,一旦信号的特性与基函数不完全匹配,则不一定能够获得信号的稀疏分解结果。因此,迫切需要寻求新的信号稀疏表示方法。2.3.2过完备字典表示方法信号在过完备字典下的稀疏分解是一种全新的信号表示理论,也是近几年信号稀疏表示研究领域的热点和难点。它的基本思想最早是由Mallat提出的。Mallat采用超完备Gabor字典对图像进行稀疏表示,并提出了匹配追踪MP(MatchingPursuit)算法。根据图像的几何结构特性,从人类视觉系统特性出发,建立了匹配各层面图像结构的Gabor感知多成份字典,进而提出一种高效的基于匹配追踪的图像稀疏分解算法。在过完备字典中,用于稀疏表示的不再是“单一基”,而是通过构造或学习得到的冗余原子库,通过提高变换系统的冗余性增强信号逼近的灵活性,提高对图像等复杂信号的稀疏表示能力。由于过完备稀疏表示理论还不够成熟,算法所涉及的计算十分繁重,因此给实际研究和应用带来一定的困难。可以相信,随着对该理论的进一步研究和完善,该方法将有可能成为继正交分解方法和多尺度几何分析方法之后另一研究高潮。信号在过完备字典下的稀疏表示的研究集中在两个方面:①如何构造一个适合某一类信号的过完备字典;②如何设计快速有效的稀疏分解算法。目前,构造过完备字典的方法主要包括人工构造和训练学习两大类。其中,基于人工构造方法的过完备字典设计是当前的主流方法,它主要是通过一组参数和一套含参数的函数中选取若干函数来近似表示信号。其中,参数的选取是字典设计中一个很重要的问题。理论和实验表明,在字典的相关性满足一定条件的前提下,就能够得到信号在该字典下的稀疏表示。字典设计的优点是不需要存储整个字典,只需要存储字典的相关参数,从而大大减小了存储量。但是,由于设计的字典一般与原信号无关,因而不具有自适应性。其次,当字典中的原子维数很大时,存储字典的某些参数如Gram矩阵等仍然需要较大的存储量。基于训练学习方法的过完备字典是当前过完备字典设计问题的难点和热点。通过训练、学习得到的字典与信号相关,具有信号自适应性。目前字典学习的方法大多是通过迭代来更新字典和信号在字典下的稀疏表示。例如,K-SVD稀疏字典学习算法基于K-均值聚类的思想,用某聚类的中心点来表示信号。该算法稀疏表示效果好,计算复杂度低,但不足之处是缺乏严格的理论支撑。基于递归最小均方的字典学习方法(RLS-DLA)中对字典的更新是一个连续的过程,即每处理一个训练数据,字典进行一次更新,同时又引入了遗忘因子，因此减小了对初始字典的依赖性,且收敛性较好。2.4gabor变换基分析和处理平稳信号的最常用也是最主要的方法是Fourier变换。Fourier变换建立了信号从时域到频域的变换桥梁，而Fourier反变换则建立了信号从频域到时域的变换桥梁，这两个域之间的变换为一对一映射，时域和频域构成了观察一个信号的两种方式。Fourier变换是在整体上将信号分解为不同的频率分量，而缺乏局域性信息，即它并不能告诉我们某种频率分量发生在哪些时间内，而这对非平稳信号是十分重要的。与Fourier变换相关的傅氏谱、能量谱及功率谱都是信号变换到频域的一种表示，对于频谱不随时间变化的确定性信号与平稳信号，都可用它们进行分析和处理。但当信号的频率随时间变化时，如人的语音信号与脑电信号(EEG)、通过时变信道传输的信号及非平稳信号等，频域表示法就存在严重的不足，因为它不能表示某个时刻信号频谱分布的情况。针对频谱随时间变化的非确定性信号与非平稳信号，人们开始研究联合时频分析(简称时频分析)方法，它将一个一维的时间信号以二维的时间频率密度函数形式表示出来，从而揭示信号中包含了多少频率分量，以及每一分量是怎样随时间变化的。2.4.1gabor变换的基本原理针对非平稳信号的研究工作最早是从二十世纪四十年代开始的。1946年，Gabor在他那篇题为“通信理论”的经典论文中强调指出:“迄今为止，通信理论的基础一直都是由信号分析的两种方法组成的:一种将信号描述成时间的函数，另一种将信号描述成频率的函数(Fourier分析)，这两种方法都是理想化的。然而，我们每一天的经历—特别是我们的听觉，却一直是用时间和频率两者来描述信号的”。正是在这一思想下他提出了著名的Gabor变换(也称加窗Fourier变换或短时Fourier变换)，Gabor变换继承了Fourier变换所具有的“信号频谱”这样的物理解释，同时克服Fourior变换只能反映信号的整体特征而对信号的局部特性没有任何分析能力的缺陷，为信号处理提供了一个新的分析和处理工具，即信号的联合时频分析。Gabor变换在分析数字图像中局部区域的频率和方向信息方面具有优异的性能，即它能做到时域信号的局部化。Gabor函数可在空间域和频率域中同时进行测量，并且在这两种域中都是局部的变换，具有明显的方向选择特性和频率选择特性。因此，在计算机视觉和图像分析等领域得到广泛的应用。2.4.2gabor变换的应用领域Gabor变换的应用领域很广泛。一维的Gabor变换常用于暂态信号检测、时频分析等。自1978年，Gruand等首次把二维Gabor交换引入到计算机视觉中以来，基于Gabor变换的时频分析理论得到了深入而广泛的研究，其在计算机视觉领域中的应用也得到了不断发展。每年在与计算机视觉有关的许多国际会议(如CVPR，ECCV，ICCV，ICIP，ICPR等)上都有大量的与基于Gabor交换的时频分析理论及其应用有关的文章发表。例如:图像分析与压缩、图像分割、图像变换编码、纹理图像检索、指纹识别、人脸识别、手写汉字识别、纸张计算等。2.4.3实值离散信号的gabor变换Gabor展开是一种同时用时间和频率表示一个时间函数的方法，而求解gabor展开系数的公式被称为gabor变换。gabor变换和gabor展开已被公认为是通信和信号处理中信号与图像表示的最好的方法之一。gabor变换中要解决的最基本问题是：在给定综合窗下如何求解分析窗及gabor变换系数。近十几年来，围绕这一问题国内外相继提出了很多解决方法，最主要的有以Bastiaaans，Wexler和Qian等人为代表的解析法，Daugman等人提出的神经网络方法以及Ibrahim等人提出的自适应学习算法等等。但不论上述哪一种方法，均为复数形式的gabor变换。gabor基本函数、gabor展开系数、双正交分析窗函数求解的约束条件式及gabor展开式都是复数形式，计算量很大。为了简化gabor变换的计算，本文第一作者曾提出了一种实数形式的离散gabor变换RDGT方法，这种方法类似于复数形式的离散gabor变换的解析理论体系，并可采用快速的离散Hartley变换算法计算gabor变换系数，尤其是实数形式的离散gabor变换系数与复数形式的离散gabor变换系数的实部和虚部有着非常简单的加减关系，因此前者的计算完全可以替代后者的计算，从而达到大大减小gabor复变换系数计算量的目的；同样，在信号的重建方面，实数形式的离散gabor逆变换也比复数形式的离散gabor逆变换快得多，并且在实际应用中，实值gabor变换更方便于软件和硬件的实现。（1）首先选取核函数可根据实际需要选取适当的核函数。如，如高斯窗函数；（2-3）则其对偶函数为:（2-4）（2）离散Gabor变换的表达式:（2-5）（2-6）其中，（2-7）是的对偶函数，二者之间有如下双正交关系。（2-8）对于一般自行设计的一个离散稀疏信号x=[0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0];经过ifft变换到时域中作为原始信号：图2.3原始信号图2.4gabor变换后的信号通过上述变换后可以明显看出原始信号经过gabor字典后被稀疏化。2.5稀疏表示所面临的问题和发展2.5.1模型定阶准则问题对于BMP等吐故纳新类型的算法而言,一般采用的是残差控制准则。也就是说,在每一步迭代过程中判断剩余残差是否低于给定的门限。一旦低于门限则停止迭代,认为信号已经被抽取出来,剩余的是噪声。这就要求事先知道噪声的电平(或信噪比)。在噪声电平未知时,常常利用各种模型定阶准则来决定是否停止迭代,如AIC(Akaikes'InformationCriterion)、MDL(MinimumDescriptionLength)和MAP(MaximumaPosterior)等,这些定阶准则实际上可以看作是以模型阶数为变量、以模型拟合度和模型复杂性的加权折衷值为目标的优化问题。2.5.2正则化参数选择问题以度量函数为基础的全局竞争优化算法基本上都是与正则化原理相联系的。在优化过程中各个原子都处于相同的地位,相互之间进行竞争。目前,正则化参数的选择方法主要有两类,即先验策略和后验策略。先验策略最早由Tikhonov提出,正则化参数在正则化过程之前就已经确定了;后验策略与噪声的误差水平是已知或未知有关,不同情况有不同的方法。当噪声水平已知时,广为采用的主要有Morozov偏差原理和Arcangeli准则。当噪声水平未知时,采用另外的后验策略,如拟最优准则、L-曲线准则、交叉验证、广义交叉验证准则、子空间信息准则等。总的来说,正则化参数的选择还是一个开问题,目前的准则大都是以平滑的展平泛函为基础的,采用的是平方范数。对稀疏表示而言,由于稀疏性度量函数具有自身的特性,因此针对不同的应用背景,应当选择合理的准则。2.5.3稀疏表示的发展目前，稀疏字典主要包括正交基字典、紧框架字典、过完备字典。正交基字典主要是计算调和分析中的正交变换系统，如Wavelet变换；紧框架字典主要是以Ridgelet、CurveletBandletContourlet为代表的图像几何多分辨率表示或者称BeyondWavelet变换；在过完备字典中，用于稀疏表示的不再是“单一基”，而是通过构造或学习得到的冗余原子库，通过提高变换系统的冗余性增强信号逼近的灵活性，提高对图像等复杂信号的稀疏表示能力。1993年，Mallat和Zhang首次提出了基于过完备字典的稀疏分解思想，指出了过完备字典对于信号稀疏表示的必要性和重要性。基于过完备字典的稀疏分解依然是当前信号稀疏表示研究的热点和难点。过完备字典由称为过完备原子库的冗余系统构成，原子不必再是“单一基”函数。过完备字典的构造或学习应遵循基本准则：字典中的原子应能尽量匹配信号本身固有的各种不同特征。在这种准则下，稀疏字典必定是非正交的且是冗余的，正是通过增加原子个数提高变换系统的冗余性来增强信号逼近的灵活性，进而提高图像等复杂信号的稀疏表示能力。当字典中的原子个数大于信号维数N且包含N个线性无关向量张成整个信号空间时，字典称为过完备的。基于过完备字典的稀疏分解使得信号能量集中在极少数原子上，正是这些具有非零系数的原子匹配了信号的不同特征。设计适合特定信号的过完备字典，目前主要包括人工构造和训练学习两大类方法。基于构造方法的过完备字典设计是主流，主要包括：Wavelet和局部Cosine函数的级联、各向同性的Gabor字典、各向异性的Refinement-Gaussian混合字典、各向异性的Gabor感知多成份字典等。虽然Wavelet能够稀疏表示信号中的点奇异特征、局部Cosine函数能够有效表征纹理特征，但是由于Wavelet的可分离性与各向同性，Wavelet和局部Cosine函数的级联不能有效刻画图像中的边缘轮廓等线奇异特征。各向同性的Gabor字典能够有效刻画纹理特征。但是，由于Gabor原子的各向同性和单频带宽，也不适于有效刻画图像中的边缘轮廓等线奇异特征。各向异性的Refinement-Gaussian混合字典采用Gauss函数及其二阶导数作为原子的生成函数，能够有效表征图像中边缘轮廓结构，但是没有能够有效刻画纹理特征的原子。各向异性的Gabor感知多成分字典基于视觉感知的“有效编码假设”，以二维Gabor函数作为字典原子的生成函数，依据视觉皮层中神经元的响应特性和组织方式以及图像的多成分特性，约束生成函数中自由参数的取值范围，通过对生成函数进行平移、旋转、伸缩等几何变换生成一系列原子，遵循了过完备字典构造应该遵循的基本准则。基于学习的过完备字典是过完备字典设计问题的难点和热点，涌现的典型学习算法主要有：其中，K-SVD这类学习算法具有代表性，稀疏表示效果好，计算复杂度低，但不足之处是缺乏严格的理论支撑。基于过完备字典的稀疏表示的另一个方面是设计快速有效的稀疏分解算法。由于压缩感知信号重建问题追求的同样是稀疏解，因此某种程度上这里的稀疏分解算法可以推广应用到压缩感知问题。为了避免重复，稀疏分解的相关算法将在下文予以介绍。国内关于稀疏表示也展开了广泛的理论和应用研究。例如，谢胜利等人基于稀疏表示思想开展自适应的盲分离算法研究；尹忠科等人利用快速傅立叶变换实现匹配追踪的快速算法研究。第三章基于压缩感知的稀疏重建算法实现3.1测量矩阵的设计重构算法和测量矩阵有着密切的关系。在各种重构算法里，MP、OMP、ROMP等的重构质量与测量矩阵密切相关，即测量矩阵的列向量的非线性相关性是重构算法在选取列向量的前提保证。所以若能够构造出性质良好的矩阵，将大大简化重构算法的步骤，提高信号重构质量。目前主要使用的测量矩阵有：（1）高斯测量矩阵，矩阵中的每一个元素都独立服从均值是0，方差是1/M（M是测量数）的正态分布。（2）伯努利测量矩阵，矩阵中每一个元素都独立服从对称的伯努利分布。（3）傅立叶随机测量矩阵，矩阵中的M个行向量都服从均匀随机分布，且所有列向量均单位化。目前对测量矩阵的研究主要有：（1）对已有的测量矩阵改造，使其性质更加完善，更有利于重构算法。（2）从某一个正交矩阵出发，删除或者增加其中的某些行或列，得到新的测量矩阵，然后在应用中检验其性能。（3）根据某一应用的方向，构造非随机测量矩阵，让其满足UUP特性和稀疏信号重构特性。在针对测量矩阵的研究，给出一个测量矩阵的改良。因为测量矩阵的最小奇异值必须大于某一个正常数>0[1]。矩阵的最小奇异值和矩阵的线性相关特性有密切的关系。最小奇异值越大则矩阵的独立性就越强,当最小的奇异值趋于0的时候,矩阵的独立性就消失了。因此测量矩阵的最小奇异值有着重要的作用,寻求一种方法,提高矩阵的最小奇异值。QR分解是一种增大矩阵的奇异值而不改变测量矩阵性质的方法。和标准的QR分解相比,对测量矩阵进行以下的处理：首先对测量矩阵进行标准QR分解,得到上三角的矩阵R和方阵Q;保存矩阵R主对角线上的元素,其余位置值设为0,得新矩阵,从而得新测量矩阵。将高斯随机矩阵作为例子，对分解：＝ （3-1）其中Q是N×N的矩阵，R是N×M的上三角阵：＝ （3-2）因为矩阵R的主对角线上的元素值远远大于非对角线上的元素值，只保存式中R的对角线上元素，其余元素设置为0，得到的新对角矩阵,从而得到新的：＝ （3-3）满足测量矩阵的特征，最小奇异值是否大于的最小奇异值，的最大奇异值是否小于的最大奇异值，证明如下。＝＝ （3-4）＝≤＝＝ ＝＝＝ （3-5）＝≥＝＝＝其中，为列向量，分别对应矩阵R的对角线中最大元素和最小元素的位置，将它们置1，其他位置元素置0。从上述的证明过程得知：近似QR分解比较好地降低了原来测量矩阵的条件数，缩小了高斯测量矩阵奇异值的取值区间，使新的测量矩阵有更好的RIP性质。在接下来的重构算法中使用经过近似QR分解的高斯矩阵作为测量矩阵。3.2OMP算法（Matchingpursuit）MP算法是最早的一种贪婪迭代算法，通过逐步近似来求得信号稀疏表示，原理比较简单且易于实现，但是因为在测量矩阵列向量集合上的投影的非正交性，每次迭代的结果都是次优的。因此在MP算法的基础上，Y.C.Pati和R.Rezaiifar提出了正交匹配追踪算法（OrthogonalMatchingPursuit）OMP的概念。它将选择的原子集合（测量矩阵的列向量）按Gram-Schmidt正交化方法进行正交化处理，从而减少了达到收敛的迭代次数。其他改进方面，OMP算法是在给定迭代次数的条件下进行重建，需要很多的线性测量确保重建的精确性。OMP算法的核心思想是：用贪婪迭代法选择Φ的列，确保在每次迭代中所选择的列与当前冗余向量最大程度相关，再从测量向量中减去相关部分，然后反复迭代，直到迭代次数达到稀疏度K，强制迭代即停止。OMP核心算法步骤：输入测量矩阵Φ，稀疏基Ψ，采样向量y和稀疏K；输出ω的稀疏逼近；首先进行初始化：设定残差＝y，索引集为＝，t=1；然后循环执行步骤1-5：步骤1：首先找出残差r和测量矩阵列的积，将其中的最大值所相对应的脚标注为：＝ （3-6）步骤2：然后更新索引集＝∩{}，将测量矩阵中的重建原子集合＝[,]记录下来；步骤3：通过最小二乘来得到：＝（3-7）步骤4：进行残差的更新＝y-，t=t+1（3-8）步骤5：判断是否满足t>K这个条件，若满足条件则停止迭代，不满足便执行步骤1；如此循环。由此可见OMP算法确保了每次迭代的最优化特性，确实减少了需要迭代的次数。然而它也存在一个缺点，即每次迭代中仅仅选取一个原子对原子集合进行更新，导致重建时间的大大增加。迭代次数的多少与采样个数M和稀疏度K密切相关，随其增大，迭代次数也增大，导致耗时增加。OMP算法作为最早的一种贪婪迭代算法，有着不容忽视的作用，影响着以后的多种算法。用OMP算法对一段稀疏信号进行重构，得到的波形如下图3.1所示：图3.1一段信号OMP算法重建结果图3.1给出了运用OMP算法对一段信号重构后得到的图形，其中N=48，K=4，M≥4K,选择M=16，相对误差定义为error＝,error＝0.2031。通过分析不同M/N,不同K下的重构误差，考察观测数和稀疏度的选取对信号压缩重构性能的影响。固定长度为N=48的一段自行设计的信号，对M和K分别取下表所示值，运用OMP算法对自行设计的信号进行重构，定义重构误差为：error＝得到表3.1所示的数据。表3.1N=48时不同观测数和稀疏度下的重构误差MK816243220.99920.60370.04730.111040.44370.04760.324860.24020.235780.0744因为要求M≥4K，不满足此要求时，跳过其M值，出现上表中的空格。根据表3.1的数据画出图3.2，更直观表示。—————K=2的重构误差K=4的重构误差-·-·-·K=6的重构误差·········K=8的重构误差图3.2N=48时不同观测数和稀疏度下的重构误差图3.2给出了在不同观测值和稀疏度下的平均帧重构误差，“。”号表示表3.1中的数据。从图3.2中我们可以看出，不同的稀疏度K和不同的观测值M对应着不同的重构误差。在同一稀疏度下，观测数越大，重构误差越小。当稀疏度K=4,M=24（M/N=0.5）重构误差为0.0473，仅略高于K=8,M=40时的重构误差0.0254，而低于其他情况下的重构误差。因此我们认为当N=48的信号，在稀疏度K=4，观测数M=24时，对稀疏信号重构有最好的效果。表3.2N=48采用OMP重构后的重构信噪比M/NK0.16670.33330.50000.666720.31050.35625.57343.581748.171915.989919.083765.769231.296785.1800—————K=2的信噪比K=4的信噪比-·-·-·K=6的信噪比·········K=8的信噪比图3.3采用OMP重构后的重构信噪比在图3.3中，“。”号表示表3.2中的数据。从表3.2和图3.3中可以看出，观测数的多少和帧长的大小都对信号的重构有影响，当N不变时，随着M/N的增大（压缩比增大），SNR增大，当M/N≥0.5时，AFSNR值趋于平稳，达到15dB左右。对稀疏信号取M/N=0.5（N=48），在稀疏度K=4，观测数M=24时，对稀疏信号的重构有较好的效果。3.3BP算法3.3.1理论背景压缩感知信号重构本质上是找到一个最稀疏的向量作为最后的解，即解决下式描述的优化问题：，s.t,(3-9)为简单起见，向量x为稀疏度K的实稀疏信号，即≤K。为说明式（3-9），文献[16],文献[16]给出了下面的定义及定理。定义3.1（RIP条件）：≤≤（3-10）定义3.2(RIP常数)：=inf{：≤≤，≤K,}(3-11)定理3.1：令为满足RIP常数＜1的测量矩阵，且为信号的支撑集≤K，为支撑集上的稀疏信号，则对于式（3-9）描述的优化问题，x的解是惟一的。证明：用反证法进行证明。假设x是稀疏度为K的一个解，且存在另一个稀疏解z,z的稀疏度比x更小，=。设x的支撑集为，则≤K。所以有（z-x）=0(3-12)另一方面Supp(z-x)=,≤2K(3-13)因此有=0（3-14）但根据RIP条件有0＜(1-)≤=0(3-15)所以，故z=x，且＜1，证毕。实际上，从另一角度，假设有一2K稀疏信号,且1-≤=0（3-16）因此≥1,选择子集，令x=-,x为K稀疏。所以有下式成立==（3-17）这里u=x+v,u≠x,且u也为K稀疏的信号，因此在≥1的情况下，没有一个唯一解对于式（3-9）。解决0范数的优化问题是一个NP难题，在数据量较大的时候运算复杂度是不可估量的，实际中要直接解决这个问题是不可能的，因此需要将其转化为其他等价问题来进行求解。通常的转化方法有两种，一种是范数，一种是范数。目前许多文献都进行了推导证明。本章通过在二维情况下的简单几何解释给予说明。在二维情况下，N=2，m=1，因此CS模型方程变成一条直线，假设稀疏度K=1，也即是说，x在其中一条坐标轴上。给出了直观几何解释，横纵坐标，分别表示x中的两个待求元素：从结论可以看出范数的解落在了坐标轴上，为最稀疏的解，而范数的解没有落在坐标轴上，不是最稀疏的，当且仅当待求解直线垂直于坐标轴时，范数的解才是最稀疏的。而此时测量矩阵只有其中一列不为零，其余全部为0，这在实际测量中是不太合理的，因为必须知道源信号的支撑集。此可以很容易拓展到高维空间，在高维空间里，CS模型方程变成一个超平面，范数为一个“超球”，而范数为一“超菱柱”，其最优解仍然落在坐标轴上才能保证其稀疏性。所以目前多数文献中的最优化算法都是转化成范数进行。3.3.2基追踪方法原理基追踪（BasisPursuit,BP）方法最早是由S.S.Chen等[9]1998年提出的，当时主要用于解决信号的稀疏分解。后来2006年，D.L.Donoho等[14]对BP方法进行了修正。在CS模型中引入噪声，提出了BP的去噪方法（BasisPursuitDenoise,BPDN）。但这两种算法的基本原理是一致的，都是从完备或者过完备的原子库中寻求信号最稀疏的表示，用尽可能少的原子来表征源信号，从而简化问题，更易挖掘信号的本质特征。BP方法采用信号在基上投影的系数的个数作为稀疏性的度量，并通过最小化范数将信号的重构问题转化为一类极值约束问题，从而可以通过线性规划可以求解。目前线性规划常用的软件包包括l1-Magic、SOCP、CVX、SparseLab等等。用BP算法对一段稀疏信号进行重构，得到的波形如下图3.4所示：图3.4一段信号BP算法重建结果图3.3给出了运用BP算法对一段信号重构后得到的图形，其中N=48，K=4，M≥4K,选择M=16，相对误差定义为error＝,error＝2.4327*。通过分析不同M/N,不同K下的重构误差，考察观测数和稀疏度的选取对信号压缩重构性能的影响。固定长度为N=48的一段自行设计的信号，对M和K分别取下表所示值，运用OMP算法对自行设计的信号进行重构，定义重构误差为：error＝,而在BP算法中的重构误差非常小，而且在不同稀疏度K和不同观测数M中误差变化很大，所以在分析时不宜使用重构误差，直接使用信噪比比较合理。当信号长度N取值小时，BP算法的重构效果都比较好，当取值N=120时得出下列一组数据：表3.3N=120采用BP重构后的重构信噪比MK20406080428.298860.176138.473549.0835632.248336.384165.40901236.702840.66281638.1130—————K=4的信噪比K=6的信噪比-·-·-·K=12的信噪比·········K=16的信噪比图3.5采用BP重构后的重构信噪比在图3.5中，“。”号表示表3.3中的数据。从表3.3和图3.5中可以看出，观测数的多少和稀疏度的大小都对信号的重构有影响，当N不变时，随着M/N的增大（压缩比增大），SNR增大，当M/N≥0.5时，AFSNR值趋于平稳，达到36.384dB左右。对稀疏信号取M/N=0.5（N=120）,信号的重构效果比较明显，认为该稀疏信号的重构性能比较理想。3.4算法实验结果及分析取N=48，M=24，K=4的一段信号，信号重构结果如下:图3.6信号的重建图3.6给出了OMP算法和BP算法重构信号的结果。运用OMP算法重构的信噪比为15dB；运用BP算法重构的信噪比为207.2135dB,可见在相同情况下使用BP算法重构信号效果更好。3.5本章小结本章主要介绍了在OMP算法中对同一长度N=48的情况下稀疏度K和观测数M如何选取，才能使重构误差较小，并进行了实验验证。得出压缩比越大，重构效果越好。在BP表格说明数据的时候，由于BP算法的重构效果比较好，所以其重构误差非常小，不宜采用，于是直接列出信噪比的关系，而且在信号长度N很小时得出的结论不明显，于是取N=120进行实验论证算法中，实验结果表明压缩比越大，信噪比越大，重构效果越好。在介绍了贪婪迭代算法中的基础算法OMP算法，BP算法和将其一一的编程的实现，对实验的效果进行了验证。实验结果表明，这些算法都可以重构出稀疏信号，随着压缩比的上升，重构信噪比增大，重构效果良好。在运行程序过程中虽然BP算法比OMP算法的重构效果好，但是OMP算法的运行速率比BP算法好很多，所以在以后的运用中，应该综合考虑多方面的因素（结合运行速率和重构效果）来合理使用重构算法。第四章结论4.1本文工作总结本论文主要研究了基于稀疏信号的压缩感知的重建算法。近几年来在信号处理领域诞生的这种新的压缩感知的理论，对可稀疏表示的信号，将数据的采集和数据的压缩合二为一，吸引了越来越多的研究者。目前这个领域仍然有许多问题值得探讨和研究，其中重建算法是压缩感知理论中的一个关键的部分，关系到压缩后的信号的重建的精确度和采样过程中的精确性验证，找寻一种性能良好的重建算法是人们一直努力的方向。本论文深入分析了压缩感知的基本理论，研究和讨论了对于选择的固定长度的一段稀疏信号选择多大的稀疏度K和选择多大的观测数M最为理想，然后研究两者在一定情况下达到最佳标准。在重建算法方面，围绕OMP压缩感知算法和BP压缩感知算法展开了工作。主