分段正则化正交匹配追踪算法
- 格式:pdf
- 大小:2.32 MB
- 文档页数:9
基于ROMP算法的人脸识别
张文清;李龙雨;李芬兰;欧海燕
【期刊名称】《汕头大学学报(自然科学版)》
【年(卷),期】2015(030)001
【摘要】针对用传统方法进行人脸识别的识别率不够高的问题,本文在人脸识别中采用正则化正交匹配追踪算法(ROMP),并把其与基于NN,匹配追踪(MP),正交匹配追踪(OMP)的人脸识别算法进行了对比.该算法能一次从冗余字典中选取多个原子,并能够通过正则化准则对选取的原子进行再次筛选,获得最优的原子.实验结果表明,在不同特征提取方法和训练样本数改变的情况下,基于ROMP的人脸识别算法的识别率优于其他算法.
【总页数】5页(P48-52)
【作者】张文清;李龙雨;李芬兰;欧海燕
【作者单位】汕头大学工学院电子系,广东汕头515063;汕头大学工学院电子系,广东汕头515063;汕头大学工学院电子系,广东汕头515063;汕头大学工学院电子系,广东汕头515063
【正文语种】中文
【中图分类】TP391.4
【相关文献】
1.基于ROMP算法的相干信号DOA估计 [J], 任肖丽;王骥
2.基于ROMP算法的压缩感知飞行数据重构技术 [J], 耿宏;张双;刘家学
3.基于SiT-ROMP算法的视频封装帧压缩重构研究 [J], 郭青青;李雷
4.基于MS-ROMP信号重构算法的欠定盲分离 [J], 季策; 张晓梦
5.基于Viterbi算法和ROMP的多弹道目标分离与特征提取 [J], 陈帅; 冯存前; 许旭光
因版权原因,仅展示原文概要,查看原文内容请购买。
第17卷第30期2017年10月科学技术与工程Vol.17 N o.30 O ct. 2017 1671 —1815(2017)030-0069-05 Science Technology an d E ngineering©2017 Sci.Tech.E ngrg.自动化技术、计算机技术基于正交匹配追踪算法的急性运动超分辨率图像重构方法郭瑞芳(鄂尔多斯应用技术学院,鄂尔多斯017000)摘要采用当前急性运动中超分辨率图像重构方法得到的重构图像存在全局误差,导致重构图像质量低下,重构效果不 佳。
为此,提出一种新的急性运动中超分辨率图像重构方法,设计急性运动中超分辨率图像重构模型,将小波稀疏字典作为 急性运动中超分辨率图像重构的理论依据。
将低分辨率急性运动图像分割成低分辨率图像块,对无噪高分辨率急性运动图 像块相应的无噪低分辨率图像块进行分析。
通过OMP方法对稀疏系数求解,依据得到的稀疏系数估计出高分辨率急性运动 图像块的高频小波系数,将高分辨率小波系数急性运动图像块返回高分辨率小波系数急性运动图像,通过逆小波变换得到最 终的高分辨率图像,对全局误差进行修正。
实验结果表明,采用所提方法得到的重构图像质量高,重构效果好。
关键词急性运动 超分辨率图像 重构中图法分类号TP391.41; 文献标志码A超分辨率图像重构就是通过一幅或一系列低分 辨率图像形成相应的高分辨率图像的过程,在超分 辨率图像重构的同时还可以滤除噪声[1—3]。
超分辨 率技术被广泛应用于军事与民用的视觉领域中,急 性运动分辨率通常较低,为了获取高分辨率的急性 运动图像,图像需对其进行重构[4—6]。
文献[7]提出一种基于马尔科夫方法的急性运 动中超分辨率图像重构方法,该方法利用马尔科夫 网络对大量超分辨率图像和相应的低分辨率图像的 映射关系进行学习,将最近邻高分辨率图像块作为 超分辨的输出,该方法实现过程简单,但需要大量的 样本图像;文献[8]提出一种基于X近邻的邻域嵌 人法对急性运动中超分辨率图像进行重构,该方法 依据超分辨率图像块之间的相似流形,通过X个近 邻系数结合图像块线性组合成超分辨图像,该方法 效率较高,但对于解的最优化,固定X值有欠拟合 或过拟合的弊端;文献[9]提出一种基于小波算法 的急性运动超分辨率图像重构方法,该方法直接从 输人图像中重构出超分辨率图像,易于实现,但由于 小波基自身具有冗余性,大大限制了对不同模糊退2016年9月27日收到作者简介:郭瑞芳(1974—),女,内蒙古呼和浩特人,副教授。
2021年第40卷第4期传感器与微系统(Transducer and Microsystem Technologies)131DOI : 10.13873/J. 1000-9787(2021)04-0131-04面向ECG 的二分法稀疏度自适应匹配追踪重构算法**收稿日期:2019-09-29*基金项目:中央高校基本科研业务费专项资金资助项目(JUSRP51510);江苏省研究生科研与实践创新计划项目(SJCX18-0647);江苏省物 联网应用技术重点建设实验室资助项目王 涛▽,田青】,虞致国孙益洲-顾晓峰|(1.物联网技术应用教育部工程研究中心江南大学电子工程系,江苏无锡214122;2.无锡太湖学院,江苏无锡214064)摘要:为了减少无线传感器网络(WSNs)心电信号的压缩感知重构时间,提出一种面向心电(ECG)信号的二分法稀疏度自适应匹配追踪重构算法。
基于二分法快速接近真实稀疏度的值,并通过相邻迭代之间残差范数值差的绝对值确定下一轮迭代计算区间。
实验结果表明:与传统稀疏自适应匹配追踪重构算法相比较,改进算法可显著降低重构时间并接近子空间追踪算法和正交匹配追踪算法;与子空间追踪算法和正交匹配追踪算法相比,峰值信噪比平均提升了 6.29%和5.43 %。
关键词:压缩感知;心电(ECG);重构;自适应匹配追踪中图分类号:TP391; TP212文献标识码:A 文章编号:1000-9787(2021)04-0131-04Dichotomy sparsity adaptive matching pursuit in compressedsensing reconstruction algorithm for ECG *WANG Tao 1'2, TIAN Qing 1, YU Zhiguo 1, SUN Yizhou 1, GU Xiaofeng 1(1・ Engineering Research Center of Internet of Things Technology Applications , Ministry of Education ,Department of Electronic Engineering , Jiangnan University , Wuxi 214122, China ;2. Taihu University of Wuxi,Wuxi 214064,China)Abstract : To reduce the time consumption in the reconstruction of electrocardiograph ( ECG ) signals for thewireless sensor networks ( WSNs ) , a dichotomy spars 让y adaptive matching pursuit ( DSAMP ) algorithm forcompressed sensing without knowing sparsity is proposed ・ The algorithm calculates the stage value for approachingthe real sparsity based on dichotomy , and determines the direction of stage switching by the absolute value of thedifference in residual norm between two adjacent iterations. Results show that the runtime of DSAMP can be reduced compared with that of sparsity adaptive matching pursuit and is similar to those of subspace pursuit andorthogonal matching pursuit. The peak signal to noise ratio of the DSAMP is improved 6. 29 % and 5. 43 % , compared with the that of orthogonal matching pursuit and subspace pursuit on average , respectively.Keywords : compressed sensing ; electrocardiograph (ECG ) ; reconstruction ; adaptive matching pursuit0引言随着人工智能和无线传感器技术的飞速发展,现代医 学已经进入了智能医疗和远程医疗的时代⑴。
基于 OMP 算法的极化敏感阵列多参数估计谢菊兰;许欣怡;李会勇【摘要】基于压缩感知的 DOA 估计方法在小快拍数下性能优越,并且具有天然的解相干能力,但在极化敏感阵列中运用很少。
基于极化敏感阵列研究一种改进的OMP 算法,能够成功估计出空域和极化域参数。
该算法首先将极化敏感阵列信号接收矩阵重新建模,随后采用所提的改进 OMP 算法得到空域到达角估计结果。
然后将求解出来的空域到达角代入到根据模值约束条件构造出来的代价函数中,通过闭合式解得到极化参数估计,从而实现了自动配对的空域和极化域的参数估计。
仿真结果表明,该方法无论信号相干与否都能够得到良好的估计结果,并且在非相干情况下,估计性能总体优于极化 ESPRIT 算法及模值约束 MUSIC 算法。
%The DOA estimation algorithm based on compressive sensing has superior performance in small snapshot and the natural ability of decorrelation,but it is rarely used in the polarization sensitive array. In this paper,an improved OMP algorithm based on polarization sensitive array is studied to estimate the pa-rameters of the air domain and the polarization domain.First,this algorithm remodels the signal receiving matrix of the polarization sensitive array,followed by using the proposed improved OMP algorithm to obtain the estimation results of spatial arrival angle.Then,the polarization parameters are estimated via the closed solution to a cost function of the mold constructor constraint,in which the estimated spatial arrival angle is substituted.Simulation results show that the proposed method can obtain good results in both coherent and incoherent signals and the estimation performance in the case of incoherent signals isgenerally better than the polarization ESPRIT algorithm and the modulus constraint MUSIC algorithm.【期刊名称】《雷达科学与技术》【年(卷),期】2016(014)005【总页数】7页(P453-458,465)【关键词】极化敏感阵列;压缩感知;OMP 算法;模值约束【作者】谢菊兰;许欣怡;李会勇【作者单位】电子科技大学电子工程学院,四川成都 611731;电子科技大学电子工程学院,四川成都 611731;电子科技大学电子工程学院,四川成都 611731【正文语种】中文【中图分类】TN911.70 引言压缩感知(Compressive Sensing, CS)[1]是近几年提出的一种稀疏信号重构技术,它突破了奈奎斯特采样定理对采样频率的制约,可以以低频率进行欠采样,然后以高概率、高精度重构原始信号,降低数据采样、存储和处理的成本。
基于压缩感知的图像处理基于压缩感知的图像处理一、压缩感知在过去的几十年里,人们获取数据的能力不断提高,需要处理的数据量也越来越大,因此信号的带宽也越来越大,所以对信号处理的速度和采样速率的要求也随之提高。
众所周知,奈奎斯特采样定理要求采样率不得低于信号带宽的两倍,这对目前的信号处理能力提出了巨大的挑战。
所以人们试图找到一种新的信号处理技术。
近年来提出了一种新的信号处理理论——压缩感知理论。
压缩感知理论表明:如果信号是稀疏的或者是可压缩的,就可以通过一个测量矩阵将其投影到一个低维的空间上,得到的低维信号成为测量信号,然后将这个测量信号进行传输,在接收端通过接收到的信号和已知的测量矩阵来重构出原始的信号。
理论上指出任何信号经过一定处理后都可以转化为稀疏信号,这也为压缩感知理论在各个领域的广泛使用提供了保障。
1、压缩感知理论传统的信号处理过程包括信号的采样、压缩、传输和重构四个部分,根据奈奎斯特采样定理,信号的采样速率不能低于信号最大带宽的两倍,只有以满足这一要求的采样速率进行采样,才能保证信息不丢失,但是在很多情况下,奈奎斯特采样速率显得很高,实现起来比较困难。
压缩感知是一种新的信号获取的方法,它突破了奈奎斯特采样定理的瓶颈,它将对信号的压缩和采样合并进行,使得测量数据量远远小于传统的采样方法所得的数据量。
压缩感知主要包括三个方面的内容:信号的稀疏表示、信号的压缩采样和信号的重构。
2、信号的稀疏表示前面提到,压缩感知理论只能直接应用于稀疏信号。
如果需要处理的信号是稀疏的,那就不需要稀疏表示这一部分,直接进行压缩采样就行了,但是就目前来看,我们所要处理的大多数信号都不是稀疏信号,这就需要将其转换为稀疏信号。
假设ψ=[ψ1, ψ2, ψ3, , ψN ]为R 空间上的一组基,Ψi (i=1,2,3…N)是N一个N*1的列向量,考虑x =[x 1, x 2, x 3, , x N ]T ,它是一个实值有限长的ψ线性表示:N x ∈R 一维离散信号,。
稀疏编码的鲁棒性分析与异常数据处理在现代数据处理的领域中,稀疏编码是一种重要的技术,被广泛应用于信号处理、图像处理、机器学习等领域。
稀疏编码的主要目标是通过对信号进行压缩表示,提取出信号中的主要信息,同时抑制噪声和异常数据的影响。
本文将对稀疏编码的鲁棒性进行分析,并探讨如何处理异常数据。
首先,我们来了解一下稀疏编码的基本原理。
稀疏编码是一种通过线性组合来表示信号的方法,其核心思想是将信号表示为一组基向量的线性组合,其中只有少数几个基向量的系数非零。
这种表示方式可以有效地压缩信号,并提取出信号的重要特征。
在稀疏编码中,通常使用L1范数作为稀疏性的度量,通过最小化L1范数可以得到稀疏表示。
然而,在实际应用中,信号往往面临着各种噪声和异常数据的干扰。
这些噪声和异常数据可能会对稀疏编码的结果产生较大的影响,导致信号的表示不准确。
因此,如何提高稀疏编码的鲁棒性成为一个重要的问题。
一种常用的方法是引入稀疏编码的鲁棒模型,通过优化鲁棒目标函数来提高稀疏编码的鲁棒性。
鲁棒模型考虑了信号中的噪声和异常数据,通过最小化噪声和异常数据对稀疏表示的影响,得到更准确的稀疏表示。
常见的鲁棒模型包括基于L1范数和L2范数的鲁棒稀疏编码模型。
这些模型通过引入正则化项来平衡稀疏性和鲁棒性,从而提高稀疏编码的鲁棒性。
另一种方法是结合稀疏编码和异常数据处理的方法,通过对异常数据进行检测和修复,提高稀疏编码的准确性。
异常数据处理可以通过一些统计方法或者机器学习方法来实现。
例如,可以使用离群点检测算法来检测异常数据,并使用插值或者替换的方法来修复异常数据。
这种方法可以有效地提高稀疏编码的鲁棒性,减少异常数据对稀疏表示的影响。
除了上述方法,还可以通过优化稀疏编码的求解算法来提高鲁棒性。
传统的稀疏编码算法通常使用迭代方法求解,如迭代收缩阈值算法(ISTA)和正交匹配追踪算法(OMP)。
这些算法在处理正常数据时表现良好,但对于异常数据的处理效果较差。
L0正则化增量正交投影非负矩阵分解的目标跟踪算法王海军;葛红娟【摘要】针对传统跟踪算法不能在复杂场景下进行有效跟踪的问题,提出一种基于L0正则化增量正交投影非负矩阵分解(incremental orthogonal projective non-negative matrix factorization,IOPNMF)的目标跟踪算法.在粒子滤波框架下采用IOPNMF算法在线获得跟踪目标基于部分的表示以构建模板矩阵,然后将每帧中的候选样本建立基于模板矩阵的线性表示,对表示系数进行L0正则化约束,并提出快速数值解法,同时引入粒子筛选机制,加快跟踪速度.实验结果表明,新算法能够解决跟踪过程中出现的遮挡、光照变化、运动模糊等影响跟踪性能的因素,具有较高的平均覆盖率和较低的平均中心点误差.【期刊名称】《系统工程与电子技术》【年(卷),期】2016(038)010【总页数】7页(P2428-2434)【关键词】目标跟踪;L0正则化;粒子筛选【作者】王海军;葛红娟【作者单位】南京航空航天大学民航学院,江苏南京211106;滨州学院山东省高校航空信息技术重点实验室,山东滨州256603;南京航空航天大学民航学院,江苏南京211106【正文语种】中文【中图分类】TP391目标跟踪是计算机视觉领域一项重要的研究课题,在交通流量控制、人机接口、视频监控等领域得到了广泛的应用。
近年来,国内外学者对目标跟踪进行了大量的研究工作,大致可以分为两类:基于判别模型的目标跟踪[1-4]和基于生成模型的目标跟踪[5-7]。
基于判别模型的方法将目标跟踪看成是一个二分类问题,将被跟踪的目标物体从众多的背景中分离出来。
基于生成模型的方法把目标跟踪看成是从候选样本中寻找与目标模板中最相似的区域。
这类方法由于跟踪结果比较鲁棒,得到了国内外许多学者的关注。
例如,文献[8]提出增量视觉跟踪(incremental visual tracking,IVT)算法,该方法将每个候选样本用主成分分析(principal component analysis, PCA)基向量图像的线性组合来表示,并采用增量主成分分析方法对PCA 基向量进行更新以适应跟踪目标外观的变化,取得了不错的跟踪效果。
摘要近年来,带箱型约束的L2-L p(0<p<1)最小化问题在信号还原、变量选择等方面有着广泛的应用。
然而,这是一类非凸非光滑非Lipschitz连续的约束优化问题,求解非常困难。
一般而言,这类问题都是NP难的。
本论文致力于研究该类问题的数值算法,主要工作如下:第一个方面,我们通过变量替换,将原问题转化为目标函数在约束域上连续可微且其梯度函数是Lipschitz连续的箱型约束最小化问题。
我们证明了原问题和转化问题是等价的,且给出了等价问题的KKT条件。
此外,我们还利用投影算子给出了可行解是KKT点的充要条件。
第二个方面,基于等价问题,我们设计了一阶内点法、积极集法和梯度投影法来求解该带箱型约束的L2-L p最小化问题。
对于一阶内点法,我们首先给出了ε−KKT点的定义,并证明了算法在O(ε−2)次迭代后可以得到等价问题的一个ε−KKT点。
对于积极集法,我们给出了工作集的划分法则,用共轭梯度法求解迭代子问题来得到搜索方向,我们还证明了该算法产生的迭代点序列收敛到等价问题的一个KKT点。
对于梯度投影法,我们证明了迭代点序列也能收敛到等价问题的一个KKT点。
最后我们通过将这三类算法用于求解压缩传感问题,来验证这些算法的有效性,数值结果表明梯度投影算法较优。
关键词:L2-L p最小化问题;内点算法;积极集算法;梯度投影算法AbstractIn recent years,the L2-L p(0<p<1)box-constrained minimization problem has been widely applied in signal reconstruction and variable selection.However,it is a class of nonsmooth,nonconvex and non-Lipschitz continuous constrained optimiza-tion problem,which is very difficult to solve.In general,this type of problem is NP hard.This thesis is devoted to the research of numerical algorithms for solving such problems.The main tasks of this paper are as follows:First of all,we transform the original problem to a box-constrained minimization problem whose objective function is continuously differentiable on the constraint do-main and its gradient function is Lipschitz continuous by variable substitution.We prove that the original problem is equivalent to the transformation problem and show the KKT condition for the equivalent problem.In addition,we also use the projection operator to obtain the necessary and sufficient conditions that the feasible solution is a KKT point.Secondly,based on the equivalent problem,we have designed thefirst-order in-terior point method,active set method and gradient projection method to solve the problem of L2-L p box-constrained minimization problem.Forfirst-order interior point method,wefirst give the definition ofε−KKT point and prove that after iterating O(ε−2)times,we can get aε−KKT point by the algorithm.For active set method,we present the classification rules of the working set and we solve iterative subproblems for obtaining the search direction by the conjugate gradient method.we also show that the iteration point sequence generated by the active set algorithm converges to a KKT point of the equivalent problem.For the gradient projection method,we prove that the iteration point sequence generated by the gradient projection algorithm converges to a KKT point of the equivalent problem.Last but not least,By using these three algorithms to solve the compression sens-ing problem,we verify the validity of these algorithms and the numerical results showthat the gradient projection algorithm is superior.Key words:L2-L p minimization problem;Interior point algorithm;Active set algo-rithm;Gradient projection algorithm目录第1章引言 (1)1.1问题背景 (1)1.2已有研究 (3)1.3论文结构 (5)第2章带约束L2-L p优化问题的等价问题 (6)2.1变量替换 (6)2.2KKT条件 (10)2.3投影算子 (10)第3章求解带约束L2-L p优化问题的内点算法 (12)3.1内点算法 (12)3.2收敛性分析 (14)第4章求解带约束L2-L p优化问题的积极集算法 (17)4.1积极集算法 (17)4.2收敛性分析 (21)第5章求解带约束L2-L p优化问题的梯度投影算法 (23)5.1梯度投影算法 (23)5.2收敛性分析 (24)第6章L2-L p优化问题的数值算例 (27)第7章总结 (31)参考文献 (32)致谢 (34)声明 (35)个人简历、在学期间发表的学术论文与研究成果 (36)主要符号对照表主要符号对照表R n n维列向量空间.N自然数集.‖·‖1L1范数.‖·‖L2范数.‖·‖∞无穷范数.‖·‖0L0范数,表示向量中非零分量的个数.‖·‖p L p范数,其中0<p<1.e i第i个分量为1,其余的分量为0的n维列向量. Diag(x)对角线元素是向量x的分量的对角阵.x T y向量x与y的内积.|x|p列向量(|x1|p,···,|x n|p)T.x∘y列向量(x1y1,···,x n y n)T.X⪰0矩阵X是一个半正定阵.N(0,1)均值为0,标准差为1的正态分布.第1章引言1.1问题背景支持向量机、压缩传感、变量选择、资产组合等模型[1–4]的运用需要求得线性系统中的稀疏解,比如一个常见的压缩感知问题就是:已知n维向量x在m (m≪n)维空间上的投影b,或者给定了m维向量b,以及m×n维矩阵A,根据b=Ax来恢复n维向量x,即需要找到满足Ax=b的尽可能的稀疏解。
压缩感知重构匹配类算法分析摘要:压缩感知理论是一种利用信号的稀疏性或可压缩性而把采样与压缩融为一体的新理论体系,它成功地克服了传统理论中采样数据量大、资源浪费严重等问题。
该理论的研究方向主要包括信号的稀疏表示、测量矩阵的设计和信号的重构算法。
其中信号的重构算法是该理论中的关键部分,也是近年来研究的热点。
本文主要对匹配追踪类重构算法作了详细介绍,并通过仿真实验结果对这些算法进行了对比和分析。
关键词:压缩感知;稀疏信号;重构算法;匹配追踪类压缩感知算法abstract:the compressive sensing theory is a recent proposed theory, which can utilize the sparse and compressive characteristics of signals to combine the sampling and compression processes into only one procedure. it overcomes the shortcomings of large sampling data and significant waste of resource in traditional theories. the research areas in compressive sensing mainly include the sparse representation of signals, the design of measurement matrix, and signal reconstruction algorithms. the reconstruction algorithm is the key component of this new theory and is the focus of recent research. in this paper, the reconstruction algorithms, whichuse matching and tracking techniques, are described in details. simulations of these algorithm are also conducted to compare and analyze these algorithms.key words: compressive sensing, sparse signal, reconstruction algorithm, compress sensing algorithms based on matching1 cs(压缩感知)背景知识压缩感知理论[1-4]是一种能够在采样的同时实现压缩目的的新理论,其基本思想是:只要信号本身或者信号在某个变换域上是稀疏的或可压缩的,那么就可以用一个与变换域不相关的测量矩阵将变换域的高维信号投影到一个低维空间上,然后通过求解一个优化问题就能够从少量的投影系数中以较高的概率成功或近似地重构出原信号。
用于CS的广义稀疏度自适应匹配追踪算法MA Yushuang;LIU Cuixiang;GUO Zhitao;WANG Baozhu【摘要】The basic idea of compressed sensing theory is that the original signal is sparse in a transform domain or compressible, and the sampling process and the compression process in the Nyquist sampling theorem are combined into one. Sparse Adaptive Matching Pursuit(SAMP)algorithm can realize the reconstruction under unknown sparsity, and the generalized orthogonal matching pursuit algorithm selects multiple atoms at each iteration, which improves the conver-gence speed of the algorithm. This paper proposes a Generalized Sparse Adaptive MatchingPursuit(gSAMP)algorithm based on the advantages of the above two reconstruction algorithms, and then the peak signal to noise ratio, reconstruction time, relative error, etc. of the reconstructed image are proposed. Objective evaluation indicators and subjective visual comparisons of the proposed algorithm and the traditional greedy algorithm. When the compression ratio is fixed at 0.5, the reconstruction effect of the gSAMP algorithm is better than that of the traditional greedy reconstruction algorithms such as MP, OMP, ROMP, SAMP and gOMP.%压缩感知理论的基本思想是原始信号在某一变换域是稀疏的或者是可压缩的,并将奈奎斯特采样定理中的采样过程和压缩过程合二为一.稀疏度自适应匹配追踪(SAMP)算法能够实现稀疏度未知情况下的重构,而广义正交匹配追踪算法每次迭代时选择多个原子,提高了算法的收敛速度.基于上述两种重构算法的优势,提出了广义稀疏度自适应匹配追踪(Generalized Sparse Adaptive Matching Pursuit,gSAMP)算法.针对重构图像的峰值信噪比、重构时间、相对误差等客观评价指标,以及主观视觉上对所提算法与传统的贪婪算法进行对比.在压缩比固定为0.5时,gSAMP算法的重构效果优于传统的MP、OMP、ROMP、SAMP以及gOMP贪婪类重构算法的效果.【期刊名称】《计算机工程与应用》【年(卷),期】2019(055)013【总页数】6页(P207-211,245)【关键词】压缩感知;稀疏度自适应匹配追踪;稀疏度;广义正交匹配追踪;贪婪类重构算法【作者】MA Yushuang;LIU Cuixiang;GUO Zhitao;WANG Baozhu【作者单位】School of Electronic and Information Engineering, Heibei University of Technology, Tianjin 300401, China;School of Electronic and Information Engineering, Heibei University of Technology, Tianjin 300401, China;School of Electronic and Information Engineering, Heibei University of Technology, Tianjin 300401, China;School of Electronic and Information Engineering, Heibei University of Technology, Tianjin 300401, China【正文语种】中文【中图分类】TN911.71 引言近年来,压缩感知[1](Compressed Sensing,CS)理论受到图像处理领域和信号处理领域的广泛关注。
第22卷第5期2014年5月光
Opticsand学精密工程
PrecisionEngineering
V01.22NO.5
Mav.2014
文章编号1004—924X(2014)05—1395—08分段正则化正交匹配追踪算法
吴迪H,王奎民2,赵玉新1,王巍3,陈立娟1(1.哈尔滨工程大学自动化学院,黑龙江哈尔滨150001;2.中国人民解放军海军驻锦州地区军事代表室,辽宁锦州121000;3.中国船舶重工集团公司第七O三研究所,黑龙江哈尔滨150078)
摘要:为了使压缩感知重构算法在实际重构信号时不需要稀疏度先验信息,本文提出了分段正则化正交匹配追踪算法。该算法根据信号重构残差量设计阈值,构建候选集。通过正则化候选集提取出用于表示信号的原子,并将其存入支撑集;当候选集为空集时,选择相关系数最大的原子加人支撑集。最后,针对支撑集中的原子求解最小二乘问题实现信号的逼近和残差量的更薪。实验结果表明:针对长度为256的高斯信号和二值信号,提出的算法在稀疏度分别达到50和40时,精确重构率可达90%以上;在信号稀疏度相同的条件下,重构效果和速度整体优于现有的同类算法,具有速度快、稳定性好的特点。关键词:压缩感知;重构算法;分段正则化;匹配追踪中图分类号:TP391.4;TN911.7文献标识码:Adoi:10.3788/OPE.20142205.1395
一一一一一一一
Stagewiseregularizedorthogonalmatching
pursuitalgorithm
WUDiH,WANGKui—min2,ZHAOYu—xinl,WANGWei3,CHENLi—juan
(1.CollegeofAutomation,HarbinEngineeringUniversity,Harbin150001,China;2.MilitaryDelegateSectionofChinaPeople'sLiberationArmyNavyStationedin
Jinzhou,
Jinzhou121000,China;
3.No.703ResearchInstitute,ChinaShipbuildingIndustryCorporation,Harbin150078,China;
女Co门叩spo九di行gauthor,E-mail:375342788@qq.com)
Abstract:Anovelreconstruction
algorithm(stagewiseregularizedorthogonalmatchingpursuit)was
proposedtoreconstructsignalswithoutpriorsparsityinformation.Themethodconstructedthecandi—datesetbydesigningthresholdbasedontheresidualfromsignalreconstruction.Theextractedsignal
atomsfromthecandidatesetweremergedwiththeprevioussupportset.Whenthecandidatesetwas
anullset,theatomwiththegreatestcorrelationwasdirectlyaddedtothesupportset,Finally,the
refinementofsignalapproximationandresidualupdatingwereachievedbysolvingaleast‘‘squarealgo——
rithmonthesupportset.TheexperimentalresultsforGaussiansignalandbinarysignalwithalength
of256showthattheprobabilityofexactreconstructioncanbereachedabove90%ontheconditionsof
signalsparsityof50and40,andthereconstructingeffectsandreconstructingspeedsare
betterthan
收稿日期:2013-07—23;修订日期:2013-09—10.基金项目:国家自然科学基金资助项目(No.51109045);中央高校基本科研业务费专项资金资助项目(No。HEUCFX41302)
万方数据光学精密工程第22卷
thoseofsimilaralgorithmsunderthesameconditionofsignalsparsity.ThisalgorithmisprovedtObehigherprocessingspeedsandmorestabile.
Keywords:compressedsensing;reconstructionalgorithm;stagewiseregularization;matchingpursui—ting
1引言压缩感知(CompressedSensing,CS)[1。2
o理论具有全新的信号获取和处理方式,该理论解决了传统的Nyquist方法采样频率较高的问题,大大降低了稀疏信号精确重构所需的采样频率。另外,CS理论在数据采集的同时完成数据压缩,从而节约了软、硬件资源及处理时间。这些突出优点使其在信号处理领域有着广阔的应用前景≯“。重构算法是该理论的重要部分,其目的在于由观测得到的低维数据尽可能精确地重构出真实的高维数据。目前的重构算法主要有3类:组合优化类重构算法、凸优化类算法和贪婪迭代类算法口],其中:组合优化类算法重构效果较好,但因其对采样结构要求严格,实际应用时受硬件条件约束较大;凸优化类算法,如基追踪(BasisPursuit,BP)[8等算法,需要的采样值少,计算精度高,但其计算复杂度过大,计算时间过长,难以满足实际应用;贪婪迭代类算法因其结构简单、运算量小.兼顾了运行效率和采样效率而受到广泛的推崇。现有的贪婪迭代算法有匹配追踪(MatchingPursuit,MP)’9、正交匹配追踪(0r—thogonalMatchingPursuit,OMP)lzo]、分段正交匹配追踪(StagewiseOrthogonalMatchingPur—suit,STOMP)I11]、正则化正交匹配追踪(Regu—larizedOrthogonalMatchingPursuit,ROMP)[12。、压缩采样匹配追踪(CompressiveSamplingMP,CoSaMP)L1刊和子空间追踪(Sub—spacePursuit,SP)[1“。这些方法的共同点是重构时均需要已知稀疏度,而实际应用中稀疏度通常是未知的。文献[15]中提出的SAMP算法对稀疏度未知的信号能够精确重构,然而SAMP的重构速度比其他贪婪迭代类算法慢。针对以上问题,本文提出了分段正则化正交匹配追踪算法。该算法主要用于解决以下问题:(1)稀疏度未知的情况下,对稀疏度的欠估计和过估计;(2)观测量固定且稀疏度K值较大情况下信号精确重构率低;(3)精确重构信号时速度仍然较低。本文剩余部分结构安排如下:第二节介绍了
压缩感知理论模型及重构算法;第三节为分段正则化正交匹配追踪算法的详细内容;第四节利用所提算法对稀疏信号进行实验和分析;最后得出结论。
2压缩感知与重构算法2.1压缩感知理论模型假设工为长度为N的K稀疏(或可压缩)的原始信号,这代表X可以由基于某线性方程的K《N个系数来表示。根据压缩感知理论,信
号X可以从以下线性随机投影得到:Y=m,(1)
其中:Y表示长度为M的采样向量,①为M×N维的观测矩阵。求解过程可以转化为以下最小f。范数问题:minJ|x||oS.t.Y一啦.(2)若M《N,则方程的解有无限多个,求解式
(2)的计算极不稳定,且是NP—hard问题m]。而当x足够稀疏时,m满足约束等距条件(Re—strictedIsometryProperty,RIP)[31
(1一&“)Iz鹏≤ll血忙≤(1+&。)llX忪,
(3)其中:JJ・JJ:表示向量的z。范数。晚。∈(0,1)表示2K稀疏度下的约束等距常数,此时根据某些非线性算法,只需数量为M—O(KlogN)采样值即可稀疏重建出x[2],求解问题则转化为更简单的最小Z。范数优化问题¨“:minII
X||lS.t.Y=呶.
(4)
2.2重构算法
传统的贪婪迭代类算法是基于式(4)求解原信号的最优逼近。根据各种贪婪迭代算法的特性,本文深人研究了具有高重构精度的ROMP算法和可以自适应选择原子的STOMP算法。
万方数据第5期吴迪,等:分段正则化正交匹配追踪算法R()MP算法的步骤如下:(1)计算相关系数{“,I/,/;一<r,①,>},选出K个最大相关系数对应的原子,将这些原子的角标构成的集合记为候选集.,;(2)正则化角标为候选集,中元素原子的相关系数,即I/,/,f<2I“,l(i,J∈J),选出能量最大的一组用于重构原信号,角标值存入J。;(3)更新原子角标集以,A一以UJ。;(4)以所有支撑集A中元素为角标的原子逼近信号,并更新残差量。STOMP算法中原子选取规则为根据残差量r与观测矩阵毋中原子的相关系数的大小选取西中与,内积大于设定阈值rI}rll。/ ̄/M的一组原子。算法的具体过程如下:(1)计算残差量和观测矩阵各原子的相关系数{“,}“,一<r,西,>},并找出满足{ij“:1>rIf,0。/ ̄/M}式的观测矩阵①中的原子①,,以①,的角标记为集合J。;(2)更新支撑集蛾,其中:A—AUJ。;(3)判断是否达到初始设定的阶段数:若达到,停止迭代;若未达到,采用矩阵伪逆的方式求解系数并更新残差量。结合以上两种算法,本文提出分段正则化正交匹配追踪算法,以保证贪婪迭代类算法在信号稀疏度未知的情况下重构信号的可靠性和有效性。3分段正则化正交匹配追踪算法本文提出的分段正则化正交匹配追踪算法主要包含4个阶段:原子初选、阈值的可靠性验证、候选集正则化和信号重构。下面对本文提出的算法的主要部分进行详细分析。3.1原子初选U一西1Y呈高斯分布。特殊情况下,如果观测矩阵垂由通过一致球体采样的列构成,向量的项z—ll—X一垂1①x—X的标准差为盯≈||工||2/ ̄/M的高斯直方图。尤其当M,N较大时‘“],甜包含了“真正信号”。z-选择合适时,阈值参数n一{j:f“,}>研)极可能提取出目标信号中少数大的组成成分。注意到实际上X是未知的,因此很难直接计算出盯,但可以通过盯≈||YJ:/ ̄/M来逼近。由于垂近似保持了X与Y之间的Z。的距离。支撑集的所有大成分原子很难一次被提取出来。本算法采用类似STOMP的分段方法选取原子形成候选集,这种分段逼近的原子选取方式体现了算法对稀疏度的自适应性,且为后面生成支撑集提供了基础。经验表明通常r为2.5~3。3.2阈值的可靠性验证由信号代理U一①。Y呈高斯分布可知,以上所述的阈值设定方式更适合重构高斯信号,而在重构其他类信号时不能保证绝对的有效性和可靠性。在执行过程中,算法根据所设阈值可能无法选出满足条件的原子,这会导致在后面的循环中支撑集无法更新,算法进入死循环。为了保证信号重构能有效进行,本文在融合了ROMP和StOMP算法的基础上,加入了阈值的可靠性验证阶段。具体为:根据当前残差量设定阈值,选取相关系数大于阈值的原子,若满足条件的原子个数大于零,表明所设阈值合理,对选出的原子进行正则化;若依据以上条件无法选出原子,则表明阈值设定的不合理,此时自动将最大相关系数对应的原子选出,由于只有一个原子,所以无需正则化,直接将此原子加入支撑集。阈值的可靠性验证保证了支撑集持续更新,使算法能可靠、有效地完成信号重构。3.3候选集正则化算法在本阶段通过正则化识别候选集中能量最大部分原子,以提高支撑集的可靠性以及信号重建的精确性。为了使支撑集中原子个数更加接近稀疏度真实值,需要进行几次迭代,每次迭代后支撑集都要比上一阶段更准确,从而保证下一阶段中残差量减少。实际上,支撑集中原子个数在达到最后阶段之前始终小于真实稀疏度K。本方法遵循ROMP原则,选出满足条件的原子加入支撑集。下面给出算法的伪代码,如表l所示。由表1可见,与现存的其他贪婪迭代类算法相比,本文提出的算法的优点在于重构信号的过程中根据阈值信息选取原子,不用使用稀疏度信息;同时,由于算法中阈值参数r的值是根据经验值设定的,实际中无法保证阈值的绝对合理性,因此引入了阈值的可靠性验证;对候选集正则化降低了算法的复杂度,提高了计算速度。