基于压缩感知理论的重构算法介绍_压缩感知重构算法综述

基于压缩感知理论的重构算法介绍由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“压缩感知重构算法综述”。

压缩感知重构算法综述

李珅

1,2，马彩文，李艳，陈萍

111（1.中国科学院西安光学精密机械研究所 光电跟踪与测量室,陕西省 西安市 710119;2.中国科学

院研究生院,北京 100039）

摘要：现代社会信息量的激增带来了信号采样、传输和存储的巨大压力，而近年来出现的压缩感知理论(Compreed Sensing,CS)为解决该问题提供了契机。该理论指出：对于稀疏或可压缩的信号，能够以远低于奈奎斯特频率对其进行采样，并通过设计重构算法来精确的恢复该信号。本文介绍了压缩感知理论的基本框架，综述了压缩感知理论的重构算法，其中着重介绍了最优化算法和贪婪算法并比较了各种算法之间的优劣，最后探讨了压缩感知理论重构算法未来的研究重点。

关键词：信号采样;压缩感知;稀疏;重构算法 中图法分类号： TP301.6 文献标识码：A

Survey on reconstruction algorithm based on compreive

sensing

Li Shen1,2, Ma Cai-wen1, Li Yan1, Chen Ping1

(1.Xi’an Institute of Optics and Precision Mechanics of CAS, Xi’an Shaanxi 710119, China；2.Graduate University of Chinese Academy of Sciences, Beijing 100039, China）

Abstract：With the rapid demanding for information, the existing systems are very difficult to meet the challenges of high speed sampling, large volume data transmiion and storage.Recently, a new sampling theory called compreive sensing(CS)provides a golden opportunity for solving this problem.CS theory aerts that a signal or image, unknown but supposed to be sparse or compreible in some basis, can be subjected to fewer measurements than traditional methods use, and yet be accurately reconstructed.This paper gives a brief overview of the CS theory framework and reviews the reconstruction algorithm of CS theory.Next, this paper introduces the basis pursuit algorithm and greedy algorithms and explores the difference between them.In the end, we briefly discu poible implication in the areas of CS data reconstruction.Key words：information sampling;compreive sensing;sparse;reconstruction algorithm

0 引言

随着现代科技的飞速发展，人们对信息量的需求也在剧增。传统的信息采样是基于香农采样定理，它指出信号的采样率不低于最高频率的两倍，信号才能被精确的重构。该理论支配着几乎所有信号的获取、处理、存储和传输。

一方面，在许多实际应用中（如超宽带通信，核磁共振，空间探测，高速AD转换器等），信息在存储和处理时，为达到采样率而需要大量的采样数据，从而导致采样硬件成本昂贵，获取效率低下甚至在某些情况难以实现。另一方面，在数据的存储和传输方面，传统的做法是先按照Nyquist方式获取数据，然后将获得的*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

数据进行压缩，最后将压缩后的数据进行存储或传输。显然，这样的方式造成很大程度的资源浪费，同时也提出了一个问题[1]：既然在压缩中需要丢弃大多数数据，为什么不在采样时直接取得我们需要的重要数据？ 近年来，D.Donoho、E.Candes及华裔科学家T.Tao等人提出了一种新的信息获取理论－压缩感知(Compreive Sensing)，以下简称为CS。该理论指出[1]：对于可压缩的信号，可以通过低于或远低于奈奎斯特标准的方式对其进行数据采样并精确重构该信号。与香农定理不同的是，压缩感知并不是直接测量信号本身，它使用非自适应线性投影（感知矩阵）来获得信号的整体构造从而直接得到重要的信息，忽略那些在有损压缩中会被丢弃的信息。一般来说，压缩感知涉及三个比较重要的层面 [2]：

一、信号稀疏域的选取，是压缩感知理论的基础和前提。

二、观测矩阵的选取，已经证明大部分具有一致分布的随机矩阵都可以作为观测矩阵。

三、重构算法的设计，由于压缩感知采用的是全局非自适应测量方法，观测数量远远少于信号长度，从而数据采集量大大减少。但是需要付出的代价是信号重建算法的软件成本。因此，CS重构算法的好坏直接影响到CS理论是否实用。

其中S是投影系数si,iiT构成的N×1维列向量。显然，X和S是同一个信号的等价表示，其中X是在时域或空间域的表示，S是在Ψ域的表示。当信号可以仅被K个基向量线性表示时，则称信号x为K-稀疏。当K0有：

sppsii1/pR(2)

传统思路中压缩信号就是采用这种正交变换的方式，其编码解码的策略为：编码首先构造正交基矩阵Ψ，作变换SX,保留S中最重要的K个分量及其对应的位置。解码将K个分量放回到其对应的位置，并将其他位置填0，以此构造Ψ，最后进行反变换S求得重构信号。

显然，这种以Nyquist-Shanon采样定理为准则的编码和解码方法有很多缺点。

一、采样后再进行压缩的方式浪费了大量的采样资源，如果采样后的信号长度仍然很长，那么变换会消耗很长时间；

二、由于需要保留的K个重要分量的位置是随着信号的不同而不同，所以这种编解码方式是自适应的，需要分配多余的存储空间以保留K个重要分量的位置。

三、K个重要分量有可能在传输过程中丢失其中的某几个分量从而造成较差的抗干扰能力。

近几年出现的压缩感知理论，对传统的理念是一次革新，它表明我们可以用比传统途径少得多的采样和测量来恢复信号。该理论主要依赖于两个原则[4]，稀疏（sparsity）和不相关(incoher-ence)，稀疏关于感兴趣的信号，它所表达的意思是：连续时间信号的信息率可能比根据其带宽所建议的小得多，离散时间信号所依赖自由度的T压缩感知理论简介

1.1基本思想 可压缩（稀疏）的定义：考虑一个一维信号

Nx∈RN×1，都可以用N×1维基向量ii1线性表示。为了简化问题，假设基向量为规范正交向量，使用N×N的基矩阵1|2|...|N,信号x可以被表示为：

xsiii1NorS可以说，许多自然界的(1)

数量比它的长度少得多。

信号在某种程度上都是稀疏的或可压缩的，当以*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

合适的基Ψ来表示时，信号可以有很多简练的表达式。不相关表达了一种含义即以Ψ稀疏表示的信号一定可以在其所需要的域中展开。基于这两个原则，压缩感知理论指出，长度为n的信号X在某组正交基或紧框架nn上的变换系数是稀疏的，如果我们可以用一个与变换基Ψ不相关的观测基Ф（Rmn大多数随机矩阵都满足RIP，如高斯随机测量系和伯努利随机测量系。文献[13]的工作告诉我们：在某种意义上说，选择随机测量对于稀疏矩阵来讲是一种最佳策略，只需要几乎最少的m个测量便可恢复稀疏度为S≤m/log(n/m)的信号，而且分析时所需要的常量都很小。第二类为非相关测量系，即测量矩阵和变换基Ψ是不相关的，其不相关性可以通过测量它们之间的相关系数，文献[14]给出了测量矩阵Ф和变换基Ψ的相关系数μ = N1/2maxi,k||，μ越小说明测量矩阵Ф和变换基Ψ的不相关性越大，测量所需要的数目也越少。

第三步：重构信号x，区别于奈奎斯特理论的线性感知问题，由于观测数量m远远小于信号长度n，重构面临着求解一个欠定方程组的问题。当信号x是稀疏或可压缩的，求解欠定方程组的问题可以转化为最小0范数问题如式(4)：，mn）对系数向量进行线性变换，并得到观测集合m1，则可以通过求解最优化问题来精确地重构信号X。

1.2 压缩感知采样过程

基于CS理论实现信号压缩的采样过程为： 第一步：找到某个基或紧框架Ψ，使得信号x在Ψ上是稀疏的，并求出变换系数：S ＝ ΨT X，其中S是X的等价或逼近的稀疏表示。变换基Ψ的选择可以为某种已被广泛应用的基，如小波基、傅里叶基、局部傅里叶基等[5][6]，其中关于正交基的选择，可以参考文献[1]和文献[7]。另外，可以使用紧框架（原子字典）来对信号进行稀疏表示，如曲线波Curvelets[8]和轮廓波Contourlets[9]，这两类变换基具有更好的方向性，并且各向异性，少量系数即可有效地捕捉图像的边缘轮廓，在边缘表示方面优于小波。第二步：需要设计一个平稳的、与变换基Ψ不相关的m×n维观测矩阵Ф，对S进行观测得到观测集合Y=ФS＝ФΨTX，该过程也可以表示为信号x通过矩阵Acs进行非自适应观测：Y=AcsX(其中Acs =ФΨT，称为CS信息算子)。需要关注的问题是观测矩阵Ф的选取，需要保证稀疏向量S从n维降到m维时重要信息不被破坏。在压缩感知理论中，受限等距属性（Restricted Isometry Property, RIP）N[10][11]

minTX0s..tAcsXTXY(4)

然而统计理论和组合优化理论告诉我们，组合优化是一个NP难问题，当N很大时，数值上无法有效实现，且抗噪声能力很差；Candes, Tao和Donoho等人已证明，当测量矩阵满足约束等距性质(Restricted Isometry Property, RIP)时，组合优化问题(或称，l0约束优化问题)可转化为数值上容易处理l1约束的凸优化问题：

minTX1s..tAcsXTXY(5)

除此之外还有一些其它方法可以重构信号,如:1）将l0范数松弛为lp范数；2）通过先验分布引入稀疏性，再用Bayesian方法实现信号稀疏重构；3）使用启发式算法(heuristic algorithms)，如借鉴图模型和编码理论中的belief-propagation和消息传递技术。

是判断矩阵是否可以成为测量矩阵的一个重要的标准。对于k稀疏向量S∈R来说，当它满足式(3)时，测量矩阵Ф满足RIP。

（1-）s2s2（1）s(3)压缩感知理论对于测量系有两个主要的分类：第一类为随机测量系，文献[10][12]已证明压缩感知重构算法研究

2.1 重构算法介绍

*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

现阶段CS重构算法大致可以分为以下几类。

第一类是贪婪迭代算法，针对组合优化问题提出，该类算法主要是将信号与原子字典之间的联系作为测量原子（系数）更加有效或非零的一种方式。基本原则就是通过迭代的方式寻找稀疏向量的支撑集，并且使用受限支撑最小二乘估计来重构信号。这类算法包括：匹配追踪算法(MP ,matching pursuit）、正交匹配追踪算法

比其他重构算法更优越的重构精度。目前该类算法包括：新期望极大值(Expectation-Maximization, EM)算法[25]、贝叶斯压缩感知(BCS,Bayesian Compreive Sensing)算法[26]、基于单测量向量(SMV，single measurement vector)模型提出的SBL[27](sparse Bayesian Learning)算法和基于多测量向量(MMV，Multiple Measurement Vectors)模型提出的MSBL[28]。SBL是贝叶斯学习中很重要的一类算法，SBLMSBL算法与l1范数凸优化算法不同的是，后者全局最小化通常并不是最稀疏解，而前者的全局最小值则是最稀疏的，并且全局最小值比一些典型的算法（如FOCUSS算法）更少。通过关注时间相关性对现有算法性能的影响，文献[29]提出了AR(autoregreive)-SBL算法，该算法将每一个信号源的建模都作为一次一阶自动回归过程，同时对数据本身进行学习得到AR系数。

(OMP,[16] orthogonal matching pursuit）、分段OMP算法(StOMP，stagewise orthogonal matching pursuit)、规范OMP算法[17](ROMP，Regularized Orthogonal Matching Pursuit)、CoSaMP算法[18](compreive sampling matching pursuit）、迭代硬阈值法

[19](iterative hard thresholding，IHT）以及GraDeS[20](gradient descent with sparsification)等。算法的复杂度大多是由找到正确支撑集所需要的迭代次数决定的，算法计算速度快但是需要的测量数据多且精度低。

第二类是凸优化算法或最优化逼近方法，这类方法通过将非凸问题转化为凸问题求解找到信号的逼近，其中最常用的方法为基础追踪算法（BP，Basic Pursuit），该算法提出使用l1范数替代l0范数来解决最优化问题，以便使用线性编程方法来执行。另一种算法为FOCUSS算法[21]，该算法使用lp范数（p

其他算法：这类方法有的要求信号的采样支持通过分组快速测试重建，如傅立叶采样，链式追踪和HHS(Heavg Hitters On Steroids)追踪。有的将贪婪算法和最优化算法相结合，如文献[30]提出的贝叶斯追踪算法(BPA)，算法将简单的贪婪追踪算法和最优化贝叶斯框架相结合，在信号的稀疏表示中找到有效的原子。BPA可以看作是对迭代检测估计(IDE,Iterative Detection Estima-tion)算法的修改。2.2 l1范数凸优化算法

基于l1范数凸优化算法的稀疏重构模型主要有两类[31]：

(LS)minyxxx2s..tx1和

(BPminx1s..t)yx2（6）

SpaRSA(sparse reconstruction by separable。GPSR算法通过使用梯度降的方法求解有界约束最优化问题，算法要求投影在可行域中以确保迭代过程的可行性。第三类算法是基于贝叶斯框架提出的重构算法，该类算法考虑到了信号的时间相关性，特别是当信号具有较强的时间相关性时，能够提供

其中，(LS)式为LASSO(Least Absolute Shrinkage and Selection Operator)问题[32]，(BP)式为基追踪去噪(Basis Pursuit Denoise, BPDN)问题[33], 当没有噪声时，就退化为单一的基追踪(BP)问题[34]。处理实际问题时，通过对系统测量条件的分析，可以得到噪声水平σ的大致估计。相比之下，要先验地估计原信号的l1范*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

数值τ是十分困难的，因此研究(BP)问题的求解更具有实际意义，但是(LS)问题可以作为求解(BP)问题的中间手段。

求解形如(LS)和(BP)的约束优化问题时，可将约束条件转换为惩罚项，构造非约束优化问题。即：

2x冗余的。匹配追踪的任务就是通过每一次匹配把待分析信号f(t)分解成库中一组成员gi(t)(i=1,2,…,N)的线性组合，且N越小越好，实际就是通过对一系列单一原子进行逼近的方法来逐步搜索信号的稀疏解。

匹配跟踪算法虽然简单，但由于它找到的是OMP是恢复稀疏信号算法中较早出现的一类算空间上克服了上述缺陷。

基于压缩感知理论，OMP算法可以通过已知的关于信号的O(mlnd)个随机线性测量来恢复d维空间中的信号。假设S是Rd 空间的k-稀疏信号，Ф为n×d维测量矩阵，列向量为φ1 到φd。数据向量v（v＝Фs）的列是从Ф中选取的某些列的组合。

算法的基本思想源于K-稀疏，是为了找到K个关键的分量，既然是关键，显然它的绝对值应该比其他（N－K）个分量大的多。基于上面的假设，算法就是要从测量矩阵Ф中找到参与信号x测量的列向量。方法是：设置一个剩余向量r和序号集合Λ，在每一次迭代中，从Ф中选出与数据v剩下部分即余量r最相关的那一列，将该列号添加到集合Λ中并从数据v中去掉该列所作的贡献并重新计算余量，直到m次迭代结束。算法最终会得到正确的列序号集合Λ以及数据v的N维近似值am和N维余量rm。需要注意的是，迭代过程中余量rt始终和Фt 的列向量正交。具体的算法可以参考文献[15]。

文献[15]中Tropp和Gilbert分析了OMP算法执行的性能，提出了合适的测量矩阵为N×d维随机矩阵，且具有（M0）独立性、（M1）归一化、（M2）联合相关性和（M3）最小奇异值四个性质。文献[36]也证明了当测量矩阵Ф满足RIP条件时（其中参数k11/(12K)）,OMP算法可通过K个步骤精确地恢复任意K-稀疏信号。同时该文对OMP算法进行了改进，提出了MOMP

逼近结果的稀疏度较差。(QP)minyx2x(7)

次优解，故算法收敛慢、事实上，（QP）问题中的控制参数λ可视为求解约束优化问题(LS)和(BP)中的拉格朗日乘数。因此，若参数σ、λ和τ选取合适，以上三个问题的解是一致的。其中（QP）问题是一个二阶锥规划(second-order cone program)问题，可利用内点法(interior-point)[9,35]求解。

文献[11]比较了各种不同的恢复算法，总结出了l1凸优化算法，如LASSO或BPDN[33,36]

法，通过把信号矢量投影到由选取原子张成的子，通过求解式（8）可以在稀疏计算的复杂度和精度之间提供最佳的平衡点。

minx12yx2x(8)2迭代阈值技术（iterative thresholding algorithm）在稀疏优化算法中经常被采用，一些迭代阈值算法被用在解决LASSO问题上，可以使迭代过程中每一次迭代的计算量减小，这样就可以将LASSO用于解决高维方面的问题[8]。在迭代阈值技术中，迭代收缩算法解决

[20]凸优化问题十分有效，包括IHT [19]、GraDeS、PCD(parallel coordinate descent)以及FISTA(fast-iterative-shrinkage thresholding algorithm)等。对于IHT和GraDes算法，由于该算法使用负梯度作为搜索方向，即Landweber迭代，所以造成算法执行效率偏低。2.3 贪婪算法

MP算法最初是Mallat等人在1993年提出的匹配追踪算法，基本原理就是首先建立一个来分析信号的基本库函数D，不要求库中所有基本函数gi(t)（也叫“原子”）相互正交，但要求其二范数||gi(t)||2=1。因此这组函数并非相互独立，是有*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

（multi-candidate OMP）算法。该算法对OMP的改进在于：在每一次的迭代中，OMP算法只选择一个候选列加入到原子集合中，而MOMP算法选择多个候选列加入到最优原子集合，从而减少迭代的次数，降低重构信号的计算复杂度。文献[34]中，Rauhut研究了使用傅里叶矩阵作为测量矩阵的OMP算法的执行性能，通过大量的试验，他们证明了通过O(Klog(n))个测量就可以精确的恢复K-稀疏信号。同时，Kunis和Rauhut提出，对于m-稀疏信号给出的O（mlnd）次测量，在第一次迭代中，OMP方法可以从测量矩阵中选出正确的列，但是由于矩阵列向量之间存在的微小随机相关性，很难对OMP算法后续的迭代进行分析。于是D.Needell 和 R.Vershynin就在文献[17]中提出了对OMP算法的改进，称为ROMP算法（Regularized Orthogonal Matching Pursuit），该算法可以通过选择替代信号的最大元素并采用正则化的方式来确保没有太多的错误元素被选择，ROMP算法比OMP算法更快速且重构结果更加均衡稳定。文献[37]中Nam H.Nguyen和Trac D.Tran使用ROMP方法从含噪测量中稳定地重构可压缩信号。Donoho也在文献[16]中提出了分段OMP算法(stagewise orthogonal matching pursuit)，该算法对OMP算法进行了简化，通过设置阈值的方法来找到替代的信号，同时以逼近精度为代价进一步提高了计算速度，更适合求解大规模问题。除此之外，2005年Chinh和Minh提出了树型正交匹配算法[38]（TOMP, Tree-based Orthogonal Matching Pursuit），该算法是通过构造稀疏树并在树中追踪重要的系数来实现的。TOMP算法考虑到了信号的多尺度分解时稀疏信号在各奇异子带位置的关系，从而构建了比BP和OMP算法更加快速且重构精度更高的算法。

压缩感知追踪算法（CoSaMP,Compreed Sampling Matching Pursuit）是最近由Needell和Tropp提出的[18]，和大多数贪婪算法一样，CoSaMP算法采用了正交测量矩阵Ф（Ф*TФ近似归一化），因此算法中的替代信号p = Ф*TФS的最大元素与S的非零输入相关联。算法的执行是将p的最大元素加入到运行支撑集中，并使用最小二乘法来获取信号的估计。最后，修正最小二乘估计并更新错误余量。2.4 一些新想法

最近，很多学者提出了一些新想法，其中之一就是将消息传递用于解决压缩感知的信号重构问题。其中，Donoho等提出了一种算法称之为AMP（approximate meage paing）[39]，这种算法既具有迭代阈值算法的低复杂度，同时也具备基追踪算法较强的信号重构能力。事实上，AMP是将一些广泛采用的算法集合成的一个实例，是一类新的低复杂度迭代阈值算法，用于解决从较少的线性测量中重构稀疏信号的问题。

考虑式子：

yAS0,S0RN,y,wRn

(9)

其中S0是稀疏向量，ω为噪声。一般的AMP算法的迭代公式如下：

xt10(xtATzt;t)zyAx

ttItnzt(10)

x和z的初始值为x0=0,z0=y，其中，0(x;)(x)sign(x)属于软阈值函数；It 是xt的有效集合。具体的迭代算法和一些相关算法可参见文献[39-44]，这里就不再详述。算法对比及特点评述

BP算法的优势在于它可以当作线性编程问题来解决，因而可以使用标准的技术软件来处理。但是在实际应用中，对于稀疏信号的重构，商业化的软件并不能很好的工作，因为解向量是稀疏的，而测量向量是稠密的，所以即使是常见的图像尺寸，计算也相当耗时且执行复杂度很高。除此之外，由于l1范数无法区分稀疏尺度的位置，所以尽管整体上重构信号在*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

欧氏距离上逼近原信号，但存在低尺度能量搬移到高尺度的现象，从而容易出现一些人工效应，如一维信号会在高频出现振荡。

贪婪算法是CS重构算法中使用比较频繁的一类算法（主要为OMP算法及其改进算法），基本思想是根据残差向量与测量矩阵之间相关性最大的分量，逐步找到原信号的支撑集，并在与信号支撑集相对应的子矩阵上进行类似于最小二乘的计算。该算法较凸优化算法来说，大大提高了计算效率，同时在算法中可以加入额外的先验信息，提高了重构信号的精度。如基于模型的压缩感知方法[45](model based compreed sensing）和前面提到过的贝叶斯压缩感知方法（BCS）。其中BCS算法借助传统的贝叶斯方法与机器学习中的主动学习方法,将关于稀疏性的先验信息用垂直先验分布来建模，提出了自适应的感知方法以及相应的恢复方法。而基于模型的压缩感知方法利用小波树模型和块稀疏模型，仅需要与稀疏程度相当的测量数目即可实现信号的鲁棒性恢复[46]。

当信号稀疏性不是很好且测量中噪声较大时，贪婪算法效果没有凸优化算法好。同时，贪婪算法中涉及到的最小二乘过程要进行矩阵求逆，需大量的矩阵-向量乘法，当算子Φ存在快速算法时也难以应用。近两年，随着梯度投影、迭代阈值等算法的出现，最小l1范数方法的计算效率大幅度提高，同时还可以充分利用算子Φ的快速算法。

CS重构算法各有优缺点，在设计算法时，应根据所应用的领域和信号的特点来进行选择。主要目的是配合CS测量矩阵尽可能减少测量数据并保证重构信号的精度，同时根据需求进行合理权衡。的对于信号重构所采用的最小二乘优化算法已经不够充分，采用不同方式的凸优化算法和贪婪算法来重构信号是压缩感知研究的一个重点。本文对压缩感知理论的框架做了一个简单的描述，着重放在了对压缩感知重构算法的综述上，主要介绍了一些常用的CS重构算法如贪婪算法、凸优化算法等，同时对各算法的特点进行了评述。纵观现在的压缩算法，可以看出今后对于压缩算法的改进主要集中在三个方面：1）构造更稳定、计算复杂度低且需要较少的观测次数的重构算法来精确地恢复可压缩信号；2）构造有效的重构算法来精确恢复含噪信号或在采样过程中被引入噪声的信号；3）将理论与实际相结合，根据特定的领域或应用构造具有针对性的有效可行的压缩算法。参考文献

[1] D L Donoho．Compreed sensing[J].IEEE Transactions on Information Theory.2006,52(4): 1289-1306.[2] 石光明,刘丹华,高大化.压缩感知理论及其研究进展[J].电子学报.2009, 37:1070-1081.[3] Richard G.Baraniuk.Compreive Sensing[J], IEEE Signal Proceing Magazine, 2007:118-124.[4] Emmanuel J.Candès, Michael B.Wakin.An Introduction To Compreive Sampling[J].IEEE Signal Proceing Magazine,2008,25(2):21-30.[5] I.Daubechies, Ten Lectures on Wavelets.New York:SIAM, 1992.[6] S.Mallat, A Wavelet tour of signal proceing, the sparse way, 2009.[7] Emmanuel J.Candès, Justin Romberg, Terence Tao.Stable Signal Recovery from Incomplete and Inaccurate Measurements[J].Communications on Pure and Applied Mathematics, 2006,59(8):1207-1223.[8] E.Cand`es and D.Donoho, New tight frames of curvelets and optimal representations of objects 4 结束语

对于稀疏信号或可压缩信号来说，压缩感知理论作为一种新的信号获取方式，比传统的采样方式更加有效。在压缩感知理论中，传统*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

with piecewise singularities, Comm.Pure Appl.Math.vol.57, pp.219-266, 2004.[9] D.D.-Y.Po and M.N.Do, Directional multiscale modeling of images using the contourlet transform, IEEE Transactions on Image Proceing, vol.15(6), pp.1610–1620, 2006.[10] R.Baraniuk, M.Davenport, R.DeVore, and M.Wakin.A simple proof of the restricted isome-try property for random matrices.Constructive Approximation, 2007.[11] E.Cand`es.The restricted isometry property and its implications for compreed sensing.Compte Rendus de l’Academie des Sciences, Paris, 2008.[12] E.Cand`es and T.Tao.Near optimal signal recovery from random projections: Universal encoding strategies.IEEE Transactions on Information Theory, vol.52, pp.5406-5425, 2006.[13] Jérome Bobin, Jean-Luc Starck, Roland Ottensamer.Compreed Sensing in Astronomy[J].IEEE Journal of Selected Topics in Signal Proceing, 2008,2(5):718-726 [14] Emmanuel J.Candès.Compreive sampling [A].Proceeding of the International Congre of Mathematicians[C].Madrid, Spain, 2006, 3: 1433-1452.[15] Joel A.Tropp, Anna C.Gilbert.Signal Recovery From Random Measurements Via Orth-ogonal Matching Pursuit[J].IEEE Transactions on Information Theory.2007, 53(12): 4655-4666.[16] D.L.Donoho,Y.Tsaig, I.Drori, and J.L.Starck, “Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit” Stanford Statistics Technical Report 2006-2, 2006.[17] D.Needell and R.Vershynin, “Uniform uncertainty principle and signal recovery via regularized orthogonal matching

pursuit,”

Foundations of Computational Mathematics, vol.9,no.3, pp.317–334, 2009.[18] Needell, D.,Tropp, J.A.CoSaMP: Iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis, 2009,26(3):301-321.[19] T.Blumensath and M.E.Davies, “Iterative hard thresholding for compreed sensing,” Applied and Computational Harmonic Analysis, vol.27, no.3, pp.265–274, 2009.[20] R.Garg and R.Khandekar, “Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property,” in Proceedings of the 26th International Confer-ence on Machine Learning, pp.337–344, 2009.[21] I.F.Gorodnitski and B.D.Rao, Sparse signal reconstruction from limited data using focu: a re-weighted norm minimization algorithm[J].IEEE Transactions on Signal Proceing, 1997,45(3):600 –616.[22] H.Mohimani, M.Babaie-zadeh, and C.Jutten.A fast approach for overcomplete sparse decomposition based on smoothed l0-norm[J].IEEE Transactions on Signal Proceing, 2009, 57(1):289–301.[23] Figueiredo, M.A.T., Nowak, R.D., Wright, S.J.Gradient projection for sparse reconstruction: Application to compreed sensing and other inverse problems[J].IEEE J.Sel.Top.Sign.Proces: Special Iue on Convex Optimization Methods for Signal Proceing, 2007,1:586-597.[24] S.J.Wright, R.D.Nowak, and M.A.T.Figueiredo, “Sparse reconstruction by separable approximation,” IEEE Transactions on Signal Proceing, vol.57, no.7, pp.2479–2493, 2009.[25] H.Zayyani, M.Babaie-zadeh, C.Jutten.Decoding real-field codes by an iterative expectation-maximizaion algorithm[A].ICASSP [C], 2008, pp.3169–3172.[26] S.Ji, Y.Xue, and L.Carin.Bayesian *基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:waterblue_333@opt.ac.cn

compreive sensing[J].IEEE Transactions on Signal Proceing, 2008,56(6):2346–2356.[27] D.P.Wipf and B.D.Rao, “Sparse Bayesian learning for basis selection,” IEEE Trans.on Signal Proceing, vol.52, no.8, pp.2153–2164, 2004.[28] D.P.Wipf and B.D.Rao, “An empirical Bayesian strategy for solving the simultaneous sparse approximation problem,” IEEE Trans.on Signal Proceing, vol.55, no.7, pp.3704–3716, 2007.[29] Z.Zhang and B.D.Rao, “Sparse signal recovery in the presence of correlated multiple measurement vectors,” in Proc.of the 35th International Conference on Acoustics, Speech, and Signal Proceing(ICASSP 2010), Texas, USA, 2010, pp.3986–3989.[30] H.Zayyani, M.Babaie-Zadeh, C.Jutten.Bayesian Pursuit Algorithm

for

Sparse Representation[A].IEEE Int.Conf.on Acoustics, Speech, and Signal Proceing(ICASSP)[C].Taipei, Taiwan, April 2009.[31] 刘吉英.压缩感知理论及在成像中的应用[D].国防科技技术大学研究生院博士学位论文, 2010 [32] R.Tibshirani.Regreion shrinkage and selection via the Lao[J].J.Roy.Statist.Soc.Ser.B., 1996, 58: 267-288 [33] S.S.Chen, D.L.Donoho, M.A.Saunders.Atomic decomposition by basis pursuit[J].SIAM Rev., 2001, 43: 129-159 [34] S.Kunis, H.Rauhut.Random sampling of sparse trigonometric polynomials ii-orthogonal matching pursuit versus basis pursuit[OL].http://dsp.rice.edu/cs.[35] E.J.Candes.l1-magic[EB/OL].[2011-09-29].http://www.daodoc.com