读焦李成-压缩感知回顾与展望有感

压缩感知回顾与展望---焦李成1.概论压缩感知是建立在矩阵分析、统计概率论、拓扑几何、优化与运筹学、泛函分析等基础上的一种全新的信息获取与处理的理论框架.它基于信号的可压缩性,通过低维空间、低分辨率、欠Nyquist采样数据的非相关观测来实现高维信号的感知.压缩感知不仅让我们重新审视线性问题,而且丰富了关于信号恢复的优化策略,极大的促进了数学理论和工程应用的结合.2.背景及意义压缩感知理论的提出？随着当前信息需求量的日益增加,信号带宽越来越宽,在信息获取中对采样速率和处理速度等提出越来越高的要求.而传统的奈奎斯特采样定理在对信号进行采样时，采样速率必须是信号带宽的两倍才能保证原始信号无失真地恢复。由DDonoho、E.Cand.s及华裔科学家Tao等人提出的压缩感知(CompressiveSensing,CS)理论指出了一条将模拟信号“经济地”转化为数字形式的压缩信号的有效途径。在该理论下,信号的采样速率不再取决于信号的带宽,而是取决于信息在信号中的结构与内容,因此在满足的两大特性：(1)信号的可压缩性,(2)表示系统与观测系统的不相关性两大条件下,从低分辨观测中恢复高分辨信号就成为了可能.CS理论显著降低数据存储和传输代价,以及信号处理时间和计算成本。CS被美国科技评论评为“2007年度十大科技进展”,D.Donoho因此还获得了“2008年IEEEIT学会最佳论文奖”。CS的发展：分布式CS理论,1-BITCS理论,BayesianCS理论,无限维CS理论,变形CS理论、谱CS、边缘CS理论、KroneckerCS理论、块CS理论等。2011年4月,第一本关于CS的专著《CompressedSensing:TheoryandApplications》出版,汇集了世界各国学者在CS理论和应用上的观点和成功范例.CS理论与奈奎斯特采样定理的区别：尽管压缩感知理论最初的提出是为了克服传统信号处理中对于奈奎斯特采样要求的限制,但是它与传统采样定理有所不同.首先,传统采样定理关注的对象是无限长的连续信号,而压缩感知理论描述的是有限维观测向量空间的向量;其次,传统采样理论是通过均匀采样(在很少情况下也采用非均匀采样)获取数据,压缩感知则通过计算信号与一个观测函数之间的内积获得观测数据;再次,传统采样恢复是通过对采样数据的Sinc函数线性内插获得(在不均匀采样下不再是线性内插,而是非线性的插值恢复),压缩感知采用的则是从线性观测数据中通过求解一个高度非线性的优化问题恢复信号的方法.首先介绍压缩感知的数学模型.3.CS理论的基本框架4.信号x的稀疏表达，为正交基字典矩阵。对信号x执行一个压缩观测:，为观测矩阵，两者不相关。从y中恢复x是一个解线性方程组的问题,但从方程上看,这似乎是不可能的,因为这是一个未知数个数大于方程个数的病态方程,存在无穷多个解.但是记CS信息算子ACS=,可以得到:虽然从y中恢复也是一个病态问题,但是因为系数是稀疏的,这样未知数个数大大减少,使得信号重构成为可能.那么在什么情况下的解是存在的呢?可以证明:只要矩阵ACS中任意2K列都是线性独立的,那么至少存在一个K-稀疏的系数向量满足.换言之,在满足上述要求的情况下,通过求解一个非线性优化问题就能从观测y、观测矩阵和字典矩阵中近乎完美的重建信号x.信号压缩感知的过程如图2所示:3.1压缩感知的条件两个条件：1.要满足信号在正交基字典矩阵下的稀疏性或可压缩性，即信号需要在变换空间下的展开系数足够的稀疏;2．由观测系统所确定的CS信息算子ACS,需要满足任意2K列都是线性无关的.在这两个条件都同时满足时,就可以通过求解如下问题:获得一个唯一确定的解,即稀疏系数向量,将它与字典相乘,就可以得到信号x.这是一个NP-hard的非凸优化问题，此问题的求解方法两类：以匹配追踪(MatchingPursuit,MP)和正交匹配追踪(OrthogonalMatchingPursuit,OMP)为代表的贪婪算法,以及迭代阈值收缩为代表的门限算法.贪婪算法存在的问题是时间代价过高,无法保证收敛到全局最优;而门限算法虽然时间代价低,但对数据噪声十分敏感,解不具有连续性,且不能保证收敛到全局极小.由Cand.s和Donoho提出的l1范数下的凸化压缩感知恢复框架是一个里程碑式的工作.基本思想是将非凸的优化目标用l1范数来代替:这就将式非凸优化问题变成了一个凸优化问题,可以方便地转化为线性规划问题求解,因此称之为凸化的压缩感知框架。CS理论提出之初,绝大多数研究都建立在此基础上.在有限等距性质(RestrictedIsometryProperty,RIP)和有限等距常数(RestrictedIsometryConstant,RIC)框架下,一些学者证明了范数l1和范数l0的等价条件,2008年,Cand.s给出了有限等距常数需满足的条件:2S0.414;2009年,FoucartandLai等人将此界放松:2S0.4531;之后Cai等人又证明:2S0.472.2010年,Cai等人给出新的RIC界:2S0.307.但是,判断一个矩阵是否满足RIP,以及其RIC的计算都是非常困难的,除RIP理论可以衡量某个测量矩阵能处理稀疏信号的能力外,Donoho还提出了相关性判别理论,Elad提出了矩阵Spark判别理论、Kashin和Temlakov提出了测量算子零空间理论,以及Donoho和Tanner的k-neighborly理论等.相关性判别理论采用矩阵ACS的互相关系数(mutualcoherencecoefficient)衡量压缩重建的条件.互相关系数定义为矩阵任意两个归一化列向量之间的相关系数的最大值,该值介于0和1之间,取值越小则说明矩阵ACS列之间的相关性越弱,即观测矩阵与字典矩阵之间具有低相关性.Spark常数定义为矩阵线性相关向量组的最小数目,取值越大则说明矩阵ACS列之间的相关性越弱.Donoho和Elad早在2003就指出:对于式(4)的欠定系统,若要通过求解式(5)的非线性优化问题唯一确定地得到一个K-稀疏的解,矩阵ACS的Spark常数至少要等于2K,但是矩阵Spark常数的计算也是一个NP难问题.总结来说,关于压缩重建的条件可以通过矩阵ACS的三个定量指标衡量,即互相关系数、Spark常数和RIC.在这些理论中,只有Donoho提出的相关性判别理论可以较为直观的用来判别某一测量矩阵的形态.3.2压缩感知的关键要素压缩感知理论的实现包含三个关键要素:稀疏性、非相关观测、非线性优化重建,其中信号的稀疏性是压缩感知的必备条件,非相关观测是压缩感知的关键,非线性优化是压缩感知重建信号的手段.信号在字典矩阵下的表示越稀疏,高概率精确重构所需要的观测数目就越少.压缩感知的关键是观测矩阵的构造。作为感知的前端,观测系统要求物理上容易实现,并且与表示系统所形成的CS信息算子矩阵ACS具有较小的RIC.观测矩阵设计中的两个关键内容就是观测波形和采样方式,设计的主要原则是:(1)观测波形在理论上的最优性能,即ACS要具有良好的性质;(2)观测波形的普适性,即要满足和一般的字典或表示系统都具有不相关性;(3)实用性,包括快速计算、低存储量、硬件易实现等.目前常采用的测量波形是独立同分布的高斯随机波形、贝努利分布随机波形、Fourier正交函数系、半Fourier矩阵、Chirp序列、Alltop序列等.随机观测矩阵在理论上能满足其最优性,2006年,Cand.s和Tao等证明了:独立同分布的高斯随机变量形成的观测矩阵与任意正交字典都具有较强的不相关性.2011年,Cand.s指出:在独立同分布的高斯随机变量形成的观测矩阵和任意超完备冗余字典的条件下,压缩观测信号的精确恢复仍然是有可能的,因此高斯随机矩阵可成为普适的CS观测矩阵.但是,在实际实现中,其计算复杂度较高,占用的内存较多,因此不适合大规模应用.半Fourier矩阵计算快速、但不满足普适性,即只能用于时域稀疏的信号,不适用于自然图像等信号.在采样方式上,目前主要的有均匀采样、随机采样等.非线性优化是CS重建信号的手段,也是从低分辨观测中恢复出高分辨信号所必须付出的软件代价.Candˆs和Donoho提出的l1范数下的凸化压缩感知恢复是一个里程碑式的工作,对该框架的研究产生了丰富的关于优化恢复的工具。国内学者徐宗本证明了p=0.5时解的最优性,并给出了最优解的解析形式.3.3压缩感知的稀疏表示系统稀疏字典的种类：正交基字典、正交基级联字典、框架字典、字典学习。正交基字典：各种正交变换基。正交基级联字典：框架字典：超完备冗余字典下的信号稀疏更加有效。字典学习：自适应的冗余字典.自适应冗余字典设计的思路是通过字典学习算法获得更符合信号内容,特征,或者纹理信息的原则。字典学习算法,其中大多数是基于贝叶斯模型的最大似然值和最大后验概率,通过获取图像信号的先验来选择更合适的原子组成自适应字典,获得字典原子.其中被广泛应用的有MOD算法[81],ILS-DLA[83],RLS-DLA[84],SL0-DLA[85],KSVD算法[82],以及在此基础上发展起来的多尺度KSVD版本,EK-SVD[86],DK-SVD[87]等.众多的应用实验结果表明,KSVD算法对各种图像处理任务均具有更好的效果.3.4观测系统主要包括随机观测和确定性观测。随机观测：高斯观测矩阵的优点在于它几乎与任意稀疏信号都不相关,因而所需的观测次数最小.随机观测矩阵属于非适应性的测量,在实际实现中具有复杂度较高,难以在大规模问题中应用的缺点.确定性观测：除了如前所述的随机观测矩阵之外,不少学者基于RIP理论提出了多种确定性测量矩阵,例如Chirp测量矩阵、Alltop序列形成的测量矩阵、半Fourier矩阵、结构Fourier矩阵等等.此外,来自于快速算法的Noiselets也被证明和正交基字典之间具有低相关的性质.最近有学者指出可以在压缩感知中采用自适应性的观测矩阵:基于相关性理论,将投影矩阵和观测矩阵的非相关条件可以等价为Gramma矩阵:的单位阵逼近问题:即,首先产生一个随机观测矩阵,然后利用信号的稀疏基的信息,训练学习出一个优化观测矩阵,相比随机观测矩阵,优化之后得到的观测矩阵与字典矩阵之间具有更低的相干性.采用最近Martin提出K-SVD方法求解式(9)中的优化问题,可以根据字典矩阵优化求解确定性的观测矩阵,观测矩阵的优化过程如图所示。将优化观测矩阵用于压缩感知理论应用中,能够提高信号的重构精度或者在相同的重构精度下具有更少的测量数目.4．压缩信息获取单像素相机的应用。5．压缩感知信号恢复l1范数下的凸化压缩感知框架lp范数下的松弛压缩感知框架l0范数下的非凸压缩感知框架6．压缩感知应用压缩成像：传统的成像方式完全不同;压缩感知成像可以从以远低于Nyquist采样率的采样率获取高质量的图像,有效降低了传感器数目与硬件成本,为微波、医疗成像提供了新的理论和方法,目前在医疗成像、光学成像、对地观测等领域得到了成功的应用.第一个被广泛认可的实际系统就是美国Rice大学Baraniuk等人研制出的单像素相机,类似的系统还有Kir研制的Analog-to-InformationConverter(AIC)、莱斯大学RBaraniuk教授研制的单像素相机和A/I转换器、麻省理工学院研制的MRIRF脉冲设备、麻省理工学院WTFreeman教授研制的编码孔径相机、耶鲁大学研制的超谱成像仪、伊利诺伊州立大学OMilenkovic研制的DNA微阵列传感器,以及我国中科院研制的CS滤波器和混沌腔等.美国DARPA(DefenseAdvancedResearchProjectsAgency)资助的MONTAGE(MultipleOpticalNon-RedundantApertureGeneralizedSensors)研究计划极具应用潜力,目前已完成焦平面编码等技术可行性的实验验证.在国内,自2009年973计划开始资助中科院电