结构化压缩感知研究进展

发布时间：2017-01-03 11:17

本文关键词：结构化压缩感知研究进展，由笔耕文化传播整理发布。

第39卷第12期2013年12月；自动化学报；ACTAAUTOMATICASINICA；Vol.39,No.12December,201；结构化压缩感知研究进展；刘芳1,2；武娇1,2,3；杨淑媛2；焦李成2；摘要压缩感知(Compressivesensin；压缩感知,压缩观测,稀疏表示,信号重构,结构模型；刘芳,武娇,杨淑媛,焦李成.结构化压缩感知研究进；

第39卷第12期2013年12月

自动化学报

ACTAAUTOMATICASINICA

Vol.39,No.12December,2013

结构化压缩感知研究进展

刘芳1,2

武娇1,2,3

杨淑媛2

焦李成2

摘要压缩感知(Compressivesensing,CS)是一种全新的信息采集与处理的理论框架.借助信号内在的稀疏性或可压缩性,可从小规模的线性、非自适应的测量中通过非线性优化的方法重构信号.结构化压缩感知是在传统压缩感知基础上形成的新的理论框架,旨在将与数据采集硬件及复杂信号模型相匹配的先验信息引入传统压缩感知,从而实现对更广泛类型的信号准确有效的重建.本文围绕压缩感知的三个基本问题,从结构化测量方法、结构化稀疏表示和结构化信号重构三个方面对结构化压缩感知的基本模型和关键技术进行详细的阐述,综述了结构化压缩感知的最新的研究成果,指出结构化压缩感知进一步研究的方向.关键词引用格式DOI

压缩感知,压缩观测,稀疏表示,信号重构,结构模型

刘芳,武娇,杨淑媛,焦李成.结构化压缩感知研究进展.自动化学报,2013,39(12):1980?199510.3724/SP.J.1004.2013.01980

ResearchAdvancesonStructuredCompressiveSensing

LIUFang1,2

WUJiao1,2,3

YANGShu-Yuan2

JIAOLi-Cheng2

AbstractCompressivesensing(CS)isanewlydevelopedtheoreticalframeworkforinformationacquisitionandpro-cessing.Usingthenon-linearoptimizationmethods,thesignalscanberecoveredfromfewerlinearandnon-adaptivemeasurementsbytakingadvantageofthesparsityorcompressibilityinherentinrealworldsignals.Structuredcom-pressivesensingisanewframeworkwhichcantreatmoregeneralsignalclassestoachievetheaccurateande?ectivereconstructioninpracticebyintroducingthepriorinformationmatchingwithdataacquisitionhardwareandcompli-catedsignalmodelstotraditionalcompressivesensing.Inthispaper,thebasicmodelsandkeytechniquesofstructuredcompressivesensingareintroducedintermsofthestructuredmeasurements,thestructureddictionaryrepresentationandthestructuredsignalreconstruction,whichcorrespondtothreebasicaspectsofcompressivesensing,andtherecentdevelopmentsofstructuredcompressivesensingarereviewedindetail.Finally,thecurrentandfuturechallengesofthestructuredcompressivesensingarediscussed.Keywordsturedmodel

Compressivesensing(CS),compressivemeasurement,sparserepresentation,signalreconstruction,struc-

CitationLiuFang,WuJiao,YangShu-Yuan,JiaoLi-Cheng.Researchadvancesonstructuredcompressivesensing.ActaAutomaticaSinica,2013,39(12):1980?1995

收稿日期2012-09-10录用日期2013-04-09

ManuscriptreceivedSeptember10,2012;acceptedApril9,2013国家重点基础研究发展计划(973计划)(2013CB329402),国家自然科学基金(61072106,61072108,61173090,61272023),高等学校学科创新引智计划(111计划)(B07048),教育部长江学者和创新团队发展计划(IRT1170),国家教育部博士点基金(20110203110006),智能感知与图像理解教育部重点实验室开放基金(IPIU012011002)资助SupportedbyNationalBasicResearchProgramofChina(973Program)(2013CB329402),NationalNaturalScienceFounda-tionofChina(61072106,61072108,61173090,61272023),FundforForeignScholarsinUniversityResearchandTeachingPro-grams(111Project)(B07048),ProgramforCheungKongSchol-arsandInnovativeResearchTeaminUniversity(IRT1170),NationalResearchFoundationfortheDoctoralProgramofHigherEducationofChina(20110203110006),andtheOpenResearchFundProgramofKeyLaboratoryofIntelligentPer-ceptionandImageUnderstandingofMinistryofEducationofChina(IPIU012011002)本文责任编委王聪

新兴的压缩感知(Compressivesensing,CS)为信息采集提供了全新的方法.与传统的Nyquist采样相比,CS以压缩形式(即低采样率)直接感知具有稀疏或可压缩性的对象,而不是先以高速率进行采样,然后再对数据进行压缩,因此CS为解决传统采样方法面临的高成本、低效率、信息冗余以及数据存储和传输的资源浪费等问题带来了新的契机.CS领域的研究始于Cand`es等[1?4]和Donoho[5]开创性的工作,他们证明了具有稀疏或可压缩性的有限维信号,可从小规模的线性、非自适应的测量中使用非线性优化的方法获得恢复.CS理论一经提出就备受关注,之后的几年涌现出大量的相关研究,并在许多工程领域实现了CS的应用,例如欠Nyquist采样系统[6]、压缩成像系统[7]、压缩传感网络[8]等.最

sity,Xi??an7100712.KeyLaboratoryofIntelligentPercep-tionandImageUnderstandingofEducation,XidianUniversity,Xi??an7100713.CollegeofSciences,ChinaJiliangUniversity,Hangzhou310018

RecommendedbyAssociateEditorWANGCong

1.西安电子科技大学计算机学院西安7100712.智能感知与图像理解教育部重点实验室西安7100713.中国计量学院理学院杭州310018

1.SchoolofComputerScienceandTechnology,XidianUniver-

典型的应用例子是在医学成像领域,CS成像在保持诊断质量的同时将儿科的核磁共振成像(Nuclearmagneticresonanceimaging,NMRI)的速度提高了7倍[9].这种基于CS理论的新型成像方法,将对医学成像领域中昂贵的成像器件的设计产生重要的影响.

自2006年CS理论提出以来,国际与国内出现了许多CS理论与应用研究的课题组和科研机构,召开了众多相关的研讨会,并且在IEEE的信息论、信号处理及图像处理等国际知名期刊涌现出上百篇涉及CS理论与应用方面的文献.其中一些关于传统CS理论的优秀的综述性文献[1,10?15]对CS的理论基础、基本问题、研究方法以及CS的应用前景进行了详细的介绍.上述文献指出,传统CS理论是以信号的稀疏性或可压缩性为基础的,研究的基本内容包括信号的稀疏表示、压缩测量(采样)方法设计和信号重构算法设计.传统CS的工作多集中于使用随机测量对有限维的信号进行低速观测,以信号固有的变换稀疏性作为先验信息来重构信号,没有考虑时间连续信号的情况和应用CS理论所必须的硬件系统.为此与数据采集硬件系统和复杂信号模型相匹配的先验信息被引入到传统CS,这些先验信息在CS中的应用主要表现在三个方面:1)结构化的测量方法,即传统CS中的随机测量被与信号相匹配的结构化测量框架所代替;2)结构化字典下的表示,即获得信号低维结构的稀疏表示(即结构稀疏表示);3)结构化的CS重构,即在信号的重构中使用能够对更为广泛类型的信号(包括无限维信号)进行描述的结构先验模型.由此传统CS理论得到推广,逐步形成CS的新的理论框架—结构化CS理论[16].

本文对新的结构化CS理论的研究状况进行综述.在第1节中,首先概述传统CS的数学模型;其次,在第2节中介绍结构化CS中的几种低维结构模型;在第3节中,围绕CS理论的三个基本问题,对结构化CS的相关研究方法进行详细的综述;最后,在第4节中展望未来的研究方向.

若令Φ=ΘΨ,式(1)可转化为

y=ΘΨx=Φx(2)

Φ被称为CS信息算子.

与压缩采样过程相对的逆问题是从测量y中

??,从而估重构信号f.求解式(2)获得变换系数x

??.但该问题是欠定的,具有无穷多个解.CS计f

理论以x的稀疏性作为约束条件,大大减少了问题可行解的个数.这时,求解式(2)是寻找线性系统稀疏解的过程,一般被称为稀疏逼近(Sparseapproximation)[17],出现在诸如统计学、信号处理、机器学习、编码理论和逼近理论等许多领域.CS重构是稀疏逼近的一种特殊形式.

信号的传统压缩感知过程如图1所示,其中压缩观测、稀疏表示和信号优化重构这三个基本模块是CS理论研究的三个重要方向.信号的稀疏性是CS的必备条件,非相关的观测是CS的关键,非线性优化是CS重构信号的手段[15]

图1

Fig.1

传统压缩感知框架

Frameoftraditionalcompressivesensing

2信号的低维结构模型

一般来说,包含着先验知识的模型对寻找或处理我们感兴趣的信号是很有帮助的,而我们研究的信号往往具有各种不同的潜在的低维结构,也就是说,高维信号的自由度通常远低于信号的维数.近年来,在许多领域出现了对信号的低维结构模型的研究[16,18].本节将介绍几个在CS中常用的信号结构模型.

2.1稀疏信号模型

稀疏信号模型是信号处理领域普遍使用的最简单的模型,传统CS理论正是以其为基础构建起来的.从数学的定义来说,当信号f∈RN在某个基或字典下的变换系数x中仅含有k个非零项,即??x??0=k(k??N),称f是k-稀疏的.稀疏性体现出在很多情况下高维信号实际仅包含了远低于其维数的少量信息.实际场景中的大部分信号并不是精确稀疏的,但能够由k-稀疏信号很好地逼近,通常称这些信号是可压缩的.对稀疏信号x∈RN,所有k-稀疏信号构成的集合记为

1传统压缩感知

传统Nyquist采样通过均匀采样获取数据,而CS系统则是以信号与观测函数之间的内积的形式来对数据进行采样.假设信号f∈RN在某个正交字典Ψ∈RN×N下具有稀疏表示,即f=Ψx,变换系数x是稀疏的,那么给定与Ψ不相关的观测矩阵Θ∈RK×N(K??N),我们可获得K维压缩的线性测量(投影):

y=Θf(1)

Σk={x:??x??0≤k}

|Σk|表示k-稀疏信号的个数,则|Σk|=CN.

(3)

这些少量的测量中包含了重构信号f的充足信息.

如上所述,压缩测量中重构信号是一个欠定问题,过去十年许多研究者从理论和求解算法上对此进行了研究.理论表明,在稀疏模型约束下,当观测矩阵满足有限等距性质(Restrictedisometryprop-erty,RIP)[2,19?22],或当Φ中线性相关的列的最小数目spark(Φ)大于2k时[23],式(2)有唯一确定的解.

稀疏矩阵X的充分必要条件是

|supp(X)|<

spark(Φ)?1+rank(X)

(5)

2.2多测量向量模型

在实际应用中,研究的复杂信号往往隐含着稀疏性之外的一些潜在的结构信息,从而出现如何将信号结构与稀疏性相结合以获得更优结果的问题.

对有限维信号的重构问题,传统CS由单重测量恢复未知的稀疏信号,被称为单测量向量(Singlemeasurementvector,SMV)模型.作为SMV模型的推广,多测量向量(Multiplemeasurementvec-tor,MMV)模型是CS中使用的第一类结构模型.从多重测量恢复多个未知的稀疏信号,被用于分布式压缩感知(DistributedCS)[24]的联合稀疏重构问题.MMV问题在信号处理领域的研究已超过十年,最初在脑磁图数据处理中提出[25],之后被应用于阵列信号处理、认知无线电、多带通信以及DNA微阵列等[16].

MMV模型具有如下形式:

文献[26?27]证明了当用rank(Y)代换式(5)中的rank(X)时,仍能够保证从Y唯一地确定X,并提出可获得更优性能的基于Y的秩信息的重构算法.文献[28]证明了甚至在有无穷多个向量xq的情况下,上述唯一恢复的条件也是充分的.

上述研究表明,具有较大的秩的矩阵X能够从比支撑个数少得多的测量中恢复;具有较大支撑的矩阵X能够从与支撑个数相同的测量恢复.当rank(X)=k,且spark(Φ)的最大的可能值等于K+1时,由式(5)可得K≥k+1,也就是说在最理想的情况下,MMV模型的每个信号仅需k+1个测量即可保证唯一重构,这比传统CS(或SMV模型)中由spark性质获得的保证唯一恢复的测量数量2k[23]要低得多.

2.3子空间联合模型

这种结构化模型可以推广至无限维空间.对具有某些结构的N维k-稀疏信号,可能仅需将信号的支撑限制在Σk中的一个更小的子集上就能够很好地刻画信号的结构.例如当信号的非零系数以某种聚集形式出现时,就可以由子空间联合(Unionsofsubspaces)模型来刻画信号的这种结构.信号的子空间联合模型是对稀疏模型的扩展,能够用于刻画包括维数有限和无限的更多类型的信号.

在子空间联合模型中,如果已经知道x位于L个可能的子空间U1,···,UL中的某个子空间,那么x一定位于这L个子空间的并中[16,29],即

Y=ΦX+V(4)

其中X=[x1,···,xQ]∈RN×Q是信号矩阵,表示由Q个信号xq∈RN(q=1,···,Q)构成的信号集;Y=[y1,···,yQ]∈RK×Q是多测量矩阵,Φ∈RK×N是CS信息矩阵,V∈RK×Q是Gaus-sian白噪声矩阵.当Q=1时,式(4)退化为SMV模型.

MMV模型假设信号xq(q=1,···,Q)是k-稀疏的,并且具有相同的稀疏支撑,即非零值出现在相同的位置.定义?=supp(X)=∪qsupp(xq)为X的非零行的位置标识集,则X最多有k个非零行,即|supp(X)|≤k,我们称X是k-联合稀疏矩阵[26].

对从多测量Y重构信号矩阵X的问题,可以通过求解Q个SMV问题,依次从yq恢复xq来重构X.但由于所有的信号xq(q=1,···,Q)都具有相同的支撑,因此可以期望利用这种联合结构信息来提高重构质量.也就是说,一般情况下重构X所需的测量的数量K×Q要小于S×Q,其中S是由传统CS方法在相同精度下重构单个信号xq所需的测量个数[16].

MMV模型的k-联合稀疏矩阵X满足rank(X)≤k,rank(X)是X的秩.文献[26]从理论上证明了从多测量Y=ΦX唯一确定k-联合

x∈U=

L??l=1

Ul(6)

其中,Ul(1≤l≤L)是RN中的k-维子空间,对应

于x中k个非零系数的某个特定的位置集合.与包

含所有可能的N维k-稀疏信号的集合Σk(由CN

个子空间的并构成)相比,L往往远小于CN.

当前还没有统一的方法来处理所有的联合模型,研究者们对在一些特殊类型的子空间联合模型下的信号采样和恢复问题做出了相关的理论和应用研究[16].最简单的联合模型为有限个子空间的联合(Finiteunionofsubspaces,FUS)模型,其中子空间的个数和维数都是有限的.

文献[30]中提出的基于模型的CS(Model-basedCS)使用了FUS模型的一种特殊情况—结构稀疏支撑(Structuredsparsesupports)模型.该模型利用支撑的额外信息,如向量的非零元素的位置,使得U仅是Σk中的一部分.一种典型的结

图2

Fig.2

信号/图像的小波树结构

Wavelettreestructureofsignal/image

构稀疏支撑模型为树结构支撑(Tree-structuredsupports)模型[30].光滑的小波基为光滑和分段光滑的信号,包括自然图像,提供了稀疏或可压缩表示,并且这些信号和图像的小波系数自然地形成一种树状结构,具有大幅值的系数沿着树的分支而聚集,如图2所示.因此仅需要使用由与树结构相对应的子空间构成的并集来表示信号.

FUS模型的另一种特殊情况是子空间的稀疏和(Sparsesumsofsubspaces)模型,在这种模型中构成并集的每个子空间Ul是k个低维子空间的直和[16,31]:

k??Ul=Wlj(7)

j=1

等应用中

图3Fig.3

块稀疏向量[16]

Blocksparsevector[16]

其中{Wl1,···,Wlk}是给定的子空间集合,

dim(Wlj)=dl.因此不同的子空间Ul对应于从L个子空间Wlj中取出不同的k个子空间构成的和.当dim(Wlj)=1时,该模型退化为标准的稀疏模型.由此,可得到块稀疏(Blocksparsity)模型[32?34],即一个向量中的某些块等于零,其他部分不为零.图3给出一个块稀疏向量的例子.向量x分成5个块,其中阴影区域表示向量的10个非零元素,它们占了2个块,dl表示第l个块中包含的元素的个数.当对所有l,dl=1时,块稀疏性退化为标准稀疏性.统计学领域对块稀疏模型的性质进行了大量的研究[35?38],此外块稀疏模型也被用于DNA微阵分析[39?40]、稀疏通信信道均衡[41]和源定位[42]

对FUS模型,文献[29?31,43?44]将传统CS中的标准的RIP性质扩展为(U,δ)-RIP性质,证明了在常数δ足够小的情况下,为FUS模型设计的重构算法能够正确恢复稀疏向量x,并给出了保证稳定恢复所需的测量数量.文献[32]在子空间的稀疏和模型下对相关性(Coherence)进行了推广,定义了矩阵的块相关性(Block-coherence).文献[45?46]加入了子空间的内部结构,例如子空间的稀疏性,这相当于在对单个块的优化中加入表示稀疏性的正则项,从而得到多层的结构稀疏模式,该模型已被成功地应用于源识别和分离问题[46].

上述维数与个数都有限的子空间联合模型主要依赖于对模拟输入的离散化,没有考虑实际的硬件系统.为了能在硬件上真正地实现对具有结构的模拟信号的低速采样和重建,出现了对更为复杂的子空间联合模型的研究.这些子空间的联合模型包括子空间个数有限而子空间维数无限的模型、子空间维数有限而个数无限的模型和子空间维数和个数都无限的模型.

由于是对由联合子空间表示的模拟信号的低速采样,因此解决相同问题所使用的方法与上述有限

子空间联合模型中对离散化信号使用的方法有本质的区别.处理模拟信号的欠Nyquist采样问题的两个主要的框架是Xampling和有限更新率(Finite-rateofinnovation,FRI).Xampling框架主要处理那些能够被表示为有限个无限维子空间的并的模拟信号,例如多带模型[47].在这种模型中,模拟信号由带限信号的有限和构成,信号分量通常具有一个相对较小的带宽,但分布在一个比较大的频率范围内[48].另一类能够用子空间的并表示的信号是具有有限更新率的一类信号[49].依赖于特定的结构,这种模型对应于有限维子空间的无限或有限个并[6,50?51],可以刻画许多具有低自由度的信号.在这种情况下,每个子空间对应于参数值的某种选择,参数的可能取值的集合是无限维的,从而由模型张成的子空间的个数也是无限的.借助于子空间的这种模拟的并,使我们能够以低速率对模拟信号进行采样及实时处理,并且设计出有效的硬件,诸如使用调制器、低速率模数转换器(Analog-to-digitalconverter,ADC)和低通滤波等标准模拟设计组件实现模拟前端[16],从而促进模拟CS框架从理论到实际应用的发展.

其中λ>0为正则参数,??·??l为某种正则策略.模型(11)通常被称为鲁棒主成分分析(Robustprincipalcomponentanalysis,RPCA)[52].在RPCA的基础上,文献[53]提出低秩加稀疏矩阵分解的低秩表示(Low-rankrepresentation,LRR)模型处理多子空间问题.LRR模型表示为

minrank(Z)+λ??E??l,s.t.X=DZ+E

(12)

其中,D∈RN1×n是一个线性张成数据空间的字典,n为字典中原子的个数.类似于CS的l0-最小化问题,式(9)～(12)都是NP(Nondeterministicpolynomial)-难的.一类有效的方法是用矩阵的核范数??Z???(即矩阵Z的奇异值的和)代替rank(Z),将上述问题转化为凸优化问题进行求解[54?55].

3结构化压缩感知

传统CS在信号的采集与重建中仅将稀疏性作为唯一的先验信息,而结构化CS在传统CS的三个基本模块中引入了结构先验,即结构化的观测、结构化的字典和结构化的信号重构.结构化CS的理论框架如图4所示,可以看到,结构化CS以结构稀疏表示为基础,采用与信号匹配的结构化观测,在结构化先验下,对更为广泛的信号类实现更加有效的重构.接下来,我们将结合上一节给出的信号的各种低维结构模型对结构化CS理论的三个基本问题进行详细的介绍

2.4低秩矩阵模型

矩阵的稀疏性主要表现在两个方面:1)矩阵元素的稀疏性,即矩阵具有很少的非零元素;2)矩阵奇异值的稀疏性,即矩阵具有很少的非零奇异值,也就是说矩阵的秩非常小,这时我们称矩阵为低秩矩阵.对矩阵X∈RN1×N2,低秩矩阵的集合可表示为

{X∈RN1×N2:rank(X)≤r}(8)

??r

矩阵X的奇异值分解为X=i=1σiuivi,σ1,···,σr≥0为奇异值,u1,···,ur∈RN1和v1,···,vr∈RN2为相应的奇异向量.

近年来低秩矩阵重建已成为机器学习、信号处理、计算机视觉等领域研究的热点,矩阵的恢复与填充可看作是CS重构由一维信号到二维矩阵的推广.在低秩矩阵约束下,矩阵填充问题表示为

minrank(Z),s.t.P?(Z)=P?(X)

图4

Fig.4

结构化压缩感知框架

Frameofstructuredcompressivesensing

3.1结构化观测矩阵

为了保证从低维测量y重构信号x时式(2)存在确定的解,传统CS理论要求观测矩阵Θ与稀疏基矩阵Ψ不相关,从而使信息算子Φ以很大的概率满足RIP性质[10].除了RIP性质之外,相关性判别理论[56]、矩阵spark判别理论[57]以及测量算子零空间理论[58]等都可作为衡量观测矩阵处理稀疏信号的能力的判定标准.因此在传统CS中,主要设计满足上述性质的非自适应的观测矩阵.观测矩阵固定,不随信号发生改变.已证明传统CS广泛使用的随机观测矩阵(如随机Gaussian矩阵)能够以高概率保证RIP和不相关性,但当信号维数很高时,随机观测矩阵将导致复杂度过高的问题,不易实现.

在某些特定应用中,观测矩阵的类型通常受到

(9)

其中?为具有缺失元素的矩阵X中已知元素的标识集,P?(X)定义为

Xij,若(i,j)∈?

P?(Xij)=(10)

0,其他最近,一些同时考虑矩阵元素与矩阵奇异值的

稀疏性的低秩矩阵模型被用于矩阵恢复问题:

minrank(Z)+λ??E??l,s.t.X=Z+E

(11)

下载地址：结构化压缩感知研究进展_刘芳334_图文43.Doc

　　【】