摘 要：信号采样是联系模拟信源和数字信息的桥梁。人们对信息的海量需求造成了信号采样、传输和存储的巨大压力。如何缓解这种压力又能有效提取承载在信号中的有用信息是信号与信息处理中急需解决的问题之一。近年来，新兴的压缩感知理论为数据采集技术带来了革命性的突破，得到了研究人员的广泛关注。压缩感知采用非自适应线性投影来保持信号的原始结构，能通过求解最优化问题准确重构原始信号。本文综述了CS(Compressed Sensing)基本理论框架及关键技术，并重点介绍了重构算法及其在信号重构方面的应用。

　　关 键 词：压缩感知;采样定理;稀疏表示;观测矩阵;信号重构 1 引 言传统的信号获取和处理过程主要包括采样、压缩、传输和解压缩四个部分。其采样过程必须满足香农采样定理。在信号压缩中，先对信号进行某种变换，然后对少数绝对值较大的系数进行压缩编码，舍弃零或接近于零的系数，通过对数据进行压缩，舍弃了采样获得的大部分数据，但不影响“感知效果”。

　　然而随着人们对信息需求量的增加，携带信息的信号带宽越来越宽，以此为基础的信号处理框架要求的采样速率和处理速度也越来越高,因而对宽带信号处理的困难在日益加剧。

Candés等在2004年从数学上证明了可以从部分傅立叶变换系数精确重构原始信号，为压缩感知奠定了理论基础。Candés和Donoho在相关研究基础上于2006年正式提出了压缩感知的概念。压缩感知理论与传统奈奎斯特采样定理不同，它指出，只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号。在该理论框架下，采样速率不决定于信号的带宽，而决定于信息在信号中的结构和内容。 2、压缩感知理论框架简介压缩感知理论指出，设长度为N的信号X在某组正交集或紧框架上的变化系数是稀疏的，如果我们用一个与变化基不相关的观测基：对系数向量进行线性变换，并得到观测集合：。那么就可以利用优化求解方法从观测集合中精确或高概率地重构原信号X。

　　压缩感知理论是一种新的在采样的同时实现压缩目的的理论框架，其压缩采样过程如图1所示。

　　图1 压缩感知理论框架

首先，如果信号在某个正交基或紧框架上是可压缩的，求出变化系数，是的等价或逼近的稀疏表示;第二步，设计一个平稳的、与变换基不相关的维的观测矩阵，对进行观测得到观测集合，该过程也可以表示为信号X通过矩阵进行非自适应观测：(其中);最后利用范数(非零元素的个数)意义下的优化问题求解X的精确或近似逼近：

求得的向量在基上的表示最稀疏。

压缩感知理论主要涉及以下几个方面的内容：(1)对于信号，如何找到某个正交基或紧框架，使其在上的表示是稀疏的，即信号的稀疏表示问题。(2)如何设计一个平稳的、与变换基不相关的维的观测矩阵，保证稀疏向量从N维降到M维时重要信息不遭破坏。(3)如何设计快速重构算法，从线性观测中恢复信号，即信号重构问题。

　　2.1、信号的稀疏表示

稀疏的数学定义[4]：信号X在正交基下的变换系数向量为，假如对于和，这些系数满足：

则说明系数向量在某种意义下是稀疏的。另一种定义[1]：如果变换系数的支撑域的势小于等于K，则可以说信号X是K-稀疏的。

　　如何找到信号最佳的稀疏域?这是压缩感知理论应用的基础和前提，只有选择合适的基表示信号才能保证信号的稀疏度，从而保证信号的恢复精度。在研究信号的稀疏表示时，可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Candés和Tao研究表明，满足具有幂次(power-law)速度衰减的信号，可利用压缩感知理论得到恢复，并且重构误差满足：

其中。

　　光滑信号的Fourier系数、小波系数、有界变差函数的全变差范数、振荡信号的Gabor系数及具有不连续边缘的图像信号的Curvelet系数等都具有足够的稀疏性，可以通过压缩感知理论恢复信号[6]。

　　2.2、观测矩阵的设计

压缩感知理论中，通过变换得到信号的稀疏系数向量后，需要设计压缩采样系统的观测部分，它围绕观测矩阵展开。观测器的设计目的是如何采样得到M个观测值，并保证从中能重构出长度为N的信号X或者基下等价的稀疏系数向量。显然，如果观测过程破坏了X中的信息，重构是不可能的。观测过程实际就是利用观测矩阵的M个行向量对稀疏系数向量进行投影，即计算和各个观测向量之间的内积，得到M个观测值，记观测向量，即

在这里，采样过程是非自适应的，也就是说，无须根据信号而变化，观测的不再是信号的点采样而是信号的更一般的K-线性范函。对于给定的Y从上式中求出是一个线性规划问题，但由于，即方程的个数少于未知数的个数，这是一个欠定问题，一般来讲无确定解。然而，如果具有K-稀疏性()，则该问题有望求出确定解。此时，只要设法确定出中的K个非零系数的合适位置，由于观测向量Y是这些非零系数对应的K个列向量的线性组合，从而可以形成一个的线性方程组来求解这些非零项的具体值。对此，有限等距性(Restricted Isometry Property, RIP)给出了存在确定解的充要条件。对于任意K稀疏信号X和常数，如果

成立，其中为中由索引T所指示的相关列构成的大小为的子矩阵，则称矩阵满足约束等距性。

这个充要条件和Candés、Tao等人提出的稀疏信号在观测矩阵作用下必须保持的几何性质相一致。即，要想使信号完全重构，必须保证观测矩阵不会把两个不同的K-项稀疏信号映射到同一个采样集合中，这就要求从观测矩阵中抽取的每M个列向量构成的矩阵是非奇异的。可以看出，问题的关键是如何确定非零系数的位置来构造一个可解的线性方程组。

然而判定给定的是否具有RIP性质是比较复杂的，为降低复杂度，能否找一种易于实现RIP条件的替代方法成为构造观测矩阵的关键。

如果保证观测矩阵和稀疏基不相干，则在很大概率上满足RIP性质。不相干是指向量不能用稀疏表示[15]。不相干性越强，互相表示时所需的系数越多;反之，相关性越强。

通过选择高斯随机矩阵作为即可高概率保证不相干性和RIP性。如，可以生成多个零均值、方差为的随机高斯函数，将它们作为观测矩阵的元素，使得以很高的概率具有RIP性质。随机高斯矩阵有个有用的性质：对于一个的随机高斯矩阵，可以证明当时在很大概率下具有RIP性质(c是一个很小的常数)。总之，随机高斯矩阵与大多数固定正交基构成的矩阵不相关。这一特性决定了选它作为观测矩阵，其它正交基作为稀疏变换基时，满足RIP性质。因此，可以从M个观测值中以很高的概率去恢复长度为N的K-项稀疏信号X。其他能使传感矩阵满足约束等距性的测量矩阵还有一致球矩阵、二值随机矩阵、局部傅立叶矩阵、局部哈达玛矩阵以及托普里兹矩阵等。

　　2.3、信号重构

信号重构是压缩感知理论的重要部分。为更清晰地描述压缩感知理论的信号重构问题，首先定义向量的p-范数为

当时得到0-范数，它实际上表示X中非零项的个数。于是，在信号系数或可压缩的前提下，求解欠定方程组的问题转化为最小0-范数问题。但是，它需要列出X中所有非零项位置的种可能的线性组合，才能得到最优解。因此，求解最小0-范数问题的数值计算极不稳定而且是NP难问题。鉴于此，研究人员提出了一系列求得次最优解的算法，主要包括最小范数法、匹配追踪(Matching Pursuit, MP)系列算法、迭代阈值法(Iterative Shrinkage/Threshold, IST)以及专门处理二维图像问题的最小全变分法(Total Variation, TV)等，其中最小范数法和迭代阈值法属于将非凸问题转化为凸问题的凸松弛法。

2.3.1 最小范数法

Chen，Donoho，Saunders指出，求解一个更加简单的优化问题会产生同等的解：

使得问题变成了一个凸优化问题，于是可以方便地化简为线性规划问题，典型算法代表：基追踪(Basis Pursuit, BP)算法，计算复杂度的量级为。若考虑重构误差，上述问题可以转换为如下最小范数问题，

　　或者经典形式：

最小范数问题也可以转化为求解Lagrangian函数形式：

　　或著名的LASSO(Least Absolute Shrinkage andSelection Operator)问题：

最优化理论证明，当参数满足一定的关系时，这三个问题的求解是等价的。

　　2.2.2 匹配追踪法

匹配追踪算法是一种贪婪迭代算法，其基本思想在每一次的迭代过程中，从过完备原子库中(测量矩阵)选择与信号最匹配的原子(列向量)来构建稀疏逼近，并求出与信号的残差，然后继续选择与信号残差最为匹配的列向量，经过一定次数的迭代，信号可以由一些原子线性表示。但是由于信号在已选定原子集合上的投影的非正交性使得每次迭代的结果可能是次最优的，因此为获得收敛可能需要经过较多次迭代。正交匹配追踪算法(Orthogonal Matching Pursuit, OMP)则有效克服了这个问题，该算法沿用了匹配追踪算法中的原子选择规则，只是通过递归地对已选择原子集合进行正交化以保证迭代的最优性，从而减少了迭代次数。实验表明[13]对固定K稀疏N维离散时间信号x，用一个的高斯矩阵测量时，只要，正交匹配追踪算法以极大概率准确重构信号，而且比最小范数法更快。但是，正交匹配追踪算法精确重构的理论保证比最小范数法弱，并非对所有信号都能准确重构，而且对于测量矩阵的要求比约束等距性更加严格。Needell等在OMP基础上提出了正则正交匹配追踪(Regularized Orthogonal Matching Pursuit, ROMP)算法，对所有满足约束等距性条件的矩阵和所有稀疏信号都可以准确重构。另外，压缩采样匹配追踪算法(Compressive Sampling Matching Pursuit, CoSaMP)也可以用于很好地重构信号，提供了比OMP、ROMP更全面的理论保证，并且能在采样过程中对噪声鲁棒。

　　2.2.3 迭代阈值法

　　IST算法的思想最先在基于小波域图像重建的最大期望值算法中提出。其形式如下：

时为最初的表示形式。其中是阈值函数，给定阈值，则

　　或

　　阈值函数的选择主要看值较大的系数，经过函数后是否保持不变。在IST算法的基础上，之后出现了提高其速度的TwIST(Two-Step IST)算法和FIST(Fast IST)算法，它们的迭代形式在IST的基础上改进如下：

TwIST:

FIST:

其中。

　　2.2.4 最小全变分法

相对于适合一维信号重构的最小范数法，Candés等从大量自然图像的离散梯度都是稀疏的角度出发，提出了更适合二维图像重构的最小全变分法。图像压缩传感的全变分模型如下：

目标函数为图像离散梯度之和，即

　　该问题的求解可以转换为二阶锥规划问题。最小全变分模型可以有效地解决图像压缩传感重构问题，结果精确而且鲁棒，但运算速度较慢。 3、压缩感知理论在信号处理中的应用上述对压缩感知理论框架进行了简要的介绍，重点介绍了其信号重构部分一些近来的经典算法。下面将针对一维信号和二维图像的重建问题，利用这些算法实现如下：

　　1) TwIST：

　　图2 原始图像 图3 模糊并加噪图像

　　图4 TwIST恢复图像图5 模糊图像

图6 恢复图像(归一化函数为全变分模型)图7f 一维信号重构(归一化函数为范数)

　　2)基于小波变换的OMP算法：

　　图8 信号重构采样图 图9 原始图像

　　图10 小波变换后的图像图11 恢复的图像 4、结语本文介绍了CS基本理论框架及关键技术，重点对压缩感知理论中的信号重构的各种算法及其在信号重构方面的应用进行了具体的研究，但压缩感知理论在国外还处于一个发展阶段，国内的研究基本上只停留在应用阶段。压缩感知理论的研究已经有了一些成果,但是仍

　　然存在大量的问题需要研究.概括为以下几个方面：(1)对于稳定的重构算法是否存在一个最优的确定性的观测矩阵;(2)如何构造稳定的、计算复杂度较低的、对观测次数限制较少的重构算法来精确地恢复可压缩信号;(3)如何找到一种有效且快速的稀疏分解算法是冗余字典下的压缩感知理论的难点所在;(4)对于p-范数优化问题的求解研究还远远不够。

　　压缩感知理论是新诞生的,虽然还有许多问题待研究,但它是对传统信号处理的一个极好的补充和完善,是一种具有强大生命力的理论,其研究成果可能对信号处理等领域产生重大影响 5、参考文献[1] E Candés. Compressive sampling[A]. Proceedings of the International Congress of Mathematicians [C], Madrid, Spain, 2006, 3:1433-1452.

　　[2] E Candés, J Romberg, Terence Tao. Robust uncertainty principle: Exact signal reconstructionfrom highly incompletefrequency information [J]. IEEE Trans. on Information Theory, 2006, 52 (2): 489-509.

　　[3] E Candés, J Romberg. Quantitative robust uncertainty principles and optimally sparse decompositions [J], Foundations of Comput Math, 2006, 6 (2): 227-254.

　　[4] D L Donoho. Compressed sensing [J]. IEEE Transactions On Information Theory. 2006, 52 (4): 1289-1306.

　　[5] D L Donoho, Y Tsaig. Extensions of compressed sensing [J]. Signal Proscessing, 2006, 86 (3): 533-548.

　　[6] E Candés, T Tao. Near optimal signal recovery from random projections: Universal encoding strategies [J]. IEEE Transactions Information Theory, 2006, 52 (12): 5406-5425.

　　[7] D Needell, J Tropp. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples [J]. Appl Comp Harmonic Anal, 2009, 26 (3): 301-321.

　　[8] M A T Figueiredo, R D Nowak, S J Wright. Gradient projection for sparse reconstruction:Application to Compressed Sensing and Otherinverse problem [J]. Journal of Selected Topics in Signal Processing: Special Issue on Convex Optimization Methods for Signals Processing, 2007, 1 (4): 586-598.

　　[9] M A Figueiredo,RD Nowak. An EM algorithm for wavelet-based image restoration,IEEE Transactionson Image Processing, 12 (2003):906-916.

　　[10] J M Bioucas-Dias, and M A T Figueiredo.A New TwIST: Two-Step IterativeShrinkage/ThresholdingAlgorithms for Image Restoration, IEEE Transactions on Image Processing, 2007, 16 (12), 2992-3004.

　　[11] A. Beck, M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linearinverse problems, SIAM J. on Imaging Sciences, 2009.

　　[12] E.Candés, L. Demanet, D. Donoho, L. Ying, Fast discrete curvelet transforms,Mul-tiscale Model. Simul. 20065 (3):861-889.

　　[13] J A Tropp, and A C Gilbert. Signal Recovery from Random Measurementsvia Orthogonal Matching Pursuit, 2007, 53(12), 4655-4666.

　　[14] J M Bioucas-Dias, and M A T Figueiredo.TwIST matlab toolbox, 2007.

　　[15] R Baraniuk. Alecture on compressive sensing [J]. IEEE Signal Processing Magazine, 2007, 24(4): 118-121.