2023年7月29日发(作者：)

⽂献综述积累--ROMP算法ROMP算法⽂献阅读笔记     参考⽂献：Needell D，VershyninR．Signal recovery from incompleteand inaccurate measurements via regularizedorthogonal matching pursuit[J]. IEEEJournal on Selected Topics in Signal Processing, 2010, 4(2): 310—316.⽂中符号体系：     在⽂中摘要部分，给出了符号体系，原始信号为v，观测信号为x，观测矩阵是ϕ，观测矩阵是N⾏×d列，也就意味着原始信号v长是d，观测信号

x 长度是N，其中x=ϕv+e，e 在此处表⽰误差，语⾔表述就是观测信号等于观测矩阵乘原始信号再加上误差。正则化的个⼈理解     个⼈理解的正则化是⼀种限制条件，当我们想要拟合⼀条含噪曲线时，本来曲线本⾝阶数不⾼，但是由于噪声的原因，导致最终的拟合曲线将噪声也作为了拟合⽬标，从⽽出现了过拟合现象拟合了⼀条阶数很⾼的复杂曲线，这样降低了模型的适应度（不是所有信号都含有相同噪声），为了避免这种事情发⽣，我们引⼊⼀种限制条件，防⽌过拟合现象的发⽣，这种限制⽅法，称其为正则化。正⽂简述部分：主要问题与研究意义     ⽂章中作者提出了⼀种正则化正交匹配追踪（ROMP）算法，该算法将贪婪算法本⾝速度快的优越性和正则化条件限制的⾼准确性相结合，最终通过最⼩⼆乘迭代解决使⽤不完全、不准确观测信号恢复原始数据估计值的问题。该算法理论上是基于稀疏恢复问题是等效于凸优化问题的 （也就是统⼀不确定性原则，个⼈理解此处的UUP就是RIP准则），可以将⽋定性⽅程组的解问题转化为L1最⼩范数的问题。（就是在⽆穷多解中求解⼀个误差最⼩的解）研究⽬标     该⽂章针对的⽬标是含噪信号和扰动测量中信号的恢复，在含噪信号的恢复中⽂中提及ROMP的算法稳定度与凸优化的稳定度相同，⾼于OMP算法的稳定度。主要研究模型ROMP算法步骤     ROMP的意思是Regularized Orthogonal Matching Pursuit 正则化正交匹配追踪算法 该算法属于贪婪算法与凸优化的结合，在原本贪婪迭代的过程加⼊了正则化条件。以下算法步骤中对于部分符号参数有所调整，论⽂中的时间较为久远，对其中⼀些符号采⽤了当下流⾏的压缩感知符号体系做了修改。输⼊部分：观测信号的向量yM×1，公共稀疏度K，传感矩阵AM×N。输出部分：重构的估计稀疏向量

θ1×N ,残差值

rN×1。该算法步骤基本按照⽂章描述及相关博客总结，个⼈理解如下：此处参考了1、  初始化各参数，0次迭代残差r0初始化为输⼊变量

y，迭代计数变量t。                 （---------------------称该步骤为算法初始化过程---------------------）2、  计算优化问题

u1×N=∣∣rt−1,aj∣∣2，j∈N，即将残差与传感矩阵的各列分别做内积，在u中按降序排列，取前K个最⼤值，若u 中⾮0值不⾜K个，则选取全部的⾮0值，并存其序号于J中。3、  在

J中筛选符合正则化条件的⼦集J0，正则化标准意思是选择各列向量与残差内积绝对值的最⼤值不能⽐最⼩值⼤两倍以上(comparable coordinates)且能量最⼤的⼀组(with the maximal energy)。4、  存下

J0 的序号，并⼊索引集中，也存下传感矩阵中

J0 的索引列，也并⼊索引集中。（此处的J0仅能保证⼤于等于1，这个索引集的⼤⼩会影响最终最⼩⼆乘法输出的

θ 的个数，随着迭代次数的增加，这个索引集的⼤⼩会逐渐增⼤）5、  利⽤最⼩⼆乘法求解估计值

θ (本次迭代中产⽣了⼏个索引列，θ就⽐原来多了⼏列)6、  更新残差

rt=y−y=y−Aθ 。此处判断残差是否满⾜精度要求？迭代次数

t 是否⼤于

K ？迭代过程中产⽣的索引集个数是否⼤于2K？三个条件满⾜其⼀停⽌迭代，不满⾜回到第2步继续迭代。                 （---------------------称以上步骤为算法贪婪迭代过程过程---------------------）7、  最终获得了K个列数索引，⽽原

θ 是⼀个N长的向量，只不过是K稀疏的。所以我们按照这K个索引将最终所求得的

θk 排好顺序填进所有的⾮0点中作为最终重构的稀疏向量

θ输出。                 （---------------------称该步骤为算法输出最终结果---------------------）关于正则化步骤的详细解读    （---------此处参考了博主彬彬有礼_jbb0523的流程图，对相关步骤进⾏了⽂字说明补全---------）流程图原出处链接: .                   

     因为此处的正则化条件最开始本⼈阅读的时候有些问题也有点绕的云⾥雾⾥，故采⽤⼀个⼩例⼦将此处的步骤展开来看，帮助理解。现有⼀个要重构的⽬标信号K=5，初始化能量

Et=−1。经第⼀步计算内积，取得前7个⾮0值，分别是 27,26,16,15,11。J(k=1)=27,Et=272判断

2J(m=2)⩾J(k=1) 成⽴，更新能量Et=272+262。判断

2J(m=3)⩾J(k=1) 成⽴，更新能量Et=272+262+162。判断

2J(m=4)⩾J(k=1) 不成⽴，对⽐该组参数的能量是否⼤于现有能量值，显然⼤于-1，故更新能量值Etmax=272+262+162判断此时

k

J0=J（k：m），k=k+1继续迭代。J(k=2)=26,Et=262判断

2J(m=3)⩾J(k=2) 成⽴，更新能量Et=262+162。判断

2J(m=4)⩾J(k=2) 成⽴，更新能量Et=262+162+152。判断

2J(m=5)⩾J(k=2) 不成⽴，对⽐该组参数的能量是否⼤于现有能量值，不⼤于，故不更新能量值，本次迭代⽆⽤。J(k=3)=16,Et=162判断

2J(m=4)⩾J(k=3) 成⽴，更新能量Et=162+152。判断

2J(m=5)⩾J(k=3) 成⽴，更新能量Et=162+152+112。判断

2J(m=6)⩾J(k=3) 不成⽴，（J只有5个，J(6)=0）对⽐该组参数的能量是否⼤于现有能量值，不⼤于，故不更新能量值，本次迭代⽆⽤。………………直到J(k=5)=11,Et=112判断

2J(m=6)⩾J(k=5) 不成⽴，（J只有5个，J(6)=0）对⽐该组参数的能量是否⼤于现有能量值，不⼤于，故不更新能量值，本次迭代⽆⽤。该迭代过程直到最后仅输出了J0=27,26,16将该索引集加⼊计算最⼩⼆乘的A向量中，并将位置序号保存⾄索引集中。在进⾏整体最⼩⼆乘迭代，从⽽更新残差。实验设置     关于实验数据，在该⽂章的实验设置中，测试的是ROMP的算法稳定，分别模拟了信号本⾝受⼲扰的情况和观测过程受⼲扰的情况。每组分别进⾏了500次试验。1、  观测信号本⾝是采⽤了⽣成随机序列作为输⼊信号。2、  在模拟信号本⾝⼲扰的时候添加了d维的⾼斯随机误差信号⾄⽣成的原信号v中。3、  在模拟观测受⼲扰的情况时，添加N维误差向量⾄观测矩阵

ϕ 中。结论     当观测矩阵受扰动且原始信号稀疏度固定时，随观测数的增加，误差⽐在不断减⼩。     当观测矩阵受扰动且原始信号观测值固定时，随着原始信号稀疏度的增加，误差⽐在不断增⼤。     当观测信号受扰动且原始信号稀疏度固定时，随观测数的增加，误差⽐在不断减⼩。     当观测信号受扰动且原始信号观测值固定时，随着原始信号稀疏度的增加，误差⽐在不断增⼤。图截取⾃论⽂第四节后半部分，正⽂Page_12总结     ROMP算法的原始提出⽂献中研究⽬标是提⾼算法稳定度，这就与OMP中的以重构精度为⽬的有本质不同，之前光看 博主彬彬有礼_jbb0523 的博客始终有⼀个疑问就是为什么ROMP算法的重构效果不如OMP，甚⾄不太好，还成为了⼀个较为有代表性的算法。     将来在对压缩感知重构算法的研究上确实不能只针对于重构精确度、重构所需最⼩观测值、重构时间等常规参数，还要想到类似于特殊特征信号重构以及重构算法适应度、稳定度等问题。