当前位置:文档之家› 分段正则化正交匹配追踪算法

分段正则化正交匹配追踪算法

分段正则化正交匹配追踪算法
分段正则化正交匹配追踪算法

一种改进的用于稀疏表示的正交匹配追踪算法

第10卷 第5期 信 息 与 电 子 工 程 Vo1.10,No.5 2012年10月 INFORMATION AND ELECTRONIC ENGINEERING Oct.,2012 文章编号:1672-2892(2012)05-0579-05 一种改进的用于稀疏表示的正交匹配追踪算法 王燕霞,张 弓 (南京航空航天大学 电子信息工程学院,江苏 南京 210016) 摘 要:稀疏表示理论在军事目标识别、雷达目标参数估计等领域应用越来越广,而目标信号的稀疏表示通常不唯一,因此产生了大量的稀疏表示算法。本文基于现有稀疏表示算法的研究,提出一种改进的正交匹配追踪(OMP)算法。首先采用非线性下降的阈值更快速地选择原子,确定备选原子集,提高了算法速度;其次用正则化的二次筛选剔除备选原子集中能量较低的原子,保证了算法精确度;并设置迭代停止条件实现算法的稀疏度自适应。实验结果表明,本文算法可以实现稀疏表示求解精确度和速度上的平衡,求解速度比基追踪(BP)算法快,精确度比OMP 、正则化OMP(ROMP)、基于自适应OMP 回溯(BAOMP)算法高。 关键词:过完备字典;稀疏表示;正交匹配追踪;正则化 中图分类号:TN850.6;TP753 文献标识码:A An improved orthogonal matching pursuit algorithm for sparse representation WANG Yan -xia,ZHANG Gong (College of Electronics and Information Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing Jiangsu 210016,China) Abstract:Usually sparse representation of signal is not unique, which results in a large number of sparse representation algorithms. An improved Orthogonal Matching Pursuit(OMP) algorithm is proposed. The atoms are selected more quickly with nonlinear decline threshold and the set of alternative atoms is determined, which improves the algorithm speed. Regularized secondary screening can remove lower -energy atoms from the alternative atoms set to ensure the accuracy. A stop condition for iteration is preset to realize the adaptive sparsity of new algorithm. Simulation results show that, the improved algorithm can keep a balance between accuracy and speed for sparse solving with a faster speed than Basis Pursuit(BP) algorithm and a higher accuracy than OMP, Regularized OMP(ROMP) and Backtracking -based Adaptive OMP(BAOMP) algorithms. Key words:over -complete dictionary;sparse representation;orthogonal matching pursuit;regularized 稀疏表示理论在军事目标识别[1]、雷达目标参数估计[2]等领域的应用越来越广,2010年Vishal 和Nasser 等人基于科曼奇族前视红外数据库将稀疏表示用于军事目标的识别,稀疏求解的结果表明算法取得了较好的识别效果[1]。对于稀疏表示理论应用于各种目标信号处理来说,信号的表示应该能对自身不同性质,以及各性质间的差异提供明确信息,这就促进了信号在基于大量波形的过完备字典上的分解[1]。然而过完备库中的波形数远远超过信号的维数,因此它对给定信号的表示不是唯一的,由此产生了信号处理工作中大量的稀疏表示算法。 基于过完备字典的稀疏表示起源于20世纪90年代,Mallat 和Zhang 首次提出了匹配追踪(Matching Pursuit ,MP)算法来解决该稀疏分解问题[3?4],通常这些算法可以分为3类:基于p l 范数正则化的方法、迭代收缩算法和贪婪追踪算法。基于p l 范数正则化的方法通过求解在重构条件下系数的p l 范数最小化来寻找稀疏解,此类比较典型的算法有基追踪(BP)[5];迭代收缩算法首先要获得系数的初始集,然后迭代修正获得稀疏表示,早期的这类方法有噪声整形(Noise Shaping ,NS)[6]等;贪婪追踪算法力求从字典中选取与余量最匹配的原子作为信号的近似表示,并通过减去与该原子相关的分量来更新余量,此类算法研究的成果较多,典型的有MP [5],OMP [7],ROMP [8]及BAOMP [9]等。 收稿日期:2011-12-14;修回日期:2012-02-09

分段正交匹配追踪算法StOMP

压缩感知重构算法之分段正交匹配追踪(StOMP) 分段正交匹配追踪(StagewiseOMP)或者翻译为逐步正交匹配追踪,它是OMP另一种改进算法,每次迭代可以选择多个原子。此算法的输入参数中没有信号稀疏度K,因此相比于ROMP及CoSaMP有独到的优势。 0、符号说明如下: 压缩观测y=Φx,其中y为观测所得向量M×1,x为原信号N×1(M<

2、分段正交匹配追踪(StOMP)Matlab代码(CS_StOMP.m) 代码参考了文献[4]中的SolveStOMP.m,也可参考文献[5]中的StOMP.m。其实文献[4]是斯坦福的SparseLab 中的一个函数而已,链接为https://www.doczj.com/doc/ca7499263.html,/,最新版本为2.1,SolveStOMP.m在目录 SparseLab21-Core\SparseLab2.1-Core\Solvers里面。 1.function[theta]=CS_StOMP(y,A,S,ts) 2.%CS_StOMP Summary ofthisfunctiongoes here 3.%Version:1.0 writtenbyjbb0523@2015-04-29 4.%Detailedexplanationgoeshere 5.%y =Phi*x

贪婪算法中ROMP算法的原理介绍及MATLAB仿真

压缩感知重构算法之正则化正交匹配追踪(ROMP) 正交匹配追踪算法每次迭代均只选择与残差最相关的一列,自然人们会想:“每次迭代是否可以多选几列呢?”,正则化正交匹配追踪(RegularizedOMP)就是其中一种改进方法。本篇将在上一篇《压缩感知重构算法之正交匹配追踪(OMP)》的基础上给出正则化正交匹配追踪(ROMP)算法的MATLAB函数代码,并且给出单次测试例程代码、测量数M与重构成功概率关系曲线绘制例程代码。 0、符号说明如下: 压缩观测y=Φx,其中y为观测所得向量M×1,x为原信号N×1(M<

我将原子选择过程封装成了一个MATLAB函数,代码如下(Regularize.m):

1.function [val,pos] = Regularize(product,Kin) 2.%Regularize Summary of this function goes here 3.% Detailed explanation goes here 4.% product = A'*r_n;%传感矩阵A各列与残差的内积 5.% K为稀疏度 6.% pos为选出的各列序号 7.% val为选出的各列与残差的内积值 8.% Reference:Needell D,Vershynin R. Uniform uncertainty principle and 9.% signal recovery via regularized orthogonal matching pursuit. 10.% Foundations of Computational Mathematics, 2009,9(3): 317-334. 11. productabs = abs(product);%取绝对值 12. [productdes,indexproductdes] = sort(productabs,'descend');%降序排列 13. for ii = length(productdes):-1:1 14. if productdes(ii)>1e-6%判断productdes中非零值个数 15. break; 16. end 17. end 18. %Identify:Choose a set J of the K biggest coordinates 19. if ii>=Kin 20. J = indexproductdes(1:Kin);%集合J 21. Jval = productdes(1:Kin);%集合J对应的序列值 22. K = Kin; 23. else%or all of its nonzero coordinates,whichever is smaller 24. J = indexproductdes(1:ii);%集合J 25. Jval = productdes(1:ii);%集合J对应的序列值 26. K = ii; 27. end 28. %Regularize:Among all subsets J0∈J with comparable coordinates 29. MaxE = -1;%循环过程中存储最大能量值 30. for kk = 1:K 31. J0_tmp = zeros(1,K);iJ0 = 1; 32. J0_tmp(iJ0) = J(kk);%以J(kk)为本次寻找J0的基准(最大值) 33. Energy = Jval(kk)^2;%本次寻找J0的能量 34. for mm = kk+1:K 35. if Jval(kk)<2*Jval(mm)%找到符合|u(i)|<=2|u(j)|的 36. iJ0 = iJ0 + 1;%J0自变量增1 37. J0_tmp(iJ0) = J(mm);%更新J0 38. Energy = Energy + Jval(mm)^2;%更新能量 39. else%不符合|u(i)|<=2|u(j)|的 40. break;%跳出本轮寻找,因为后面更小的值也不会符合要求 41. end 42. end 43. if Energy>MaxE%本次所得J0的能量大于前一组 44. J0 = J0_tmp(1:iJ0);%更新J0 45. MaxE = Energy;%更新MaxE,为下次循环做准备 46. end 47. end 48. pos = J0; 49. val = productabs(J0);

贪婪算法中正交匹配追踪算法OMP的原理及仿真

压缩感知重构算法之正交匹配追踪(OMP) 前面经过几篇的基础铺垫,本篇给出正交匹配追踪(OMP)算法的MATLAB函数代码,并且给出单次测试例程代码、测量数M与重构成功概率关系曲线绘制例程代码、信号稀疏度K与重构成功概率关系曲线绘制例程代码。 0、符号说明如下: 压缩观测y=Φx,其中y为观测所得向量M×1,x为原信号N×1(M<

2、正交匹配追踪(OMP)MATLAB代码(CS_OMP.m) [plain]view plaincopy 1.function [ theta ] = CS_OMP( y,A,t ) 2.%CS_OMP Summary of this function goes here 3.%Version: 1.0 written by jbb0523 @2015-04-18 4.% Detailed explanation goes here 5.% y = Phi * x 6.% x = Psi * theta 7.% y = Phi*Psi * theta 8.% 令 A = Phi*Psi, 则y=A*theta 9.% 现在已知y和A,求theta 10. [y_rows,y_columns] = size(y); 11. if y_rows

mp&omp 匹配追踪 正交匹配追踪

1. 信号的稀疏表示(sparse representation of signals) 给定一个过完备字典矩阵,其中它的每列表示一种原型信号的原子。给定一个信号y,它可以被表示成这些原子的稀疏线性组合。信号y 可以被表达为y = Dx ,或者 。字典矩阵中所谓过完备性,指的是原子的个数远远大于信号y的长度(其长度很显然是n),即n<

相关主题
相关文档 最新文档