论文部分内容阅读
摘要：信号采样是模拟的物理世界通向数字的信息世界的必备手段。多年来，指导信号采样的理论基础一直是著名的Nyquist采样定理，但其在采样过程中产生的大量数据浪费了存储空间，而在压缩过程又会丢弃大量采样资源。压缩感知（Compressed Sensing）提出一种新的采样理论，它能够以远低于Nyquist要求的采样速率采样信号。本文详述了压缩感知的基本理论，着重介绍了信号稀疏变换、观测矩阵设计和重构算法三个方面的最新进展，并介绍了压缩感知目前有待解决的几个关键问题，最后举例说明压缩感知理论在各领域的应用。
关键词：压缩感知；稀疏变换；观测矩阵；有限等距性；编码；解码
中图分类号：TN957.52
0 引言
Nyquist采样定理指出，采样速率达到信号带宽的两倍以上时才能实现采样信号的精确重构。可见，带宽是Nyquist采樣定理对采样的本质要求。然而随着信息需求量的增加，携带信息的信号带宽越来越宽，以此为基础的信号处理框架所要求的采样速率和处理速度也越来越高。解决这些压力常见的方案是信号压缩。但是，信号压缩会浪费大量采样资源，因为大量非重要或冗余信息在压缩过程中被丢弃。基于此可以得出结论：带宽不能本质地表达信号的信息，基于Nyquist采样定理的采样机制是冗余的。
于是很自然地引出一个问题：能否利用其它变换空间描述信号，建立新的信号描述和处理的理论框架，使得在保证信息不损失的情况下，用远低于Nyquist采样定理要求的速率采样信号，同时又可以完全恢复信号。与信号带宽相比，稀疏性能够直观地而且相对本质地表达信号的信息。事实上，稀疏性在现代信号处理领域起着至关重要的作用。近年来基于信号稀疏性提出一种称为压缩感知新兴采样理论，成功实现了信号的同时采样与压缩。
简单地说，压缩感知理论指出：只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。在该理论框架下，采样速率不再取决于信号的带宽，而在很大程度上取决于两个基本准则：稀疏性和等距约束性。事实上，压缩感知理论的某些抽象结论源于Kashin创立的范函分析和逼近论 ，由Candes ，Romberg ，Tao 和Donoho 等人构造了具体的算法并且通过研究表明了这一理论的巨大应用前景。目前国内已经有科研单位的学者对其展开研究，如西安电子科技大学课题组基于该理论提出采用超低速率采样检测超宽带回波信号 。
显然，在压缩感知理论中，图像/信号的采样和压缩同时以低速率进行，使传感器的采样和计算成本大大降低，而信号的恢复过程是一个优化计算的过程.因此，该理论指出了将模拟信号直接采样压缩为数字形式的有效途径。从理论上讲任何信号都具有可压缩性，只要能找到其相应的稀疏表示空间，就可以有效地进行压缩采样。
当前，压缩感知理论主要涉及三个核心问题：
（1） 具有稀疏表示能力的过完备字典设计；
（2） 满足非相干性或等距约束性准则的测量矩阵设计；
（3） 快速鲁棒的信号重建算法设计。
压缩感知理论必将给信号采样方法带来一次新的革命。这一理论的引人之处还在于它对应用科学的许多领域具有重要的影响，如统计学、信息论、编码 等。目前，学者们已经在模拟-信息采样、合成孔径雷达成像、遥感成像、核磁共振成像、深空探测成像、无线传感器网络、信源编码、人脸识别、语音识别、探地雷达成像等诸多领域对压缩感知展开了广泛的应用研究。Rice大学已经成功设计出了一种基于压缩感知的新型单像素相机，在实践中为取代传统相机迈出了实质性的一步。
本文围绕稀疏字典设计、测量矩阵设计、重建算法设计三个核心问题，综述了压缩感知理论以及与之相关的信号稀疏变换、观测矩阵设计、重构算法等一系列最新理论成果和应用研究，描述了国内外的研究进展。
1 压缩感知理论框架
传统的信号采集、编解码过程如图l所示：编码端先对信号进行采样，再对所有采样值进行变换，并将其中重要系数的幅度和位置进行编码，最后将编码值进行存储或传输：信号的解码过程仅仅是编码的逆过程，接收的信号经解压缩、反变换后得到恢复信号。采用这种传统的编解码方法，由于信号的采样速率不得低于信号带宽的两倍，使得硬件系统面临着很大的采样速率的压力。此外在压缩编码过程中，大量变换计算得到的小系数被丢弃，造成了数据计算和内存资源的浪费。
压缩感知理论对信号的采样、压缩编码发生在同一个步骤，利用信号的稀疏性，以远低于Nyquist采样率的速率对信号进行非自适应的测量编码。测量值并非信号本身，而是从高维到低维的投影值，从数学角度看，每个测量值是传统理论下的每个样本信号的组合函数，即一个测量值已经包含了所有样本信号的少量信息。解码过程不是编码的简单逆过程，而是在盲源分离中的求逆思想下。利用信号稀疏分解中已有的重构方法在概率意义上实现信号的精确重构或者一定误差下的近似重构 。解码所需测量值的数目远小于传统理论下的样本数。
2 压缩感知的基本理论
假设有一信号 ，长度为 ，基向量为 ，对信号进行变换：
显然 是信号在时域的表示， 是信号在 域的表示。信号是否具有稀疏性或者近似稀疏性是运用压缩感知理论的关键问题，若（1）式中的 只有 个是非零值 者仅经排序后按指数级衰减并趋近于零，可认为信号是稀疏的。信号的可稀疏表示是压缩感知的先验条件。在已知信号是可压缩的前提下，压缩感知过程可分为两步：
（1）一个与变换基不相关的 维测量矩阵对信号进行观测，得到 维的测量向量。
（2）由 维的测量向量重构信号。 2.1 信号的稀疏表示
文献[4]给出稀疏的数学定义：信号 在正交基 下的变换系数向量为 ，假如对于 和 ，这些系数满足：
则说明系数向量 在某种意义下是稀疏的.文献[1]给出另一种定义：如果变换系数
的支撑域 的势小于等于 ，则可以说信号 是 项稀疏。如何找到信号最佳的稀疏域？这是压缩感知理论应用的基础和前提，只有选择合适的基表示信号才能保证信号的稀疏度，从而保证信号的恢复精度。在研究信号的稀疏表示时，可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Candes和Tao研究表明，满足具有幂次（power-law）速度衰减的信号，可利用压缩感知理论得到恢复。
最近几年，对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解.这是一种全新的信号表示理论：用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子.字典的选择应尽可能好地符合被逼近信号的结构，其构成可以没有任何限制.从从冗余字典中找到具有最佳线性组合的K项原子来表示一个信号，称作信号的稀疏逼近或高度非线性逼近 。
在冗余字典下的稀疏表示的研究集中在两个方面：（1）如何构造一个适合某一类信号的冗余字典；（2）如何设计快速有效的稀疏分解算法.这两个问题也一直是该领域研究的热点，学者们对此已做了一些探索，其中以非相干字典为基础的一系列理论证明得到了进一步改进.西安电子科技大学的石光明教授也对稀疏表示问题进行了认真研究，并基于多组正交基级联而成的冗余字典提出一种新的稀疏分解方法 。
2.2 信号的观测矩阵
用一个与变换矩阵不相关的 测量矩阵 对信号进行线性投影，得到线性测量值 ：
测量值 是一个 维向量，这样使测量对象从 维降为 维。观测过程是非自适应的即测量矩阵少的选择不依赖于信号 。测量矩阵的设计要求信号从 转换为 的过程中，所测量到的 个测量值不会破坏原始信号的信息，保证信号的精确重构。
由于信号 是是可稀疏表示的，上式可以表示为下式：
其中 是一个 矩阵。上式中，方程的个数远小于未知数的个数，方程无确定解，无法重构信号。但是，由于信号是K稀疏，若上式中的 满足有限等距性质（Restricted Isometry Property，简称RIP），即对于任意K稀疏信号 和常数 ，矩阵 满足：
则 个系数能够从 个测量值准确重构。RIP性质的等价条件是测量矩阵 和稀疏基 不相关。目前，用于压缩感知的测量矩阵主要有以下几种：高斯随机矩阵，二值随机矩阵（伯努力矩阵），傅立叶随机矩阵，哈达玛矩阵，一致球矩阵等。
2.3 信号的重构算法
当矩阵 满足RIP准则时。压缩感知理论能够通过对上式的逆问题先求解稀疏系数 ，然后将稀疏度为K的信号 从 维的测量投影值 中正确地恢复出来。解码的最直接方法是通过 范数下求解的最优化问题：
从而得到稀疏系数的估计。由于上式的求解是个NP—HARD问题。而该最优化问题与信号的稀疏分解十分类似，所以有学者从信号稀疏分解的相关理论中寻找更有效的求解途径。文献[10]表明， 最小范数下在一定条件下和 最小范数具有等价性，可得到相同的解。那么上式转化为 最小范数下的最优化问题：
最小范数下最优化问题又称为基追踪（BP），其常用实现算法有：内点法和梯度投影法。内点法速度慢，但得到的结果十分准确：而梯度投影法速度快，但没有内点法得到的结果准确 。二维图像的重构中，为充分利用图像的梯度结构。可修正为整体部分（Total Variation，TV）最小化法。由于 最小范数下的算法速度慢，新的快速贪婪法被逐渐采用，如匹配追踪法（MP）和正交匹配追踪法（OMP）。此外，有效的算法还有迭代阈值法以及各种改进算法。
3 有待解决的几个关键问题
压缩感知经过近年来的迅猛发展，已基本形成了自己的理论框架，包括基础理论、实现方法和实际应用。但是，压缩感知理论还有很多亟待解决的问题，为此本文列出了压缩感知有待解决的几个关键问题。
3.1 基础理论层面
（1）基于非正交稀疏字典的压缩感知信号重建理论。在等距约束性准则驱动的可压缩信号压缩感知定理中，关于稀疏字典 和测量矩阵 仅要求两者乘积 满足RIP。但是，测量矩阵设计部分关于压缩测量个数M 的界定还额外附加了假设条件，即稀疏字典 是正交基。当测量矩阵 依然通过三种方式生成，但是稀疏字典 不再正交时， 是否满足RIP？压缩测量个数M 的下限是否不变？由于过完备的稀疏字典才能保证表示系数具有足够的稀疏性或衰减性，进而能够在减少压缩测量的同时保证压缩感知的重建精度，所以需要设计鲁棒的测量矩阵 使之与过完备稀疏字典依然满足RIP，同时需要重新估计压缩测量个数M 的下限，这时所需的压缩测量定会减少。
（2）自然图像的自适应压缩感知信号重建理论。虽然基于线性投影的压缩感知理论能够直接应用于自然图像这样的复杂高维信号，但是由于没有考虑到自然图像的固有特性，诸如结构多成分性、高阶统计性等，对于自然图像压缩采样本身没有特殊的指导作用。事实上，相对于一维离散信号，自然图像的复杂性和高维性使之需要自适应的压缩采样和重建算法。
例如，基于图像多成分性的特点能够提高重建图像的峰值信噪比和视觉效果。注意到，压缩感知理论的大部分文献中，测量矩阵 都是线性的且设计好的，不需根据观测信号自适应地变化。对于自然图像，假如能够实现非线性自适应的压缩测量，压缩感知的压缩性能势必会获得大幅度的提高。目前，自然图像的自适应压缩感知信号重建理论基本空白。这项工作对压缩感知的理论推广和实际应用都具有重要意义。
3.2 实现方法层面
（1）基于学习的自然图像过完备字典设计。目前，基于构造方法的自然图像过完备字典设计具有很好的理论支撑，正则化几何方法、几何多尺度分析、基于信息论的“有效编码假设”为其奠定了坚实广阔的理论基础。但是，从国际上关于过完备字典设计的整体情况看，基于学习的自然图像过完备字典设计的工作非常少，主要在于：设计难度大、性能要求高，同时缺乏严格的理论支撑。这项工作对于稀疏字典和压缩感知都将是重要的理論完善。 （2） 硬件易实现的确定性测量矩阵设计。在等距约束性准则驱动的可压缩信号压缩感知定理3、4 中，要求稀疏字典 和测量矩阵 的乘积 满足RIP。其中，稀疏字典 可以是正交的也可以是非正交的，测量矩阵 可以是随机的也可以是确定的。但是，面向应用且硬件易实现的测量矩阵应该具有以下基本特点：满足等距约束性、压缩测量个数少、采样计算成本低、存储矩阵的空间小、以及测量矩阵最好是确定性的。设计出硬件容易实现的测量矩阵和快速稳定的重建算法是将压缩感知理论推向实用的关键。
（3） 噪声情形大尺度问题的快速鲁棒重建算法设计。快速稳定的信号重建算法是将压缩感知理论推向实用的关键技术之一，特别适用于纠错编码、核磁共振成像、NMR波谱研究等大尺度问题。通常，基于最小化松弛算法的计算复杂度相对较高。因而，在最小化驱动的压缩感知理论完善工作的基础上，希望能够基于稀疏性自适应的贪婪迭代和基于多层超先验建模的非凸迭代思想设计适于噪声情形大尺度问题的快速鲁棒重建算法。
4 压缩感知的应用
使用一定数量的非相关测量值能够高效率地采集可压缩信号的信息，这种特性决定了压缩感知应用的广泛性。例如低成本数码相机和音频采集设备；节电型音频和图像采集设备；天文观测；网络传输；军事地图；雷达信号处理等等。以下归纳了压缩感知几个方面的应用：
（1） 数据压缩
在某些情况下，稀疏表示在编码中是未知的或在数据压缩中是不能实际实现的。由于测量矩阵西是不需要根据缈的结构来设计的，随机测量矩阵可认为是一个通用的编码方案，而只有在解码或重建信号的时候需要用到。这种通用用性在多信号装置（如传感器网络）的分布式编码特别有用。
（2） 信道编码
压缩感知的稀疏性、随机性和凸优化性，可以应用于设计快速纠错码以防止错误传输。
（3） 逆问题
在其他情况下，获取信号的唯一方法是运用特定模式的测量系统 。然而，假定信号存在稀疏变换基 ，并与测量矩阵 不相关，则能够有效的感知的信号。这样的應用在文献[2]中的MR血管造影术有提到， 记录了傅立叶变换子集，所得到的期望的图像信号在时域和小波域都是稀疏的。
（4） 数据获取
在某些重要的情况下，完全采集模拟信号的N个离散时间样本是困难的，而且也难以对其进行压缩。而运用压缩感知，可以设计物理采样装置，直接记录模拟信号离散、低码率、不相关的测量值，有效地进行数据获取。基于RIP理论，目前已研制出了一些设备，有莱斯大学研制的单像素相机和A/I转换器，麻省理工学院研制的编码孔径相机，耶鲁大学研制的超谱成像仪，麻省理工学院研制的MRI RF脉冲设备，伊利诺伊州立大学研制的DNA微阵列传感器。
5 结论
本文主要阐述了压缩感知理论框架，基于压缩感知理论的编解码模型，以及压缩感知技术的三大核心问题。通过对一维信号编解码的仿真实验说明了压缩感知理论是一种能够使用少量测量值实现信号准确恢复的数据采集、编解码理论。由于压缩感知理论对处理大规模稀疏或可压缩数据具有十分重要的意义。所以该理论提出后在许多研究领域得到了关注。目前，国外研究人员已开始将压缩感知理论用于压缩成像、医学图像、模数转换、雷达成像、天文学、通信等领域。作为国外刚出现的新理论，压缩感知理论的研究方兴未艾，将有着更广泛的应用前景。
参考文献：
[1].石光明，刘丹华，高大化，刘哲，林杰，王良君.压缩感知理论及其研究进展[J].ACTA Electronica Sinica，2009，37（5）：1070-1081.
[2].张锐.基于压缩感知理论的图像压缩初步研究[J].Computer Knowledge And Technology.2012，6（4）：958-959.
[3]. Candes E，Romberg J，Tao T.Robust uncertaintyprinciples：Exact signal reconstruction from highly incomplete frequency information[J].IEEE Trans.Information Theory，2006，52（4）：489-509.
[4]. E Candes，J Romberg.Quantitative robust uncertainty principles and optimally sparse decompositions[J].Foundations of Comput Math，2006，6（2）：227-254.
[5]. Emmanuel J.Candes，Terence Tao.Near-Optimal signal recovery from random projections：Universal encoding strategies[J].IEEE Transaction on Information Theory，2006，52（12）：5406-5425.
[6]. D.L.Donoho.Compressed sensing，2006（04）.
[7]. B Kashin.The widths of certain finite dimensional sets and classes of smooth functions[J].Izv Akad Nauk SSSR，1977，41（2）：334-351.
[8]. E.Candes，M.Wakin.An introduction to compressive sampling[J]. IEEE Signal Processing Magazine 2008，25（2）：21-30. [9]. 喻玲娟，谢晓春.压缩感知理论简介.Video Engineering，2008，32（12）：16-18.
[10].DONOHO D，TSAIG Y.Extensions of compressed sensing[J].Signal Processing，2006，86（3）：533-548.
[11].UWB Echo Signal Detection with Ultra-Low Rate Sampling based on Compressed Sensing[J].IEEE Trans.Circuits and Systems II：Express Briefs，2008，55（4）：379–383.
[12]. 张春梅，尹忠科，肖明霞.基于冗余字典的信号超完备表示与稀疏分解[J].科学通报，2006，51（06），628-633.
[13].V.Temlyakov.Nonlinear Methods of Approximation. IMI Research Reports， Dept of Mathematics， University of South Carolina. 2001， 01-09.
[14]. RIGUEIREDO M A T，NOWAK R D，WRIGHT S J. Gradient projection for sparse reconstruction：application to compressed sensing and other inveme problems[J].IEEE Journal of Selected Topics in Signal Processing，2007，1（04），586-597.
[15]. S Mallat.信號处理的小波导引（第二版）[M].杨力华， 戴道清， 黄文良等. 北京：机械工业出版社，2002.
[16]. 覃凤清.数字图像压缩综述[J].宜宾学院学报，2006，6（6），88-90.
[17]. 刘丹华，石光明，周佳社.一种冗余字典下的信号稀疏分解新方法[J].西安电子科技大学学报（自然科学版），2008，35（02），228-232.
地址：北京市海淀区学院路丁11号科技楼708A，李咏梅电话：15321406861邮箱：[email protected]
抬头：中国矿业大学（北京）版面费
关键词：压缩感知；稀疏变换；观测矩阵；有限等距性；编码；解码
中图分类号：TN957.52
0 引言
Nyquist采样定理指出，采样速率达到信号带宽的两倍以上时才能实现采样信号的精确重构。可见，带宽是Nyquist采樣定理对采样的本质要求。然而随着信息需求量的增加，携带信息的信号带宽越来越宽，以此为基础的信号处理框架所要求的采样速率和处理速度也越来越高。解决这些压力常见的方案是信号压缩。但是，信号压缩会浪费大量采样资源，因为大量非重要或冗余信息在压缩过程中被丢弃。基于此可以得出结论：带宽不能本质地表达信号的信息，基于Nyquist采样定理的采样机制是冗余的。
于是很自然地引出一个问题：能否利用其它变换空间描述信号，建立新的信号描述和处理的理论框架，使得在保证信息不损失的情况下，用远低于Nyquist采样定理要求的速率采样信号，同时又可以完全恢复信号。与信号带宽相比，稀疏性能够直观地而且相对本质地表达信号的信息。事实上，稀疏性在现代信号处理领域起着至关重要的作用。近年来基于信号稀疏性提出一种称为压缩感知新兴采样理论，成功实现了信号的同时采样与压缩。
简单地说，压缩感知理论指出：只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。在该理论框架下，采样速率不再取决于信号的带宽，而在很大程度上取决于两个基本准则：稀疏性和等距约束性。事实上，压缩感知理论的某些抽象结论源于Kashin创立的范函分析和逼近论 ，由Candes ，Romberg ，Tao 和Donoho 等人构造了具体的算法并且通过研究表明了这一理论的巨大应用前景。目前国内已经有科研单位的学者对其展开研究，如西安电子科技大学课题组基于该理论提出采用超低速率采样检测超宽带回波信号 。
显然，在压缩感知理论中，图像/信号的采样和压缩同时以低速率进行，使传感器的采样和计算成本大大降低，而信号的恢复过程是一个优化计算的过程.因此，该理论指出了将模拟信号直接采样压缩为数字形式的有效途径。从理论上讲任何信号都具有可压缩性，只要能找到其相应的稀疏表示空间，就可以有效地进行压缩采样。
当前，压缩感知理论主要涉及三个核心问题：
（1） 具有稀疏表示能力的过完备字典设计；
（2） 满足非相干性或等距约束性准则的测量矩阵设计；
（3） 快速鲁棒的信号重建算法设计。
压缩感知理论必将给信号采样方法带来一次新的革命。这一理论的引人之处还在于它对应用科学的许多领域具有重要的影响，如统计学、信息论、编码 等。目前，学者们已经在模拟-信息采样、合成孔径雷达成像、遥感成像、核磁共振成像、深空探测成像、无线传感器网络、信源编码、人脸识别、语音识别、探地雷达成像等诸多领域对压缩感知展开了广泛的应用研究。Rice大学已经成功设计出了一种基于压缩感知的新型单像素相机，在实践中为取代传统相机迈出了实质性的一步。
本文围绕稀疏字典设计、测量矩阵设计、重建算法设计三个核心问题，综述了压缩感知理论以及与之相关的信号稀疏变换、观测矩阵设计、重构算法等一系列最新理论成果和应用研究，描述了国内外的研究进展。
1 压缩感知理论框架
传统的信号采集、编解码过程如图l所示：编码端先对信号进行采样，再对所有采样值进行变换，并将其中重要系数的幅度和位置进行编码，最后将编码值进行存储或传输：信号的解码过程仅仅是编码的逆过程，接收的信号经解压缩、反变换后得到恢复信号。采用这种传统的编解码方法，由于信号的采样速率不得低于信号带宽的两倍，使得硬件系统面临着很大的采样速率的压力。此外在压缩编码过程中，大量变换计算得到的小系数被丢弃，造成了数据计算和内存资源的浪费。
压缩感知理论对信号的采样、压缩编码发生在同一个步骤，利用信号的稀疏性，以远低于Nyquist采样率的速率对信号进行非自适应的测量编码。测量值并非信号本身，而是从高维到低维的投影值，从数学角度看，每个测量值是传统理论下的每个样本信号的组合函数，即一个测量值已经包含了所有样本信号的少量信息。解码过程不是编码的简单逆过程，而是在盲源分离中的求逆思想下。利用信号稀疏分解中已有的重构方法在概率意义上实现信号的精确重构或者一定误差下的近似重构 。解码所需测量值的数目远小于传统理论下的样本数。
2 压缩感知的基本理论
假设有一信号 ，长度为 ，基向量为 ，对信号进行变换：
显然 是信号在时域的表示， 是信号在 域的表示。信号是否具有稀疏性或者近似稀疏性是运用压缩感知理论的关键问题，若（1）式中的 只有 个是非零值 者仅经排序后按指数级衰减并趋近于零，可认为信号是稀疏的。信号的可稀疏表示是压缩感知的先验条件。在已知信号是可压缩的前提下，压缩感知过程可分为两步：
（1）一个与变换基不相关的 维测量矩阵对信号进行观测，得到 维的测量向量。
（2）由 维的测量向量重构信号。 2.1 信号的稀疏表示
文献[4]给出稀疏的数学定义：信号 在正交基 下的变换系数向量为 ，假如对于 和 ，这些系数满足：
则说明系数向量 在某种意义下是稀疏的.文献[1]给出另一种定义：如果变换系数
的支撑域 的势小于等于 ，则可以说信号 是 项稀疏。如何找到信号最佳的稀疏域？这是压缩感知理论应用的基础和前提，只有选择合适的基表示信号才能保证信号的稀疏度，从而保证信号的恢复精度。在研究信号的稀疏表示时，可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Candes和Tao研究表明，满足具有幂次（power-law）速度衰减的信号，可利用压缩感知理论得到恢复。
最近几年，对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解.这是一种全新的信号表示理论：用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子.字典的选择应尽可能好地符合被逼近信号的结构，其构成可以没有任何限制.从从冗余字典中找到具有最佳线性组合的K项原子来表示一个信号，称作信号的稀疏逼近或高度非线性逼近 。
在冗余字典下的稀疏表示的研究集中在两个方面：（1）如何构造一个适合某一类信号的冗余字典；（2）如何设计快速有效的稀疏分解算法.这两个问题也一直是该领域研究的热点，学者们对此已做了一些探索，其中以非相干字典为基础的一系列理论证明得到了进一步改进.西安电子科技大学的石光明教授也对稀疏表示问题进行了认真研究，并基于多组正交基级联而成的冗余字典提出一种新的稀疏分解方法 。
2.2 信号的观测矩阵
用一个与变换矩阵不相关的 测量矩阵 对信号进行线性投影，得到线性测量值 ：
测量值 是一个 维向量，这样使测量对象从 维降为 维。观测过程是非自适应的即测量矩阵少的选择不依赖于信号 。测量矩阵的设计要求信号从 转换为 的过程中，所测量到的 个测量值不会破坏原始信号的信息，保证信号的精确重构。
由于信号 是是可稀疏表示的，上式可以表示为下式：
其中 是一个 矩阵。上式中，方程的个数远小于未知数的个数，方程无确定解，无法重构信号。但是，由于信号是K稀疏，若上式中的 满足有限等距性质（Restricted Isometry Property，简称RIP），即对于任意K稀疏信号 和常数 ，矩阵 满足：
则 个系数能够从 个测量值准确重构。RIP性质的等价条件是测量矩阵 和稀疏基 不相关。目前，用于压缩感知的测量矩阵主要有以下几种：高斯随机矩阵，二值随机矩阵（伯努力矩阵），傅立叶随机矩阵，哈达玛矩阵，一致球矩阵等。
2.3 信号的重构算法
当矩阵 满足RIP准则时。压缩感知理论能够通过对上式的逆问题先求解稀疏系数 ，然后将稀疏度为K的信号 从 维的测量投影值 中正确地恢复出来。解码的最直接方法是通过 范数下求解的最优化问题：
从而得到稀疏系数的估计。由于上式的求解是个NP—HARD问题。而该最优化问题与信号的稀疏分解十分类似，所以有学者从信号稀疏分解的相关理论中寻找更有效的求解途径。文献[10]表明， 最小范数下在一定条件下和 最小范数具有等价性，可得到相同的解。那么上式转化为 最小范数下的最优化问题：
最小范数下最优化问题又称为基追踪（BP），其常用实现算法有：内点法和梯度投影法。内点法速度慢，但得到的结果十分准确：而梯度投影法速度快，但没有内点法得到的结果准确 。二维图像的重构中，为充分利用图像的梯度结构。可修正为整体部分（Total Variation，TV）最小化法。由于 最小范数下的算法速度慢，新的快速贪婪法被逐渐采用，如匹配追踪法（MP）和正交匹配追踪法（OMP）。此外，有效的算法还有迭代阈值法以及各种改进算法。
3 有待解决的几个关键问题
压缩感知经过近年来的迅猛发展，已基本形成了自己的理论框架，包括基础理论、实现方法和实际应用。但是，压缩感知理论还有很多亟待解决的问题，为此本文列出了压缩感知有待解决的几个关键问题。
3.1 基础理论层面
（1）基于非正交稀疏字典的压缩感知信号重建理论。在等距约束性准则驱动的可压缩信号压缩感知定理中，关于稀疏字典 和测量矩阵 仅要求两者乘积 满足RIP。但是，测量矩阵设计部分关于压缩测量个数M 的界定还额外附加了假设条件，即稀疏字典 是正交基。当测量矩阵 依然通过三种方式生成，但是稀疏字典 不再正交时， 是否满足RIP？压缩测量个数M 的下限是否不变？由于过完备的稀疏字典才能保证表示系数具有足够的稀疏性或衰减性，进而能够在减少压缩测量的同时保证压缩感知的重建精度，所以需要设计鲁棒的测量矩阵 使之与过完备稀疏字典依然满足RIP，同时需要重新估计压缩测量个数M 的下限，这时所需的压缩测量定会减少。
（2）自然图像的自适应压缩感知信号重建理论。虽然基于线性投影的压缩感知理论能够直接应用于自然图像这样的复杂高维信号，但是由于没有考虑到自然图像的固有特性，诸如结构多成分性、高阶统计性等，对于自然图像压缩采样本身没有特殊的指导作用。事实上，相对于一维离散信号，自然图像的复杂性和高维性使之需要自适应的压缩采样和重建算法。
例如，基于图像多成分性的特点能够提高重建图像的峰值信噪比和视觉效果。注意到，压缩感知理论的大部分文献中，测量矩阵 都是线性的且设计好的，不需根据观测信号自适应地变化。对于自然图像，假如能够实现非线性自适应的压缩测量，压缩感知的压缩性能势必会获得大幅度的提高。目前，自然图像的自适应压缩感知信号重建理论基本空白。这项工作对压缩感知的理论推广和实际应用都具有重要意义。
3.2 实现方法层面
（1）基于学习的自然图像过完备字典设计。目前，基于构造方法的自然图像过完备字典设计具有很好的理论支撑，正则化几何方法、几何多尺度分析、基于信息论的“有效编码假设”为其奠定了坚实广阔的理论基础。但是，从国际上关于过完备字典设计的整体情况看，基于学习的自然图像过完备字典设计的工作非常少，主要在于：设计难度大、性能要求高，同时缺乏严格的理论支撑。这项工作对于稀疏字典和压缩感知都将是重要的理論完善。 （2） 硬件易实现的确定性测量矩阵设计。在等距约束性准则驱动的可压缩信号压缩感知定理3、4 中，要求稀疏字典 和测量矩阵 的乘积 满足RIP。其中，稀疏字典 可以是正交的也可以是非正交的，测量矩阵 可以是随机的也可以是确定的。但是，面向应用且硬件易实现的测量矩阵应该具有以下基本特点：满足等距约束性、压缩测量个数少、采样计算成本低、存储矩阵的空间小、以及测量矩阵最好是确定性的。设计出硬件容易实现的测量矩阵和快速稳定的重建算法是将压缩感知理论推向实用的关键。
（3） 噪声情形大尺度问题的快速鲁棒重建算法设计。快速稳定的信号重建算法是将压缩感知理论推向实用的关键技术之一，特别适用于纠错编码、核磁共振成像、NMR波谱研究等大尺度问题。通常，基于最小化松弛算法的计算复杂度相对较高。因而，在最小化驱动的压缩感知理论完善工作的基础上，希望能够基于稀疏性自适应的贪婪迭代和基于多层超先验建模的非凸迭代思想设计适于噪声情形大尺度问题的快速鲁棒重建算法。
4 压缩感知的应用
使用一定数量的非相关测量值能够高效率地采集可压缩信号的信息，这种特性决定了压缩感知应用的广泛性。例如低成本数码相机和音频采集设备；节电型音频和图像采集设备；天文观测；网络传输；军事地图；雷达信号处理等等。以下归纳了压缩感知几个方面的应用：
（1） 数据压缩
在某些情况下，稀疏表示在编码中是未知的或在数据压缩中是不能实际实现的。由于测量矩阵西是不需要根据缈的结构来设计的，随机测量矩阵可认为是一个通用的编码方案，而只有在解码或重建信号的时候需要用到。这种通用用性在多信号装置（如传感器网络）的分布式编码特别有用。
（2） 信道编码
压缩感知的稀疏性、随机性和凸优化性，可以应用于设计快速纠错码以防止错误传输。
（3） 逆问题
在其他情况下，获取信号的唯一方法是运用特定模式的测量系统 。然而，假定信号存在稀疏变换基 ，并与测量矩阵 不相关，则能够有效的感知的信号。这样的應用在文献[2]中的MR血管造影术有提到， 记录了傅立叶变换子集，所得到的期望的图像信号在时域和小波域都是稀疏的。
（4） 数据获取
在某些重要的情况下，完全采集模拟信号的N个离散时间样本是困难的，而且也难以对其进行压缩。而运用压缩感知，可以设计物理采样装置，直接记录模拟信号离散、低码率、不相关的测量值，有效地进行数据获取。基于RIP理论，目前已研制出了一些设备，有莱斯大学研制的单像素相机和A/I转换器，麻省理工学院研制的编码孔径相机，耶鲁大学研制的超谱成像仪，麻省理工学院研制的MRI RF脉冲设备，伊利诺伊州立大学研制的DNA微阵列传感器。
5 结论
本文主要阐述了压缩感知理论框架，基于压缩感知理论的编解码模型，以及压缩感知技术的三大核心问题。通过对一维信号编解码的仿真实验说明了压缩感知理论是一种能够使用少量测量值实现信号准确恢复的数据采集、编解码理论。由于压缩感知理论对处理大规模稀疏或可压缩数据具有十分重要的意义。所以该理论提出后在许多研究领域得到了关注。目前，国外研究人员已开始将压缩感知理论用于压缩成像、医学图像、模数转换、雷达成像、天文学、通信等领域。作为国外刚出现的新理论，压缩感知理论的研究方兴未艾，将有着更广泛的应用前景。
参考文献：
[1].石光明，刘丹华，高大化，刘哲，林杰，王良君.压缩感知理论及其研究进展[J].ACTA Electronica Sinica，2009，37（5）：1070-1081.
[2].张锐.基于压缩感知理论的图像压缩初步研究[J].Computer Knowledge And Technology.2012，6（4）：958-959.
[3]. Candes E，Romberg J，Tao T.Robust uncertaintyprinciples：Exact signal reconstruction from highly incomplete frequency information[J].IEEE Trans.Information Theory，2006，52（4）：489-509.
[4]. E Candes，J Romberg.Quantitative robust uncertainty principles and optimally sparse decompositions[J].Foundations of Comput Math，2006，6（2）：227-254.
[5]. Emmanuel J.Candes，Terence Tao.Near-Optimal signal recovery from random projections：Universal encoding strategies[J].IEEE Transaction on Information Theory，2006，52（12）：5406-5425.
[6]. D.L.Donoho.Compressed sensing，2006（04）.
[7]. B Kashin.The widths of certain finite dimensional sets and classes of smooth functions[J].Izv Akad Nauk SSSR，1977，41（2）：334-351.
[8]. E.Candes，M.Wakin.An introduction to compressive sampling[J]. IEEE Signal Processing Magazine 2008，25（2）：21-30. [9]. 喻玲娟，谢晓春.压缩感知理论简介.Video Engineering，2008，32（12）：16-18.
[10].DONOHO D，TSAIG Y.Extensions of compressed sensing[J].Signal Processing，2006，86（3）：533-548.
[11].UWB Echo Signal Detection with Ultra-Low Rate Sampling based on Compressed Sensing[J].IEEE Trans.Circuits and Systems II：Express Briefs，2008，55（4）：379–383.
[12]. 张春梅，尹忠科，肖明霞.基于冗余字典的信号超完备表示与稀疏分解[J].科学通报，2006，51（06），628-633.
[13].V.Temlyakov.Nonlinear Methods of Approximation. IMI Research Reports， Dept of Mathematics， University of South Carolina. 2001， 01-09.
[14]. RIGUEIREDO M A T，NOWAK R D，WRIGHT S J. Gradient projection for sparse reconstruction：application to compressed sensing and other inveme problems[J].IEEE Journal of Selected Topics in Signal Processing，2007，1（04），586-597.
[15]. S Mallat.信號处理的小波导引（第二版）[M].杨力华， 戴道清， 黄文良等. 北京：机械工业出版社，2002.
[16]. 覃凤清.数字图像压缩综述[J].宜宾学院学报，2006，6（6），88-90.
[17]. 刘丹华，石光明，周佳社.一种冗余字典下的信号稀疏分解新方法[J].西安电子科技大学学报（自然科学版），2008，35（02），228-232.
地址：北京市海淀区学院路丁11号科技楼708A，李咏梅电话：15321406861邮箱：[email protected]
抬头：中国矿业大学（北京）版面费