基于压缩感知理论的重构算法研究

*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:[e-mail]压缩感知重构算法综述李珅1,2，马彩文1，李艳1，陈萍1（1.中国科学院西安光学精密机械研究所光电跟踪与测量室,陕西省西安市710119;2.中国科学院研究生院,北京100039）摘要：现代社会信息量的激增带来了信号采样、传输和存储的巨大压力，而近年来出现的压缩感知理论(CompressedSensing,CS)为解决该问题提供了契机。该理论指出：对于稀疏或可压缩的信号，能够以远低于奈奎斯特频率对其进行采样，并通过设计重构算法来精确的恢复该信号。本文介绍了压缩感知理论的基本框架，综述了压缩感知理论的重构算法，其中着重介绍了最优化算法和贪婪算法并比较了各种算法之间的优劣，最后探讨了压缩感知理论重构算法未来的研究重点。关键词：信号采样;压缩感知;稀疏;重构算法中图法分类号：TP301.6文献标识码：ASurveyonreconstructionalgorithmbasedoncompressivesensingLiShen1,2,MaCai-wen1,LiYan1,ChenPing1(1.Xi’anInstituteofOpticsandPrecisionMechanicsofCAS,Xi’anShaanxi710119,China；2.GraduateUniversityofChineseAcademyofSciences,Beijing100039,China）Abstract：Withtherapiddemandingforinformation,theexistingsystemsareverydifficulttomeetthechallengesofhighspeedsampling,largevolumedatatransmissionandstorage.Recently,anewsamplingtheorycalledcompressivesensing(CS)providesagoldenopportunityforsolvingthisproblem.CStheoryassertsthatasignalorimage,unknownbutsupposedtobesparseorcompressibleinsomebasis,canbesubjectedtofewermeasurementsthantraditionalmethodsuse,andyetbeaccuratelyreconstructed.ThispapergivesabriefoverviewoftheCStheoryframeworkandreviewsthereconstructionalgorithmofCStheory.Next,thispaperintroducesthebasispursuitalgorithmandgreedyalgorithmsandexploresthedifferencebetweenthem.Intheend,webrieflydiscusspossibleimplicationintheareasofCSdatareconstruction.Keywords：informationsampling;compressivesensing;sparse;reconstructionalgorithm0引言随着现代科技的飞速发展，人们对信息量的需求也在剧增。传统的信息采样是基于香农采样定理，它指出信号的采样率不低于最高频率的两倍，信号才能被精确的重构。该理论支配着几乎所有信号的获取、处理、存储和传输。一方面，在许多实际应用中（如超宽带通信，核磁共振，空间探测，高速AD转换器等），信息在存储和处理时，为达到采样率而需要大量的采样数据，从而导致采样硬件成本昂贵，获取效率低下甚至在某些情况难以实现。另一方面，在数据的存储和传输方面，传统的做法是先按照Nyquist方式获取数据，然后将获得的*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:[e-mail]数据进行压缩，最后将压缩后的数据进行存储或传输。显然，这样的方式造成很大程度的资源浪费，同时也提出了一个问题[1]：既然在压缩中需要丢弃大多数数据，为什么不在采样时直接取得我们需要的重要数据？近年来，D.Donoho、E.Candes及华裔科学家T.Tao等人提出了一种新的信息获取理论－压缩感知(CompressiveSensing)，以下简称为CS。该理论指出[1]：对于可压缩的信号，可以通过低于或远低于奈奎斯特标准的方式对其进行数据采样并精确重构该信号。与香农定理不同的是，压缩感知并不是直接测量信号本身，它使用非自适应线性投影（感知矩阵）来获得信号的整体构造从而直接得到重要的信息，忽略那些在有损压缩中会被丢弃的信息。一般来说，压缩感知涉及三个比较重要的层面[2]：一、信号稀疏域的选取，是压缩感知理论的基础和前提。二、观测矩阵的选取，已经证明大部分具有一致分布的随机矩阵都可以作为观测矩阵。三、重构算法的设计，由于压缩感知采用的是全局非自适应测量方法，观测数量远远少于信号长度，从而数据采集量大大减少。但是需要付出的代价是信号重建算法的软件成本。因此，CS重构算法的好坏直接影响到CS理论是否实用。1压缩感知理论简介1.1基本思想可压缩（稀疏）的定义：考虑一个一维信号x∈RN×1，都可以用N×1维基向量Nii1线性表示。为了简化问题，假设基向量为规范正交向量，使用N×N的基矩阵N|...||21,信号x可以被表示为：NiiiSorsx1)1(其中S是投影系数Tiiis,构成的N×1维列向量。显然，X和S是同一个信号的等价表示，其中X是在时域或空间域的表示，S是在Ψ域的表示。当信号可以仅被K个基向量线性表示时，则称信号x为K-稀疏。当KN时，如果信号可以被很少的大系数和很多的小系数表示的话，则称信号x为可压缩的[2][3]。假设信号为稀疏的，那么对于0p2以及R0有：)2(/1Rsspipip传统思路中压缩信号就是采用这种正交变换的方式，其编码解码的策略为：编码首先构造正交基矩阵Ψ，作变换XST,保留S中最重要的K个分量及其对应的位置。解码将K个分量放回到其对应的位置，并将其他位置填0，以此构造Ψ，最后进行反变换S求得重构信号。显然，这种以Nyquist-Shanon采样定理为准则的编码和解码方法有很多缺点。一、采样后再进行压缩的方式浪费了大量的采样资源，如果采样后的信号长度仍然很长，那么变换会消耗很长时间；二、由于需要保留的K个重要分量的位置是随着信号的不同而不同，所以这种编解码方式是自适应的，需要分配多余的存储空间以保留K个重要分量的位置。三、K个重要分量有可能在传输过程中丢失其中的某几个分量从而造成较差的抗干扰能力。近几年出现的压缩感知理论，对传统的理念是一次革新，它表明我们可以用比传统途径少得多的采样和测量来恢复信号。该理论主要依赖于两个原则[4]，稀疏（sparsity）和不相关(incoher-ence)，稀疏关于感兴趣的信号，它所表达的意思是：连续时间信号的信息率可能比根据其带宽所建议的小得多，离散时间信号所依赖自由度的数量比它的长度少得多。可以说，许多自然界的信号在某种程度上都是稀疏的或可压缩的，当以*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:[e-mail]合适的基Ψ来表示时，信号可以有很多简练的表达式。不相关表达了一种含义即以Ψ稀疏表示的信号一定可以在其所需要的域中展开。基于这两个原则，压缩感知理论指出，长度为n的信号X在某组正交基或紧框架nn上的变换系数是稀疏的，如果我们可以用一个与变换基Ψ不相关的观测基Ф（nmRm，n）对系数向量进行线性变换，并得到观测集合1m，则可以通过求解最优化问题来精确地重构信号X。1.2压缩感知采样过程基于CS理论实现信号压缩的采样过程为：第一步：找到某个基或紧框架Ψ，使得信号x在Ψ上是稀疏的，并求出变换系数：S＝ΨTX，其中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维时重要信息不被破坏。在压缩感知理论中，受限等距属性（RestrictedIsometryProperty,RIP）[10][11]是判断矩阵是否可以成为测量矩阵的一个重要的标准。对于k稀疏向量S∈RN来说，当它满足式(3)时，测量矩阵Ф满足RIP。222s）1（ss）-1（(3)压缩感知理论对于测量系有两个主要的分类：第一类为随机测量系，文献[10][12]已证明大多数随机矩阵都满足RIP，如高斯随机测量系和伯努利随机测量系。文献[13]的工作告诉我们：在某种意义上说，选择随机测量对于稀疏矩阵来讲是一种最佳策略，只需要几乎最少的m个测量便可恢复稀疏度为S≤m/log(n/m)的信号，而且分析时所需要的常量都很小。第二类为非相关测量系，即测量矩阵和变换基Ψ是不相关的，其不相关性可以通过测量它们之间的相关系数，文献[14]给出了测量矩阵Ф和变换基Ψ的相关系数μ=N1/2maxi,k|Ψi,Фi|，μ越小说明测量矩阵Ф和变换基Ψ的不相关性越大，测量所需要的数目也越少。第三步：重构信号x，区别于奈奎斯特理论的线性感知问题，由于观测数量m远远小于信号长度n，重构面临着求解一个欠定方程组的问题。当信号x是稀疏或可压缩的，求解欠定方程组的问题可以转化为最小0范数问题如式(4)：0min..TcsTXstAXXY(4)然而统计理论和组合优化理论告诉我们，组合优化是一个NP难问题，当N很大时，数值上无法有效实现，且抗噪声能力很差；Candes,Tao和Donoho等人已证明，当测量矩阵满足约束等距性质(RestrictedIsometryProperty,RIP)时，组合优化问题(或称，l0约束优化问题)可转化为数值上容易处理l1约束的凸优化问题：1min..TcsTXstAXXY(5)除此之外还有一些其它方法可以重构信号,如:1）将l0范数松弛为lp范数；2）通过先验分布引入稀疏性，再用Bayesian方法实现信号稀疏重构；3）使用启发式算法(heuristicalgorithms)，如借鉴图模型和编码理论中的belief-propagation和消息传递技术。2压缩感知重构算法研究2.1重构算法介绍*基金项目：陕西省自然科学基金资助项目（2012JM8021）作者简介：李珅（1980—），女，河北乐亭人，在读博士，主要从事压缩感知和图像超分辨率分析方面的研究工作。Email:[e-mail]现阶段CS重构算法大致