几种压缩感知算法.docx

1 压缩感知部分压缩感知算法重要可分为三类：贪婪迭代算法、凸凸优化（或最优化逼近措施）和基于贝叶斯框架提出的重构算法由于第三类措施注重信号的时间有关性，不适合图像解决问题，故目前的研究成果重要集中在前两类中目前已实现6中算法，分别为正交匹配追踪法（OMP）、迭代硬阈值法（IHT）、分段正交匹配追踪法（StOMP）、分段弱正交匹配追踪法（SwOMP）、广义正交匹配追踪（GOMP）、基追踪法（BP）1.1 正交匹配追踪法（OMP）在正交匹配追踪OMP中，残差是总与已经选择过的原子正交的这意味着一种原子不会被选择两次，成果会在有限的几步收敛OMP的算法如下 (1)用x表达你的信号，初始化残差e0=x； (2)选择与e0内积绝对值最大的原子，表达为φ1； (3)将选择的原子作为列构成矩阵Φt，定义Φt列空间的正交投影算子为 通过从e0减去其在Φt所张成空间上的正交投影得到残差e1； (4)对残差迭代执行(2)、(3)步； 其中I为单位阵需要注意的是在迭代过程中Φt为所有被选择过的原子构成的矩阵，因此每次都是不同的，因此由它生成的正交投影算子矩阵P每次都是不同的。

(5)直达到到某个指定的停止准则后停止算法OMP减去的Pem是em在所有被选择过的原子构成的矩阵Φt所张成空间上的正交投影，而MP减去的Pem是em在本次被选择的原子φm所张成空间上的正交投影经OMP算法重构后的成果如下所示：算法的使用时间如下：1.2 迭代硬阈值法（IHT）目的函数为这里中的M应当指的是M-sparse，S应当指的是Surrogate这里规定：之后我们运用式对目的函数进行变形接着便是获得极值点：运用该式进行迭代可以得到极值点，我们需要的是最小值此时目的函数的最小值就得到了此时便得到我们需要的公式：我们要保证向量y的稀疏度不不小于M，即，为了达到这一目的，要保存最大的M项（由于是平方，因此要取绝对值absolute value），剩余的置零（注意这里有个负号，因此要保存最大的M项）IHT算法成果：IHT算法使用时间如下：1.3 分段正交匹配追踪法（StOMP）分段正交匹配追踪(Stagewise OMP)也是由OMP改善而来的一种贪心算法，与CoSaMP、SP算法类似，不同之处在于CoSaMP、SP算法在迭代过程中选择的是与信号内积最大的2K或K个原子，而StOMP是通过门限阈值来拟定原子。

此算法的输入参数中没有信号稀疏度K，因此相比于ROMP及CoSaMP有独到的优势StOMP的算法流程：经StOMP算法重构后的成果如下所示：该算法的用时状况如下：1.4 分段弱正交匹配追踪法（SwOMP）分段弱正交匹配追踪(Stagewise Weak OMP)可以说是StOMP的一种修改算法，它们的唯一不同是选择原子时的门限设立，这可以减少对测量矩阵的规定我们称这里的原子选择方式为"弱选择"（Weak Selection），StOMP的门限设立由残差决定，这对测量矩阵（原子选择）提出了规定，而SWOMP的门限设立则对测量矩阵规定较低（原子选择相对简朴、粗糙）SWOMP的算法流程：经SwOMP算法重构后的成果如下所示：该算法的用时状况如下：1.5 广义正交匹配追踪法（GOMP）广义正交匹配追踪(Generalized OMP, gOMP)算法可以看作为OMP算法的一种推广OMP每次只选择与残差有关最大的一种，而gOMP则是简朴地选择最大的S个之因此这里表述为"简朴地选择"是相比于ROMP之类算法的，不进行任何其他解决，只是选择最大的S个而已GOMP算法流程如下：经GOMP算法重构后的成果如下所示：该算法的用时状况如下：1.6 基追踪法（BP）除匹配追踪类贪婪迭代算法之外，压缩感知重构算法另一大类就是凸优化算法或最优化逼近措施，此类措施通过将非凸问题转化为凸问题求解找到信号的逼近，其中最常用的措施就是基追踪(Basis Pursuit, BP)，该措施提出使用l1范数替代l0范数来解决最优化问题，以便使用线性规划措施来求解。

经BP算法重构后的成果如下所示：该算法的用时状况如下：2.推荐压缩感知算法在CDSN上有诸多简介和资源，这里推荐一种大神的博客，基本涉及了目前常用的所有的压缩感知算法的简介，固然后诸多是没有完整的代码资源的，但是初学者还是可以去学习一波AndyJee 这里尚有我的几种算法的实现：STOMP SWOMP GOMP BP SP 。