压缩感知技术研究进展

压缩感知技术研究进展摘要：信号采样是联系模拟信源和数字信息的桥梁.人们对信息的巨量需求造成了信号采样、传输和存储的巨大压力.如何缓解这种压力又能有效提取承载在信号中的有用信息是信号与信息处理中急需解决的问题之一.近年国际上出现的压缩感知理论(CompressedSensing,CS)为缓解这些压力提供了解决方法.本文综述了CS理论框架及关键技术问题,并介绍了仿真实例、应用前景,评述了其中的公开问题,对研究中现存的难点问题进行了探讨,最后对CS技术做了一下总结和展望.关键词：压缩感知；稀疏表示；观测矩阵；编码；解码AdvancesinTheoryandApplicationofCompressedSensingAbstract：Samplingisthebridgebetweenanalogsourcesignalanddigitalsignal.Withtherapidprogressofinformationtechnologies,thedemandsforinformationareincreasingdramatically.Sotheexistingsystemsareverydifficulttomeetthechallengesofhighspeedsampling,largevolumedatatransmissionandstorage.Howtoacquireinformationinsignalefficientlyisanurgentprobleminelectronicinformationfields.Inrecentyears,anemergingtheoryofsignalacquirement.compressedsensing(CS)providesagoldenopportunityforsolvingthisproblem.Thispaperreviewsthetheoreticalframeworkandthekeytechnicalproblemsofcompressedsensingandintroducesthelatestdevelopmentsofsignalsparserepresentation,designofmeasurementmatrixandreconstructionalgorithm.ThenthispaperalsoreviewsseveralopenproblemsinCStheoryanddiscussestheexistingdifficultproblems.Intheend,theapplicationfieldsofcompressedsensingareintroduced.Keywords:compressedsensing;sparserepresentation;theobservationmatrix;coding;decoding一、引言在过去的半个世纪里，奈奎斯特采样定理几乎支配着所有的信号或图像等的获取、处理、存储以及传输。它要求采样频率必须大于或等于信号带宽的两倍，才能不失真的重构原始信号。在许多实际应用中，例如高分辨率的数码装置及超带宽信号处理，高速采样产生了庞大的数据，为了降低存储，处理或传输成本，只保留其中少量的重要数据。由于采样后得到的大部分数据都被丢弃了，所以这种方式造成了采样资源的严重浪费。设想如果在采样的同时直接提取信号的少量重要信息，就可以大大降低采样频率，节约资源，提高效率而且仍能够精确重构原始信号或图像。这就是Donoho、Candes以及Tao等人提出压缩感知（CompressedSensing、CompressiveSampling或CompressiveSensing，CS）理论的主要思想。压缩感知理论指出：如果信号在某个变换域是稀疏的或可压缩的，就可以利用一个与变换基不相关的观测矩阵将变换所得的高维信号投影到一个低维空间上，根据这些少量的观测值，通过求解凸优化问题就可以实现信号的精确重构。在传统理论的指导下，信号X的编解码过程如图1所示：编码端首先获得X的N点采样值，经变换后只保留其中K个最大的投影系数并对它们的幅度和位置编码，最后将编得的码值进行存储或传输。解压缩仅是编码过程的逆变换。实际上，采样得到的大部分数据都是不重要的，即K值很小，但由于奈奎斯特采样定理的限制，采样点数N可能会非常大，采样后的压缩是造成资源浪费的根本所在。CS很好的解决了这一问题，它将信号的采样、压缩及编码合并在了同一步骤中，不经过N点采样的中间过程而直接得到信号的表示，其编解码过程如图2所示。可压缩信号X通过一个线性观测过程获得M个观测值后直接进行存储或传输。在满足一定的条件下接收端可以根据这M个观测值通过一个非线性优化过程恢复出原信号X。二、压缩感知的基本理论及核心问题假设有一信号)(NRff，长度为N，基向量为),...,2,1(Nii，对信号进行变换：fafiNii或1显然f是信号在时域的表示，是信号在域的表示。信号是否具有稀疏性或者近似稀疏性是运用压缩感知理论的关键问题，若(1)式中的只有K个是非零值)(KN者仅经排序后按指数级衰减并趋近于零，可认为信号是稀疏的。信号的可稀疏表示是压缩感知的先验条件。在已知信号是可压缩的前提下，压缩感知过程可分为两步：(1)设计一个与变换基不相关的)(NMNM维测量矩阵对信号进行观测，得到M维的测量向量。(2)由M维的测量向量重构信号。2.1信号的稀疏表示文献[4]给出稀疏的数学定义：信号X在正交基下的变换系数向量为XT，假如对于20p和0R，这些系数满足：Rppiip/1)||(||||则说明系数向量在某种意义下是稀疏的．文献[1]给出另一种定义：如果变换系数iiX,的支撑域}0;{ii的势小于等于K，则可以说信号X是K项稀疏。如何找到信号最佳的稀疏域?这是压缩感知理论应用的基础和前提，只有选择合适的基表示信号才能保证信号的稀疏度，从而保证信号的恢复精度。在研究信号的稀疏表示时，可以通过变换系数衰减速度来衡量变换基的稀疏表示能力。Candes和Tao研究表明，满足具有幂次(power-law)速度衰减的信号，可利用压缩感知理论得到恢复。最近几年，对稀疏表示研究的另一个热点是信号在冗余字典下的稀疏分解．这是一种全新的信号表示理论：用超完备的冗余函数库取代基函数，称之为冗余字典，字典中的元素被称为原子．字典的选择应尽可能好地符合被逼近信号的结构，其构成可以没有任何限制．从从冗余字典中找到具有最佳线性组合的K项原子来表示一个信号，称作信号的稀疏逼近或高度非线性逼近]13,12[。目前信号在冗余字典下的稀疏表示的研究集中在两个方面：(1)如何构造一个适合某一类信号的冗余字典；(2)如何设计快速有效的稀疏分解算法．这两个问题也一直是该领域研究的热点，学者们对此已做了一些探索，其中以非相干字典为基础的一系列理论证明得到了进一步改进．西安电子科技大学的石光明教授也对稀疏表示问题进行了认真研究，并基于多组正交基级联而成的冗余字典提出一种新的稀疏分解方法]17[。2.2信号的观测矩阵用一个与变换矩阵不相关的)(NMNM测量矩阵对信号进行线性投影，得到线性测量值y：fy测量值y是一个M维向量，这样使测量对象从N维降为M维。观测过程是非自适应的即测量矩阵少的选择不依赖于信号f。测量矩阵的设计要求信号从f转换为y的过程中，所测量到的K个测量值不会破坏原始信号的信息，保证信号的精确重构。由于信号f是是可稀疏表示的，上式可以表示为下式：fy其中是一个NM矩阵。上式中，方程的个数远小于未知数的个数，方程无确定解，无法重构信号。但是，由于信号是K稀疏，若上式中的满足有限等距性质(RestrictedIsometryProperty，简称RIP)，即对于任意K稀疏信号f和常数)1,0(k，矩阵满足：kkff1||||||||12222则K个系数能够从M个测量值准确重构。RIP性质的等价条件是测量矩阵和稀疏基不相关。目前，用于压缩感知的测量矩阵主要有以下几种：高斯随机矩阵，二值随机矩阵(伯努力矩阵)，傅立叶随机矩阵，哈达玛矩阵，一致球矩阵等。2.3信号的重构算法当矩阵满足RIP准则时。压缩感知理论能够通过对上式的逆问题先求解稀疏系数xT，然后将稀疏度为K的信号x从M维的测量投影值y中正确地恢复出来。解码的最直接方法是通过0l范数下求解的最优化问题：ytsl.||||0min从而得到稀疏系数的估计。由于上式的求解是个NP—HARD问题。而该最优化问题与信号的稀疏分解十分类似，所以有学者从信号稀疏分解的相关理论中寻找更有效的求解途径。文献[10]表明，1l最小范数下在一定条件下和0l最小范数具有等价性，可得到相同的解。那么上式转化为1l最小范数下的最优化问题：ytsl.||||1min1l最小范数下最优化问题又称为基追踪(BP)，其常用实现算法有：内点法和梯度投影法。内点法速度慢，但得到的结果十分准确：而梯度投影法速度快，但没有内点法得到的结果准确]14[。二维图像的重构中，为充分利用图像的梯度结构。可修正为整体部分(TotalVariation，TV)最小化法。由于1l最小范数下的算法速度慢，新的快速贪婪法被逐渐采用，如匹配追踪法(MP)和正交匹配追踪法(OMP)。此外，有效的算法还有迭代阈值法以及各种改进算法。三、压缩感知仿真实例对256×256大小的8bit灰度lena图像进行仿真计算，由于数据量过大，将图像分为16×16大小的分块进行计算，稀疏矩阵采用DCT矩阵，观测矩阵采用高斯随机矩阵，重构算法采用OMP（正交匹配追踪）算法。MATLAB代码如下：在MATLABR2001b中的计算结果如下：原图像采样率0.7采样率0.5采样率0.3采用均方误差MSE评价重构后的图像质量。不同采样率下的计算时间与计算误差如下图所示：四、CS的应用前景能从少量的非相关观测值中高效获取可压缩信号的信息，CS的这一特点决定了其应用的广泛性。CS的应用领域涉及数据压缩、模拟/信息的转换、压缩成像、信道编码、信道估计、生物传感、语音识别、雷达成像、雷达遥感、学习理论及模式识别等诸多领域。在压缩成像方面，RICE大学已成功研制了“单像素”压缩数码照相机，该相机不像传统相机那样获取原始信号的N个像素值，而是直接获取M个随机线性观测值，在实践中为取代传统相机迈出了实质性的一步。在通信领域，压缩感知也有着强大的生命力，由于无线多径信道一般情况下是稀疏的，即使在时延扩展很大时，大幅度的径的个数也很少，因此利用少量的导频就能获取未知信道的频域响应估计。此外压缩感知理论还可用于通信信道的错误检测、传感网络的分布式信源编码、认知无线电中的频谱感知等。五、研究的公开问题5.1p2范数优化问题压缩感知理论在图像压缩编码等方面也应该有很广泛的前景,但由于信号的恢复方法是建立在12范数意义下,数据之间还有很大的冗余性没有去除,相比传统的小波变换编码,压缩感知理论应用于图像压缩的效果还不理想.p2范数的优化是提高基于压缩感知理论的压缩算法效果的必经之路.p2范数的优化方法是一个公开问题(openproblem),对它的研究将推动压缩感知理论在压缩方面的应用,具有很深远的意义.p2范数意义下的优化问题是一个凸函数优化问题,目前已有一些成熟的算法,但p2范数的优化是一个非凸函数的优化问题,其中有很多数学问题有待解决.有关p2范数非凸函数优化问题,也有一些学者开展研究.如RickChartrand[用典型的合成数据做了一些实验,表明在一定的稀疏误差范围内,可以得到最小值.在文献[19]中,他进一步给出了变换基空间内的系数严格的等距条件(restrictedisometry),由于有了严格的约束,完全适合于大多数实际的信号.笔者期望通过借用自然优化计算以及将p2范数非凸函数转换为近似凸函