当前位置：文档之家› mp&omp 匹配追踪正交匹配追踪

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

1. 信号的稀疏表示(sparse representation of signals)

给定一个过完备字典矩阵，其中它的每列表示一种原型信号的原子。给定一个信号y，它可以被表示成这些原子的稀疏线性组合。信号y 可以被表达为y = Dx ，或者

。字典矩阵中所谓过完备性，指的是原子的个数远远大于信号y的长度(其长度很显然是n)，即n<

2.MP算法(匹配追踪算法)

2.1 算法描述

作为对信号进行稀疏分解的方法之一，将信号在完备字典库上进行分解。

假定被表示的信号为y，其长度为n。假定H表示Hilbert空间，在这个空间H里，由一组向量构成字典矩阵D，其中每个向量可以称为原子(atom)，其长度与被表示信号y 的长度n相同，而且这些向量已作为归一化处理，即|，也就是单位向量长度为1。MP算法的基本思想：从字典矩阵D（也称为过完备原子库中），选择一个与信号y 最匹配的原子(也就是某列)，构建一个稀疏逼近，并求出信号残差，然后继续选择与信号残差最匹配的原子，反复迭代，信号y可以由这些原子来线性和，再加上最后的残差值来表示。很显然，如果残差值在可以忽略的范围内，则信号y就是这些原子的线性组合。如果选择与信号y最匹配的原子？如何构建稀疏逼近并求残差？如何进行迭代？我们来详细介绍使用MP进行信号分解的步骤：[1] 计算信号y 与字典矩阵中每列(原子)的内积，选择绝对值最大的一个原子，它就是与信号y 在本次迭代运算中最匹配的。用专业术语来描述：令信号，从字典矩阵中选择一个最为匹配的原子，满足

，r0 表示一个字典矩阵的列索引。这样，信号y 就被分解为在最匹配原子的垂直投影分量和残值两部分，即：

。[2]对残值R1f进行步骤[1]同样的分解，那么第K步可以得到：

，其中满足

。可见，经过K步分解后，信号y 被分解为：，其中。

2.2 继续讨论

(1)为什么要假定在Hilbert空间中？Hilbert空间就是定义了完备的内积空。很显然，MP中的计算使用向量的内积运算，所以在在Hilbert空间中进行信号分解理所当然了。

(2)为什么原子要事先被归一化处理了，即上面的描述。内积常用于计算一个矢量在一个方向上的投影长度，这时方向的矢量必须是单位矢量。MP中选择最匹配的原子是，是选择内积最大的一个，也就是信号(或是残值)在原子(单位的)垂直投影长度最长的一个，比如第一次分解过程中，投影长度就是。，三个向量，构成一个三角形，且和正交（不能说垂直，但是可以想象二维空间这两个矢量是垂直的）。

(3)MP算法是收敛的，因为，和正交，由这两个可以得出，得出每一个残值比上一次的小，故而收敛。

2.3 MP算法的缺点

如上所述，如果信号(残值)在已选择的原子进行垂直投影是非正交性的，这会使得每次迭代的结果并不少最优的而是次最优的，收敛需要很多次迭代。举个例子说明一下：在二维空间上，有一个信号y 被D=[x1, x2]来表达，MP算法迭代会发现总是在x1和x2上反复迭代，即，这个就是信号(残值)在已选择的原子进行垂直投影的非正交性导致的。再用严谨的方式描述[1]可能容易理解:在Hilbert空间H中，

，，定义，就是它是这些向量的张成中的一个，MP构造一种表达形式：;这里的Pvf表示f在V

上的一个正交投影操作，那么MP算法的第k 次迭代的结果可以表示如下(前面描述时信号为y，这里变成f了，请注意)：

如果是最优的k项近似值，当且仅当。由于MP仅能保证，

所以一般情况下是次优的。这是什么意思呢？是k个项的线性表示，这个组合的值

作为近似值，只有在第k个残差和正交，才是最优的。如果第k个残值与正交，意味这个残值与fk的任意一项都线性无关，那么第k个残值在后面的分解过程中，不可能出现fk中已经出现的项，这才是最优的。而一般情况下，不能满足这个条件，MP一般只能满足第k个残差和xk正交，这也就是前面为什么提到“信号(残值)在已选择的原子进行垂直投影是非正交性的”的原因。如果第k个残差和fk不正交，那么后面的迭代还会出现fk中已经出现的项，很显然fk就不是最优的，这也就是为什么说MP收敛就需要更多次迭代的原因。不是说MP一定得到不到最优解，而且其前面描述的特性导致一般得到不到最优解而是次优

解。那么，有没有办法让第k个残差与正交，方法是有的，这就是下面要谈到的OMP 算法。

3.OMP算法

3.1 算法描述

OMP算法的改进之处在于：在分解的每一步对所选择的全部原子进行正交化处理，这使得在精度要求相同的情况下，OMP算法的收敛速度更快。

那么在每一步中如何对所选择的全部原子进行正交化处理呢？在正式描述OMP算法前，先看一点基础思想。

先看一个k 阶模型，表示信号f 经过k 步分解后的情况，似乎很眼熟，但要注意它与MP算法不同之处，它的残值与前面每个分量正交，这就是为什么这个算法多了一个正交的原因，MP中仅与最近选出的的那一项正交。

(1)

k + 1 阶模型如下：

(2)

应用k + 1阶模型减去k 阶模型，得到如下：

(3)

我们知道，字典矩阵D的原子是非正交的，引入一个辅助模型，它是表示对前k个项的依赖，描述如下：

(4)

和前面描述类似，在span(x1, ...xk)之一上的正交投影操作，后面的项是残值。这个关系用数学符号描述：

请注意，这里的a 和b 的上标表示第k 步时的取值。

将(4)带入(3)中，有：

（5）

如果一下两个式子成立，(5)必然成立。

(6)

(7)

令，有

其中。

ak的值是由求法很简单，通过对(7)左右两边添加作内积消减得到：

后边的第二项因为它们正交，所以为0，所以可以得出ak的第一部分。对于，在（4）左右两边中与作内积，可以得到ak的第二部分。

对于(4)，可以求出；

3.2 收敛性证明

通过(7)，由于与正交，将两个残值移到右边后求二范的平方，并将ak的值代入可以得到：

可见每一次残差比上一次残差小，可见是收敛的。

分段正交匹配追踪算法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/d316451074.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

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

第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

贪婪算法中正交匹配追踪算法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