压缩感知新技术专题讲座_三_第5讲压缩感知理论中的信号重构算法

第33卷第2期

2012年6月军　事　通　信　技　术JournalofMilitaryCommunicationsTechnologyVol.33No.2Jun.2012

压缩感知新技术专题讲座(三)

第5讲　压缩感知理论中的信号重构算法研究

吴海佳,张雄伟,陈卫卫,曾　理1231

(1.解放军理工大学指挥自动化学院研究生2队,江苏南京210007;

2.解放军理工大学指挥自动化学院信息作战系;3.解放军理工大学指挥自动化学院计算机系)

摘　要:信号重构作为压缩感知理论的核心之一,是指从长度为m的测量向量Y重构长度为n(m n)的

稀疏信号Θ的过程。由于测量次数远小于原始信号维度,信号重构成为欠定方程求解问题,一般没有确定解。然

而,若Θ满足一定的稀疏性条件,问题有确定解。文章首先从解析几何角度出发,分析了压缩感知中稀疏信号重构

的原理,并对已有的两大类重构算法分别进行介绍:一类是针对l0范数最小化的一系列贪婪算法,一类是针对l1

范数最小化的凸优化算法。对前一类算法,选取了代表性的OMP、ROMP、CoSaMP和SAMP算法进行研究,并

分析了它们的优缺点;对后一类算法,着重阐述了将BP问题转换为LP问题的推导过程,并介绍了两类经典的凸

优化算法:BP-Simplex和BP-Interior。最后,展望了信号重构算法的研究前景。

关键词:压缩感知;信号重构;匹配追踪;凸优化

中图分类号:TN911.7文献标识码:A文章编号:CN32-1289(2012)02-0093-07

SurveyonSignalReconstructionAlgorithmsinCompressed

SensingTheory

WUHai-jia,ZHANGXiong-wei,CHENWei-wei,ZENGLi

(1.PostgraduateTeam2ICA,PLAUST,Nanjing210007,China;

2.DepartmentofInformationOperationStudiesICA,PLAUST;3.DepartmentofComputerScienceICA)1231

Abstract:Signalreconstruction,asoneofthecoresofthecompressedsensingtheory,refers

totheprocessofreconstructingthesparsesignalΘoflengthnfromthemeasuredvectorYof

lengthm,wherem n.Asthenumberofmeasurementsismuchsmallerthanthedimensionof

theoriginalsignal,thereconstructionprocessbecomesanissueofsolvingtheunderdetermined

equations,whichgenerallyhasnodeterminedsolution.However,ifΘsatisfiesonemore

conditionofthesparsity,thisissuewillhaveadeterminedsolution.Inthispaper,firstlythe

principleofsparse-signalreconstructionwasanalyzedfromtheperspectiveofvectorspace.

Then,twogroupsofreconstructionalgorithmsweredescribedseparately:aseriesofgreedy

algorithmsforL0-normminimizationissueasone,andaseriesofconvexoptimizationalgorithms

forL1-normminimizationissueastheother.Fortheformergroup,fourrepresentative

algorithms,includingOMP,ROMP,CoSaMP,andSAMP,werestudied,andtheiradvantages

anddisadvantagesanalyzed;Forthelattergroup,focuswasonthederivationofconvertingBP

issuetoLPissue,andtwotypesofclassicalconvexoptimizationalgorithmsdescribed,including

BP-SimplexandBP-Interior.Finally,theprospectsfortheresearchofsignalreconstruction

algorithmsweregiven.

收稿日期:2012-01-20;修回日期:2012-03-22:(),,博士生.

94

Keywords:

optimization军事通信技术2012年compressedsensing;signalreconstruction;matchingpursuit;convex

压缩感知是应用数学与信号处理领域中的一个新理论,近年来已成为研究的热点。它由Donoho等人于2006年首次提出,之后便迅速引起国内外相关领域研究者的高度重视。压缩感知理论包括三个关键技术:信号的稀疏表示、测量矩阵的设计与重构算法。

重构算法是压缩感知理论的核心之一。至今,已有众多国内外学者在信号重构领域做出了新的研究和探索。Candes等人首先证明了信号重构问题可以通过求解最小l0范数问题解决;Donoho指出求解最小l0范数是NP问题,因而无法直接求解;此后,研究者们提出了一系列求得次优解的算法,主要包括匹配追踪系列算法、最小l1范数法等。前者属于贪婪算法,该类算法能高效重构稀疏信号,是目前信号重构领域研究的热点之一;后者属于凸优化算法,在线性规划领域已有若干成熟的方法。

1　信号重构原理

从本质上讲,压缩感知理论中的信号重构问题就是寻找欠定方程组的最稀疏解的问题。l0范数刻画的是信号中非零元素的个数,因此信号重构问题可以用下式进行描述:

min‖Θ‖0　s.t.Y=HΘ(1)

其中,Θ是长度为n的稀疏信号,Y是长度为m的测量向量(m n),H为满足RIP条件[1]的m×n维观测矩阵。

为了直观地说明信号重构的原理,QiDai和WeiSha在参考文献[2]中引入一个最简单的例子。假设

T1,θ2),则Θ的l0、l1和l2范数在二维直角坐标系中对应的边界分别是Θ是一个长度为2的稀疏信号(θ

十字、菱形和圆形,如图1(a)、图1(c)、图1(d)所示;l0.5范数如图1(b)所示。在该二维直角坐标系下,式(1)的可行域为一条直线。若直线与范数边界的交点落在坐标轴上,则该交点所表示的重构解为稀疏解,否则不稀疏。

显然,从图1可以看出:当0≤p

≤1时,lp范数的边界与直线的交点

总是落在坐标轴上;当p>1时,交点

几乎不会落在坐标轴上。

这个例子可以推广到更高维的空

间中。在三维空间中,可行域为一组平　　(a)p=0　　　　(b)p=0.5　　　(c)p=1　　　(d)p面的交集;在三维以上的空间,可行域=2

为一组超平面的交集。图1　lp范数的几何学意义

参考文献[3,4]从理论上证明了,

在一定条件下lp(0≤p≤1)范数最小问题具有等价性。当0≤p<1时,lp范数最小问题是非凸优化问题,解决该问题有一系列贪婪算法,该类算法复杂度低,且在满足一定的条件时,可快速收敛到局部最优解;当p=1时,lp范数最小问题是凸优化问题,解决凸优化问题的一系列算法可精确收敛到全局最优解,但普遍计算量大,算法复杂度高。

2　信号重构算法

针对l0范数最小问题,目前已经提出若干较成熟的匹配追踪类算法,有代表性的包括匹配追踪算法MP(MatchingPursuit)、正交匹配追踪算法OMP(OrthogonalMatchingPursuit)、正则正交匹配追踪算法

[6]ROMP(RegularizedOrthogonalMatchingPursuit)、压缩采样匹配追踪算法CoSaMP(Compressive、e。[7][8][5]

第2期吴海佳等:压缩感知理论中的信号重构算法研究

[9]95l1范数最小化问题可以使用一种称作基追踪BP(BasisPursuit)的优化原则进行求解,因此也可以将

其称为BP问题。BP问题可以转换成经典的线性规划LP(LinearProgramming)问题。LP问题已经存在若干成熟的凸优化算法,有代表性的包括单纯形法(SimplexMethod)、内点法(InteriorPointMethod)等;除此之外,还有一些对LP问题的约束条件变形后得到的快速算法[10],包括梯度投影法GPSR(Gradient

[11][12]ProjectionforSparseReconstruction)、同伦算法HA(HomotopyAlgorithm)、最小角度回归法LARS

(LeastAngleRegression)[13]等。

2.1　匹配追踪算法

匹配追踪类稀疏重构算法解决的是最小l0范数问题,最早提出的是MP算法和OMP算法,其本质是一种贪婪迭代算法。MP算法的基本思想是在每一次迭代的过程中,从过完备原子库(测量矩阵)中选择与信号最匹配的原子(测量矩阵中的列向量)来进行稀疏逼近, …… 此处隐藏：12187字，全部文档内容请下载后查看。喜欢就下载吧 ……