精华内容
参与话题
问答
  • MP算法详细过程解析

    千次阅读 2017-06-26 13:46:35
    MP算法

    目的:判断目标串(T串)中是否含有模式串(P串),在下文中为了方便,命名目标串为“长串”,模式串为“短串”。

    显而易见的是,不断判断字符是否相同的过程就是两个指针移动的过程。MP算法就是要相比于暴力搜索BF,简化指针移动的过程。

    首先对图中的标识做解释,黄色填充代表长串指针的移动,红色字符代表匹配失效的时刻,绿色填充的数字代表列,也是长串每一个字符的索引值,蓝色填充数字代表短串的索引。   

    MP算法过程:长串的指针从来没有回溯。长串指针移动规则:长串在与短串的第一个字符匹配失败时指针向前移动一个位置,长串在短串某个字符匹配成功时向前移动一个位置,长串在与短串(除第一个字符)的某字符匹配失败时不移动指针。短串指针移动规则:若在短串的j位置匹配失败,下一次的匹配位置移动到f(j-1)+1 的位置。   

    好了,按照这个规则我们用按图索骥走一遍吧。第一次匹配失败发生在第1列(绿色列),并不是短串的第一个字符失匹,长串指针不动,短串指针j=1(蓝色索引),下一次(f(1-1)+1)=0,指针到0索引,也就是第一个字符。第二次不匹配发生在短串的第一个字符,长串指针移动一个,短串指针仍在第一个字符。第三次不匹配发生在第八列,因为不是短串的首字符,长串指针不动,短串指针j=6,f(6-1)+1=2,指针移动到索引为2的字符。第四次不匹配,失匹字符不是短串第一个,所以长串指针不动,短串指针j=2,f(2-1)+1=0,指针移动到索引0字符。最后一直在匹配,长串指针向前走。     MP好处:长串没有回溯。从第三次不匹配到图中第四次,短串走了很远。肯定要比暴力一次走一步搜索速度快。至于为什么,就是因为短串中前部分子串和后部分子串有可能相同,这就导致移动的时候可以多移动点,用文字我解释不清楚,大家再想想吧。



    void MP(string T, string P){
    		int lenT = T.length();//长
    		int lenP = P.length();//短
    		vector<int> v(lenP + 1, 0);
    		MP_bulid_v(v, P);
    		int i = 0, j = 0;//i是短串的指针 j是长串的指针
    		//整个过程就是两个指针的移动
    		while (j < lenT){
    			while (i>-1 && P[i] != T[j])
    				i = v[i];
    			i++;
    			j++;
    			if (i >= lenP){
    				//成功找到一组
    				cout << j - i;
    				i = v[i];//接下来找下一组
    			}
    		}
    
    
    	}
    	void MP_bulid_v(vector<int> &v, string &P){
    		int m = P.length();
    		int i = 0;
    		int j = v[0] = -1;
    		while (i < m){
    			while (j>-1 && P[i] != P[j])
    				j = v[j];//这里的实现非常巧妙 很难想到
    			i++;
    			j++;
    			v[i] = j;
    		}
    	}


    展开全文
  • MP算法与OMP算法

    千次阅读 2014-01-17 13:40:01
    MP算法是一种贪心算法(greedy),每次迭代选取与当前样本残差最接近的原子,直至残差满足一定条件。 首先解决两个问题,怎么定义“最接近原子”,怎么计算残差? 选择最接近残差的原子:MP里定义用向量内积原子与...

    稀疏编码的一般最优化公式为:


    其中的零范数为非凸优化。那么如何解这么一个非凸优化问题呢?其中一个常用的解法就是MP算法。


    MP算法

    MP算法是一种贪心算法(greedy),每次迭代选取与当前样本残差最接近的原子,直至残差满足一定条件。


    求解方法


    首先解决两个问题,怎么定义“最接近原子”,怎么计算残差?

    选择最接近残差的原子:MP里定义用向量内积原子与残差的距离,我们用R表示残差,di表示原子,则:

    Max[Dist(R,di)]=max[<R,di>];

    残差更新:R=R-<R,di>I;继续选择下一个,直至收敛;


    需要注意的是,MP算法中要求字典原子||di||=1,上面的公式才成立。

    我们用二维空间上的向量来表示,用如下的图来表述上面的过程:


    上图中d1,d2,d3表示归一化的原子,红色向量r表示当前残差;

    进过内积计算,<r,d3>最大,于是r分解为d3方向以及垂直于d3方向的两个向量(<r,d3>d3及r-<r,d3>d3),把d3方向的分量(<r,d3>d3)加入到已经求得的重构项中,那么绿色向量(r-<r,d3>d3)变为新的残差。

    再一轮迭代得到如下:


    R往d1方向投影分解,绿色向量成为新的残差。

     

    具体算法:

     


    收敛性

    从上面的向量图我们可以清楚地看出,k+1的残差Rk+1是k步残差Rk的分量。根据直角三角形斜边大于直角边,|Rk+1|<=|Rk|,则算法收敛。


    注意事项:

    1.上面也讲过,字典的原子是归一化的,也就是||di||=1,因为我们选取max<R,di>时,如果di长度不统一,不能得出最好的投影。

    2.如果我们的字典只有两个向量d1,d2,那么MP算法会在这两个向量间交叉迭代投影,也就是f=a1d1+a2d2+a3d1+a4d2+…..;也就是之前投影过的原子方向,之后还有可能投影。换句话说,MP的方向选择不是最优的,是次优的。

    如下图:


    这也是其改进版本OMP要改进的地方。

     

    OMP算法

    也就是正交的MP算法。

    MP算法的次最优性来源其残差只与当前投影方向垂直,这样在接下来的投影中,很有可能会再次投影到原来的方向。

    于是,在投影时,如果我们使得残差Rk+1与x1-xk+1的所有向量垂直,则可以克服这个问题,如下:

     


    求解方法

    假设我们已经得到了第k步的最优解:


    我们要继续更新到第k+1步,目标是得到:


    需要注意的是,我们下一步更新时,之前原子的系数 也要更新,否则不能满足约束。

    于是我们需要求得如何更新之前原子系数 ,以及如何求得下一个投影方向 。

     





    收敛性:

    同样根据勾股定理,得到如下:

    于是算法收敛。

     

    具体步骤:


     

    最后,贴一个sparse求解的工具包,里面包含了MP,OMP算法的代码:

    http://spams-devel.gforge.inria.fr/

     

    参考文献:

    http://lear.inrialpes.fr/people/mairal/tutorial_iccv09/

    http://blog.csdn.net/scucj/article/details/7467955

    OrthogonalMatching Pursuit:Recursive Function Approximation with Applications to WaveletDecomposition

    展开全文
  • 压缩感知的MP算法

    千次阅读 2016-03-19 20:41:14
    2.MP算法 作为一类贪婪算法,MP算法的基本思路是在迭代中不断找寻最有测量矩阵列来逼近被表示向量,继而寻得最优的稀疏逼近,使得x与y的残差最小。对于这个算法,最直观的问题有两个:1.如何选择逼近度最高的——...


    2.MP算法

    作为一类贪婪算法,MP算法的基本思路是在迭代中不断找寻最有测量矩阵列来逼近被表示向量,继而寻得最优的稀疏逼近,使得x与y的残差最小。对于这个算法,最直观的问题有两个:1.如何选择逼近度最高的——如何衡量逼近度,算法如何执行(比如遍历)?2.x的稀疏度由迭代次数决定,而逼近度(即最终残差)也与迭代次数有关,这是一个两难问题,如何做权衡?

    在回答以上两个问题之前,我们先给出MP算法的具体过程:


    示例代码如下:(与matlab中MP介绍时的示例相同)

    clear all
    close all
    %
    A = [1 0.5 -1/2^0.5;
        0 (3/4)^0.5 -1/2^0.5];
    y = [1,0.5]';
    K = 3;
    [m,n] = size(A);
     
     
    % iteration
    Rf(:,1) = y;
    for k = 1:K
        
        for i = 1:n 
            ip(i) = abs(Rf(:,k)'*A(:,i));
        end
        j(k) = find(max(ip)==ip);
        Rf(:,k+1) = Rf(:,k) - Rf(:,k)'*A(:,j(k))*A(:,j(k));
        Rfnorm(k) = norm(Rf(:,k));
    end
    R = [A(:,j(1)),A(:,j(2)),A(:,j(3))];
    r1 = R(:,1);
    r2 = R(:,2);
    r3 = R(:,3);
    figure,quiver(0,0,y(1),y(2),'r');
    hold,quiver(0,0,r1(1),r1(2),'b');
    quiver(0,0,r2(1),r2(2),'b');
    quiver(0,0,r3(1),r3(2),'b');
    display(norm(Rf(:,K+1)));
    

    编程遇到的简单问题:

    1.每次迭代选择A中列向量时,为什么不需要把上次选择的去除掉?

    因为每次迭代的残差是由上次的残差减去已选择的A的列计算得到的,剩余残差(恰好衡量与已选列的差异性)在已选列向量的投影将变得很小。因此没有必要去除已选列。

    2.随机字典A的生成

    示例中未涉及这个问题,但是仿真往往需要。matlab命令式norm(a,b,c,d),产生均值a,方差b,大小c*d的随机矩阵。

    3.如何画向量?

    画箭头的命令是quiver(x,y,u,v),xy为顶点,uv为向量。


    展开全文
  • MP算法和OMP算法及其思想

    万次阅读 多人点赞 2012-04-17 03:09:18
    主要介绍MP(Matching Pursuits)算法和OMP(Orthogonal Matching Pursuit)算法[1],这两个算法虽然在90年代初就提出来了,但作为经典的算法,国内文献(可能有我没有搜索到)都仅描述了算法步骤和简单的应用,并未对其...

    主要介绍MP(Matching Pursuits)算法和OMP(Orthogonal Matching Pursuit)算法[1],这两个算法虽然在90年代初就提出来了,但作为经典的算法,国内文献(可能有我没有搜索到)都仅描述了算法步骤和简单的应用,并未对其进行详尽的分析,国外的文献还是分析的很透彻,所以我结合自己的理解,来分析一下写到博客里,算作笔记。

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

    给定一个过完备字典矩阵,其中它的每列表示一种原型信号的原子。给定一个信号y,它可以被表示成这些原子的稀疏线性组合。信号 y 可以被表达为 y = Dx ,或者。 字典矩阵中所谓过完备性,指的是原子的个数远远大于信号y的长度(其长度很显然是n),即n<<k。

    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的值代入可以得到:


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

    3.3 算法步骤

    整个OMP算法的步骤如下:

    由于有了上面的来龙去脉,这个算法就相当好理解了。

    到这里还不算完,后来OMP的迭代运算用另外一种方法可以计算得知,有位同学的论文[2]描述就非常好,我就直接引用进来:

    对比中英文描述,本质都是一样,只是有细微的差别。这里顺便贴出网一哥们写的OMP算法的代码,源出处不得而知,共享给大家。

    再贴另外一个洋牛paper[3]中关于OMP的描述,之所以引入,是因为它描述的非常严谨,但是也有点苦涩难懂,不过有了上面的基础,就容易多了。


    它的描述中的Sweep步骤就是寻找与当前残差最大的内积时列在字典矩阵D中的索引,它的这个步骤描述说明为什么要选择内积最大的以及如何选择。见下图,说的非常清晰。


    它的算法步骤Update Provisional Solution中求很简单,就是在 b = Ax 已知 A和b求x, 在x的最小二范就是A的伪逆与b相乘,即:


    看上去头疼,其实用matlab非常简单,看看上面的matlab的代码就明白了。

    我们可以看得出来,算法流程清晰明了,还是很好理解的。这正是OMP算法的魅力,作为工具使用简单,背后却隐藏着很有趣的思想。

    写这篇博客的目的,是因为搜索了一下,MP和OMP没有人很详细的介绍。文献[1]讲的很清楚的,大家有兴趣可以找来看看。不要被老板发现我居然在搜中文文献还写中文博客。


    参考文献:

    [1] Orthogonal Matching Pursuit:Recursive Function Approximat ion with Applications to Wavelet Decomposition
    [2]http://wenku.baidu.com/view/22f3171614791711cc7917e4.html

    [3] From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images

    展开全文
  • 理解MP算法

    千次阅读 2017-03-07 21:01:05
    作为一类贪婪算法,MP算法的基本思路是在迭代中不断找寻最有测量矩阵列来逼近被表示向量,继而寻得最优的稀疏逼近,使得x与y的残差最小。对于这个算法,最直观的问题有两个:1.如何选择逼近度最高的——如何衡量逼近...
  • MP算法

    千次阅读 2016-12-29 10:37:58
    MP算法 MP算法是一种贪心算法(greedy),每次迭代选取与当前样本残差最接近的原子,直至残差满足一定条件。 求解方法 首先解决两个问题,怎么定义“最接近原子”,怎么计算残差? 选择最...
  • MP算法实现

    热门讨论 2012-12-14 19:03:32
    该程序为MP算法的matlab实现,是一维信号的恢复,本人认为是很好的CS入门材料
  • MP算法OMP算法及其思想与实现

    万次阅读 2017-01-09 16:29:44
    主要介绍MP(Matching Pursuits)算法OMP(Orthogonal Matching Pursuit)算法[1],这两个算法虽然在90年代初就提出来了,但作为经典的算法,国内文献(可能有我没有搜索到)都仅描述了算法步骤和简单的应用,并未对其...
  • 稀疏分解中的MPOMP算法

    万次阅读 多人点赞 2017-04-12 15:11:57
    主要介绍MPOMP算法的思想与流程,解释为什么需要引入正交? !!今天发现一个重大问题,是在读了博主的正交匹配追踪(OMP)在稀疏分解与压缩感知重构中的异同,...
  • MP算法OMP算法介绍

    千次阅读 2014-03-01 16:47:21
    主要介绍MP(Matching Pursuits)算法OMP(Orthogonal Matching Pursuit)算法[1],这两个算法虽然在90年代初就提出来了,但作为经典的算法,国内文献(可能有我没有搜索到)都仅描述了算法步骤和简单的应用,并未对其...
  • 版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...
  • 主要介绍MP(Matching Pursuits)算法OMP(Orthogonal Matching Pursuit)算法[1],这两个算法虽然在90年代初就提出来了,但作为经典的算法,国内文献(可能有我没有搜索到)都仅描述了算法步骤和简单的应用,并未对其...
  • OMP算法

    千次阅读 2016-12-07 09:49:54
    OMP算法思想假设信号s∈Rd\mathbf{s}\in\mathbb{R}^d的稀疏度为mm, {x1,...,xN}\{\mathbf{x}_1,...,\mathbf{x}_N\}是NN个基向量. Φ∈RN×d\mathbf{\Phi}\in\mathbb{R}^{N\times d}是由这些基向量构成的测量矩阵。...
  • 浅谈压缩感知(二十):MP算法OMP算法及其在人脸识别的应用 主要内容: 1、MP算法 2、OMP算法 3、OMP算法的matlab实现 4、OMP在压缩感知和人脸识别的应用   一、MP(Matching Pursuits)与OMP(Orthogonal ...
  • 匹配追踪MP和正交匹配追踪OMP算法

    万次阅读 2018-03-01 15:25:38
    匹配追踪MP和正交匹配追踪OMP算法...匹...
  • 转自:http://blog.csdn.net/scucj/article/details/7467955 主要介绍MP(Matching Pursuits)算法OMP(Orthogonal Matchin...
  • OMP算法笔记

    千次阅读 2019-06-20 14:56:47
    OMP算法笔记欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...
  • MPOMP算法

    2013-10-24 17:31:55
    匹配追踪MP、正交匹配追踪算法OMP,稀疏表示里的基本算法
  • OMP算法: % OMP的函数 % s-测量;T-观测矩阵;N-向量大小 function hat_y=omp_fun(s,T,K) N = size(T,2); Size=size(T); % 观测矩阵大小 M=Size(1); % 测量 ...
  • OMP算法MATLAB程序

    热门讨论 2012-02-20 18:49:21
    很好用的OMP算法程序,经过本人多次使用 ,很实用

空空如也

1 2 3 4 5 ... 20
收藏数 66,813
精华内容 26,725
关键字:

mp算法