压缩感知及应用[1]

第31卷第3期2010年3月MICROCOMPUTERAPPLICATIONS微　计　算　机　应　用Vol131No13Mar12010

压缩感知及应用

李卓凡

2131,2　闫敬文2(11韩山师范学院物理与电子工程系　潮州　521041汕头大学工学院　汕头　515063)

摘要:传统的信号采样必须遵循香农采样定理,产生的大量数据造成了存储空间的浪费。压缩感知(CS)提出一种新的采样理论,它能够以远低于奈奎斯特采样速率采样信号。压缩感知的基本论点是如果信号具有稀疏性,关的随机矩阵并获得远少于信号长度的测量值,再通过求解优化问题,压缩感知适用的基本条件:稀疏性和非相干性,测量矩阵设计要求,RIP。仿真结果表明当采样个数大于K×log(N/K),就能将N。

关键词:压缩感知　观测矩阵　稀疏性RIcatonofCompressiveSensing

LIZhuofan,YANJingwen

(1Physicsandelectronicengineeringdepartment,HanshanNormalCollege,Chaozhou,521041,China;

2CollegeofEngineering,ShantouUniversity,Shantou,Guangdong,515063,China)

Abstract:ConventionalapproachestosamplingsignalsfollowShannonprinciple1Ittakegreatcostsondatastorage1Inthispaper,thetheoryofCompressivesensingisintroduced1CompressivesensingprovidesanewsamplingtheorytosamplesignalbelowtheNyquistrate1Ifsignalorimageissparseinsomeorthonormalbasis,signalorimagecanberecoveredfromsmallnumberofmeasurementusinganoptimizationprocess1Thestructureofthesignalispreservedinthemeasurementandthemeasurematrixisincoherentwiththeor2thonormalbasis1CSreliesontwoprinciples:sparsityandincoherence1RIPprincipleistheprecondictionofdesigningreconstructionalgorithm1TheapplicationofCStheoryareintroducedandthesimulationisillustratedindetails1ThesimulationshowthatthesignalcanbereconstructedstablelywhenthenumberofsamplesislargerthanK×log(N/K)1

Keywords:compressivesensing,measurementmatrix;sparsity,RIP

1　引言

传统的信号采样以奈奎斯特采样定理为基础。在获取信号时,为了不丢失信号的信息,采样频率必须大于信号中最高频率的两倍,才能精确重构信号。但是随着科技的迅速发展,高分辨率的数码装置的采样产生了庞大的数据,如何更高效地处理这些数据并最大限度地节省存储和传输的成本是一大难题。实际上采样得到的大部分数据是不重要的,在信号或图像的处理过程中,只保留了某些重要的数据,舍弃了大量的剩余数据,重构后的信号或图像并不会引起视觉上的差异。于是科学家们提出一个构想,既然采集到的数据大部分都是不重要的,可以被丢弃,能否直接地采集那部分重要的、最后没有被丢弃数据,并且能够精确地本文于2009-12-14收到。

3基金项目:国家自然科学基金(项目批准号:40971206)。

3期　　李卓凡等:压缩感知及应用13重构原始信号或图像。

[1,9]在2004年,由Donoho等人提出了压缩感知(compressedsensing,简称CS)理论。压缩感知理论表

示:如果信号通过某种变换(如傅立叶变换,小波变换等)后,是可稀疏表示或可压缩的,则可设计一个与变换基不相关的测量矩阵测量信号,得到的测量值通过求解优化问题,可实现信号的精确或近似重构。测量后,信号f由N维减少到M维(M

2　压缩感知基本理论

N假设有一信号f(f∈R),长度为N,基向量为Ψi(i=1,2,・・・,N),对信号进行变换:

N

f=αψ或∑ii

i=1αf=Ψ(1)

显然f是信号在时域的表示,α是信号在Ψ域的表示K个是非零值(N>>K);或者α。信号的可稀疏表示是压缩感知的先验条件。

:

(1)MN(M

(2)从M×1维的测量向量重构信号

。

211　测量矩阵

用一个与变换矩阵不相关的M×N(M

信号进行线性投影,得到线性测量值y:

y=Φf(2)

测量值y是一个M×1矩阵,这样使测量对象从N维降为M维

(如图1(a)所示)。观测过程是非自适应的,即测量矩阵Φ的选择

不依赖于信号f的。测量矩阵的设计要求信号从f转换为y的过程

中,所测量到的K个测量值不会破坏原始信号的信息,保证信号的

精确重构。

由于信号f是可稀疏表示的,(2)式可以表示为下式:

Ψα=Θα(3)y=Φf=Φ

其中Θ是一个M×N矩阵。转换过程如图1所示。

(3)式中,方程的个数远小于未知数的个数(即M

程无确定解,无法重构信号。但是,由于信号是K稀疏的(K

M),若(3)式中的Θ满足有限等距性质(RestrictedIsometryProper2

ty,简称RIP),即对于任意K稀疏信号f和常数δk∈(0,1),矩阵

Θ满足:

1-δk≤Θff2

22≤1+δk(4)图1　压缩感知观测流程图

(K=3)则K个系数能够从M个测量值准确重构。RIP性质的等价条

件是测量矩阵Φ和稀疏基Ψ不相关。

　14　　微　计　算　机　应　用

目前,用于压缩感知的测量矩阵主要有以下几种:高斯随机矩阵

[2,7][2]2010年　[2],二值随机矩阵(伯努力矩阵),傅立叶随机矩阵,哈达玛矩阵,一致球矩阵等。

212　信号重构

RIP性质从理论上保证K稀疏信号能由M个测量值y重构长度为N的信号f。这类求逆问题的传统解法可以通过求解最小l2范数解决:

α=argminα2　s1t1　Θα′=y

∧∧∧(5)(5)的近似解为:α=ΘT(ΘΘT)-1y。但是最小化l2范数得到的向量α是非稀疏的,而我们要寻找的向

量α是K稀疏的,所以这种方法并不能找到我们需要的解,进而采用求解l0范数来代替:

α=argminα0　s1t1　Θα′=y(6)运用最小l0范数法,只需M=K+1个测量值,就能精确重建K稀疏信号。求解(6)式需要列出α中非零值位置的N

∧种可能组合,NP-Donoho等人提

出用l1代替范数l0范数会得到相同的解:

αmins1=(7)

(N/K)时,用l1范数能够高概率地精确重建K稀

[5]疏向量,,可以转化成线性规划问题求解。典型算法有基追踪(BasisPur2

[8]suit,BP

),,迭代阈值法等。　

[3][4]　其他重构算法还有正交匹配追踪算法(OMP),最小全变分法以及一些综合的改进算法。∧

3　应用

使用一定数量的非相关测量值能够高效率地采集可压

缩信号的信息,这种特性决定了压缩感知应用的广泛性。

例如低成本数码相机和音频采集设备;节电型音频和图像

采集设备;天文观测;网络传输;军事地图;雷达信号处理等

等。以下归纳了压缩感知几个方面的应用:

(1)数据压缩

在某些情况下,稀疏基Ψ在编码中是未知的或在数据

压缩中是不能实际实现的。由于测量矩阵Φ是不需要根

据Ψ的结构来设计的,随机测量矩阵可认为是一个通用的

编码方案,而Ψ只有在解码或重建信号的时候需要用到。

这种通用性在多信号装置(如传感器网络)的分布式编码

特别有用。

(2)信道编码

压缩感知的稀疏性、随机性和凸优化性,可以应用于设

计快速纠错码以防止错误传输。

图2　源信号及重构信号(3)逆问题

在其他情况下,获取信号的唯一方法是运用特定模式的测量系统Φ。然而,假定信号存在稀疏变换基Ψ,并与测量矩阵Φ不相关,则能够有效的感知的信号。这样的应用在文献[4]中的MR血管造影术有提到,Φ记录了傅立叶变换子集,所得到的期望的图像信号在时域和小波域都是稀疏的。

(4)数据获取[6]

3期　　李卓凡等:

压缩感知及应用15在某些重要的情况下,完全采集模拟信号的N个离散时间样

本是困难的,而且也难以对其进行压缩。而运用压缩感知,可以

设计物理采样装置,直接记录模拟信号离散、低码率、不相关的测

量值,有效地进行数据获取。

基于RIP理论,目前已研制出了一些设备,有莱斯大学研制的

单像素相机和A/I转换器,麻省理工学院研制的编码孔径相机,

耶鲁大学研制的超谱成像仪,麻省理工学院研制的MRIRF脉冲

设备,伊利诺伊州立大学研制的DNA微阵列传感器。

4　仿真

源信号是一维稀疏信号,长度N=128,稀疏个数K=8。变换图3　重构误差曲线图

矩阵为傅立叶正交变换矩阵,编码端采用高斯测量矩阵,解码端采用正交匹配追踪法。:

(1)产生测量矩阵(随机高斯矩阵),并对信号f,(2)产生傅立叶变换矩阵,(3)运用正交匹配追踪算法,k),即变换系数α=ΘT(ΘΘT)-1y。

(4)由αf图2,当测量次数M=56时,重构信号与源信号误差为112183×-1410,;M=15时,重构信号与源信号误差为111847,这是由于测量次数太少造成的。理论上当测量次数M≥K×log(N/K)=32,N维信号的K个最大值能稳定地重建出来。在实际应用中是否与理论吻合呢?表一是测量次数分别取M=15,17,20,22,24,25,26,28,30,32,40,56,通过实验仿真得到结果,图3为重构误差曲线图。可以看出当M小于25时,重建结果极不稳定,误差波动大;当M接

-14近但小于32时,误差的数量级是10,但波动范围较大,总体误差也偏大;当M大于或等于32时,误差小

且误差范围稳定,重建结果稳定。因此,为了保证重建结果的稳定性,减少或避免出错,观测次数必须取偏大于32次。

表1　M=15,17,20,22,24,25,26,28,30,32,40,56时重构信号误差

测

量

次

数

M[***********]324056

919588E+00211075E-14118548E-14116814E-14119434E-14119721E-14118874E-14116068E-14115185E-14113166E-14116096E-14112305E-14118652E+00712500E-02119760E-14118391E-14813500E-02210252E-14115964E-14116501E-14211640E-14114791E-14113448E-14114450E-14111792E+00212551E-14216961E-14110680E-01111963E+00116442E-14116173E-14119044E-14113191E-14113786E-14116757E-14112704E-14111364E+00119725E-14413870E-01913100E-02115314E-14116646E-14116609E-14118504E-14114924E-14116105E-14112977E-14112978E-14重112546E+00

构

误112341E+00

差214215E+00δ

713730E-01816200E-02117744E-14614400E-02118372E-14114485E-14119613E-14113673E-14113965E-14114895E-14116285E-14113018E-14416470E-01112426E+00813500E-02119370E-14116890E-14119682E-14115456E-14114561E-14114061E-14114712E-14112592E-14610000E-02215080E-01812200E-02116773E-14114257E-14119393E-14117427E-14115401E-14114785E-14115429E-14113042E-14215480E-01817000E-02118747E-14212555E-14115772E-14115514E-14115599E-14115657E-14114732E-14112898E-14111822E-14112837E+00216544E-14216961E-14413000E-01117938E-14115144E-14119915E-14210860E-14115407E-14116488E-14115659E-14111696E-14118390E+00916700E-02111892E+00119495E-14410910E-01114674E-14210134E-14116578E-14116696E-14115962E-14113028E-14115923E-14110451E+00110620E-01112569E+00212442E-14117367E-14211685E-14210926E-14116984E-14114535E-14113744E-14115029E-14112701E-14平

均211777E+00110374E-01410593E-01718182E-02115354E-01116906E-14118436E-14116972E-14115560E-14114774E-14114756E-14值113021E-14

　16　　微　计　算　机　应　用2010年　5　结束语

本文介绍了压缩感知的框架理论;通过仿真程序模拟了信号测量及重构的过程,并用实验数据表明,测量次数的选择必须大于K×log(N/K),否则信号不能稳定地重构,出错概率大。但为了尽量地压缩数据,测量次数也不宜太大。CS理论的诞生说明香农采样定理并不是获得信号的唯一途径。它运用了信号的稀疏性,对信号进行测量,通过解决凸优化问题重构信号。CS理论的前提是稀疏性(sparsity)和不相关性(inco2herence),前者由信号本身决定,后者由感知系统决定。观测矩阵的随机不相关性是准确恢复信号的保证,因此观测矩阵的设计是CS的关键部分。观测矩阵若满足RIP性质,那么K3log(N/K)个采样就能将N维信号的K个最大值稳定地重建出来。对观测矩阵的研究是目前压缩感知理论的一个热点,其中包括观测矩阵的构造、优化算法及硬件实现等等。

将压缩感知理论应用于硬件设计是该理论实用性的标志,本文总结了CS理论的实际应用,这是该理论迈向实用化的一大步,但目前仅能处理有限难数据的信号,无法处理无限维信号,。压缩感知作为一门新生的理论,虽然在很多方面还不完善,,开创了广阔的研究前景。

参考[1]DONOHOD1CompJ]Theory,2006,52(4):1289-1306

[2]EJtimrecoveryfromrandomprojections:Universalencodingstrategies[J]1IEEETrans1Info2006,(12):5406-5425

[3]TroPPJ,A1Signalrecoveryfromrandommeasurementsviaorthogonalmatchingpursuit1TransactionsonInformationTheo2ry,2007,53(12):4655-4666

[4]CandsE,RombergJ,TaoT1Robustuncertaintyprinciples:Exactsignalreconstructionfromhighlyincompletefrequencyinforma2tion1IEEETransactionsonInformationTheory12006,52(2):489-509

[5]RBaraniuk1Alectureoncompressivesensing[J]1IEEESignalProcessingMagazine1July2007,24(4):118-121

[6]EJCandèsandMBWakin11AnIntroductiontoCompressiveSampling[J]1IEEESignalProcessingMagazine1March2008,25(2):21-30

[7]ZOUJ,GILBERTAC,STRAUSSMJ,etal1TheoreticalandexperimentalanalysisofarandomizedalgorithmforsparseFouriertransformanalysis[J]1JournalofComp-utationalPhysics,2006,211(2):572-595

[8]FIGUEIREDOMAT,NOWAKRD,WRIGHTSJ1Gradientprojectionforsparsereconst-ruction:applicationtocompressedsens2ingandotherinverseproblems[J]1IEEEJ-STSP,2007,1(4):586-598

[9]ECandès1Compressivesampling[A]1ProceedingsoftheInternationalCongressofMathematicians[C]1Madrid,Spain,2006,3:1433-14521

[10]D1Takhar,V1Bansal,M1Wakin,M1Duarte,D1Baron,J1Laska,K1F1Kelly,andR1G1Baraniuk1Compressedsensingcamera:Newtheoryandanimplementationusingdigitalmicromirrors1inProc1Comput1ImagingIVSPIEElectronicImaging1SanJose,Jan120061

作者简介

李卓凡,女,(1979-),实验师,主要研究方向为图像处理。

闫敬文,男,(1964-),教授,博导,主要研究方向为数字视频处理、SAR图像处理与识别、小波分析及应用。