《贪婪算法中正交匹配追踪算法gOMP的原理及仿真》由会员分享，可在线阅读，更多相关《贪婪算法中正交匹配追踪算法gOMP的原理及仿真（10页珍藏版）》请在金锄头文库上搜索。
1、压缩感知重构算法之广义正交匹配追踪(gOMP)广义正交匹配追踪(Generalized OMP, gOMP)算法可以看作为OMP算法的一种推广，由文献1提出，第1作者本硕为哈工大毕业，发表此论文时在Korea University攻读博士学位。OMP每次只选择与残差相关最大的一个，而gOMP则是简单地选择最大的S个。之所以这里表述为“简单地选择”是相比于ROMP之类算法的，不进行任何其它处理，只是选择最大的S个而已。0、符号说明如下： 压缩观测y=x，其中y为观测所得向量M1，x为原信号N1（MN）。x一般不是稀疏的，但在某个变换域是稀疏的，即x=，其中为K稀疏的，即只有K个非零项。此时y=，
2、令A=，则y=A。 (1)y为观测所得向量，大小为M1 (2)x为原信号，大小为N1 (3)为K稀疏的，是信号在x在某变换域的稀疏表示 (4)称为观测矩阵、测量矩阵、测量基，大小为MN (5)称为变换矩阵、变换基、稀疏矩阵、稀疏基、正交基字典矩阵，大小为NN (6)A称为测度矩阵、传感矩阵、CS信息算子，大小为MN上式中，一般有KMN，后面三个矩阵各个文献的叫法不一，以后我将称为测量矩阵、将称为稀疏矩阵、将A称为传感矩阵。 注意：这里的稀疏表示模型为x=，所以传感矩阵A=；而有些文献中稀疏模型为=x，而一般为Hermite矩阵(实矩阵时称为正交矩阵)，所以-1=H(实矩阵时为-1=T)，即x=
3、H，所以传感矩阵A=H，例如沙威的OMP例程中就是如此。1、gOMP重构算法流程：2、广义正交匹配追踪(gOMP)MATLAB代码(CS_gOMP.m) 本代码完全是为了保证和前面的各算法代法格式一致，可以直接使用该实验室网站提供的代码2压缩包中的islsp_EstgOMP.m。plainview plaincopy1. functiontheta=CS_gOMP(y,A,K,S)2. %CS_gOMPSummaryofthisfunctiongoeshere3. %Version:1.0writtenbyjbb05232015-05-084. %Detailedexplanationgoes
4、here5. %y=Phi*x6. %x=Psi*theta7. %y=Phi*Psi*theta8. %令A=Phi*Psi,则y=A*theta9. %现在已知y和A，求theta10. %Reference:JianWang,SeokbeopKwon,ByonghyoShim.Generalized11. %orthogonalmatchingpursuit,IEEETransactionsonSignalProcessing,12. %vol.60,no.12,pp.6202-6216,Dec.2012.13. %Availableat:http:/islab.snu.ac.kr/pa
5、per/tsp_gOMP.pdf14. ifnargin415. S=round(max(K/4,1);16. end17. y_rows,y_columns=size(y);18. ify_rowsM36. ifii=137. theta_ls=0;38. end39. break;40. end41. At=A(:,Sk);%将A的这几列组成矩阵At42. %y=At*theta，以下求theta的最小二乘解(LeastSquare)43. theta_ls=(At*At)(-1)*At*y;%最小二乘解44. %At*theta_ls是y在At)列空间上的正交投影45. r_n=y-At
6、*theta_ls;%更新残差46. Pos_theta=Sk;47. ifnorm(r_n)1e-648. break;%quittheiteration49. end50. end51. theta(Pos_theta)=theta_ls;%恢复出的theta52. end3、gOMP单次重构测试代码(CS_Reconstuction_Test.m) 以下测试代码基本与OMP单次重构测试代码一样。也可参考该实验室网站提供的代码2压缩包中的Test_gOMP.m。plainview plaincopy1. %压缩感知重构算法测试2. clearall;closeall;clc;3. M=12
7、8;%观测值个数4. N=256;%信号x的长度5. K=30;%信号x的稀疏度6. Index_K=randperm(N);7. x=zeros(N,1);8. x(Index_K(1:K)=5*randn(K,1);%x为K稀疏的，且位置是随机的9. Psi=eye(N);%x本身是稀疏的，定义稀疏矩阵为单位阵x=Psi*theta10. Phi=randn(M,N)/sqrt(M);%测量矩阵为高斯矩阵11. A=Phi*Psi;%传感矩阵12. y=Phi*x;%得到观测向量y13. %恢复重构信号x14. tic15. theta=CS_gOMP(y,A,K);16. x_r=Psi
8、*theta;%x=Psi*theta17. toc18. %绘图19. figure;20. plot(x_r,k.-);%绘出x的恢复信号21. holdon;22. plot(x,r);%绘出原信号x23. holdoff;24. legend(Recovery,Original)25. fprintf(n恢复残差：);26. norm(x_r-x)%恢复残差 运行结果如下：（信号为随机生成，所以每次结果均不一样） 1）图： 2）Command windows Elapsedtime is 0.155937 seconds. 恢复残差： ans= 2.3426e-0144、信号稀疏度K与
9、重构成功概率关系曲线绘制例程代码 以下测试代码为了与文献1的Fig.1作比较。由于暂未研究学习LP算法，所以相比于文献1的Fig.1)缺少LP算法曲线，加入了SP算法。以下测试代码与SAMP相应的测试代码基本一致，可以合并在一起运行，只须在主循环内多加几种算法重构就行。plainview plaincopy1. %压缩感知重构算法测试CS_Reconstuction_KtoPercentagegOMP.m2. %绘制参考文献中的Fig.13. %Reference:JianWang,SeokbeopKwon,ByonghyoShim.Generalized4. %orthogonalmatch
10、ingpursuit,IEEETransactionsonSignalProcessing,5. %vol.60,no.12,pp.6202-6216,Dec.2012.6. %Availableat:http:/islab.snu.ac.kr/paper/tsp_gOMP.pdf7. %Elapsedtimeis798.718246seconds.(20150509pm)8. clearall;closeall;clc;9. %参数配置初始化10. CNT=1000;%对于每组(K,M,N)，重复迭代次数11. N=256;%信号x的长度12. Psi=eye(N);%x本身是稀疏的，定义稀疏矩阵为单位阵x=Psi*theta13. M_set=128;%测量值集合14. KIND=OMP;ROMP;StOMP;SP;CoSaMP;.15. gOMP(s=3);gOMP(s=6);gOMP(s=9);16. Percentage=zeros(N,length(M_set),size(KIND,1);%存储恢复成功概率17. %主循环，遍历每组(K,M,N)18. tic19. formm=1:length(M_set)20. M=M_set(mm);%本次测量值个数21. K_set=5:5:70;%信号x的稀疏度
