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

压缩感知重构算法之正则化正交匹配追踪(ROMP)

“

正交匹配追踪算法每次迭代均只选择与残差最相关的一列，自然人们会想：每次迭代是否可以多选几列

”(RegularizedOMP)

呢，正则化正交匹配追踪就是其中一种改进方法。本篇将在上一篇《压缩感知重构算法之正交

匹配追踪(OMP)》的基础上给出正则化正交匹配追踪(ROMP)算法的MATLAB函数代码，并且给出单次测试例程

代码、测量数M与重构成功概率关系曲线绘制例程代码。

0、符号说明如下：

压缩观测y=Φx，其中y为观测所得向量M×1，x为原信号N×1（MN）。x一般不是稀疏的，但在某个变

换域Ψ是稀疏的，即x=Ψθ，其中θ为K稀疏的，即θ只有K个非零项。此时y=ΦΨθ，令A=ΦΨ，则y=Aθ。

(1)y为观测所得向量，大小为M×1

(2)x为原信号，大小为N×1

(3)θ为K稀疏的，是信号在x在某变换域的稀疏表示

(4)Φ称为观测矩阵、测量矩阵、测量基，大小为M×N

(5)Ψ称为变换矩阵、变换基、稀疏矩阵、稀疏基、正交基字典矩阵，大小为N×N

(6)A称为测度矩阵、传感矩阵、CS信息算子，大小为M×N

上式中，一般有KMN，后面三个矩阵各个文献的叫法不一，以后我将Φ称为测量矩阵、将Ψ称为稀疏矩

阵、将A称为传感矩阵。

1、ROMP重构算法流程：

正则化正交匹配追踪（ROMP）算法流程与OMP的最大不同之处：就在于从传感矩阵A中选

择列向量的标准，OMP每次只选择与残差内积绝对值最大的那一列，而ROMP则是先选出

内积绝对值最大的K列（若所有内积中不够K个非零值则将内积值非零的列全部选出），然后

再从这K列中按正则化标准再选择一遍，即为本次迭代选出的列向量（一般并非只有一

列）。

正则化标准：意思是选择各列向量与残差的内积的绝对值的最大值不能比最小值大两

倍以上(comparablecoordinates)且能量最大的一组(withthemaximalenergy)，因为满足条

件的子集并非只有一组。似乎用叙述语言描述不清楚，下面给出一种实现第(2)(3)步的算法流程图（此算法并

非本人原创，参考网络代码[2][3]，本人将代码中的思想进行整理，画出此流程图，方便初学者快速掌握学习

ROMP算法）：

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

1.function[val,pos]=Regularize(product,Kin)

2.%RegularizeSummaryofthisfunctiongoeshere

3.%Detailedexplanationgoeshere

4.%product=A*r_n;%传感矩阵A各列与残差的内积

5.%K为稀疏度

6.%pos为选出的各列序号

7.%val为选出的各列与残差的内积值

8.%Reference:NeedellD，VershyninR.Uniformuncertaintyprincipleand

9.%signalrecoveryviaregularizedorthogonalmatchingpursuit.

10.%FoundationsofComputationalMathematics,2009,9(3):317-334.

11.productabs=abs(product);%取绝对值

12.[productdes,indexproductdes]=sort(productabs,descend);%降序排列

13.forii=length(productdes):-1:1

14.ifproductdes(ii)1e-6%判断productdes中非零值个数

15.break